Pavages au moyen de losanges
Réponses
-
Cas du décagone : est-il évident que pour tout pavage par losanges, on peut choisir tous les sommets de façon unique dans l'hypercube unité ? (cela me semble vrai...)
-
C'est très clair qu'on peut, en suivant les arêtes du pavage, remonter les sommets du pavage de manière unique en des sommets de l'hypercube. On remonte aussi les losanges du pavage en des 2-faces de l'hypercube. Et un "flip" autour d'un sommet de degré 3 se passe sur une 3-face (c.-à-d. un vrai cube) de l'hypercube.
Tout ceci pour n'importe quel $2n$-gone.
Mais ensuite ? Je ne vois pas bien comment exploiter ça. En as-tu une idée ? Un bon test : voir si ça peut servir à résoudre le petit sudoku du week-end que j'ai posé ici. Le codage par les diagrammes de tresse m'a été très utile pour trouver une solution. -
@ GBMZ, Caramba, encore t'as raison!
-
Pas encore d'idée... pour vous faire patienter, le graphe des flips de l'octogone.
-
En code normalisé (en démarrant avec le 1 sur le côté du haut et en tournant dans le sens direct) :
$$\begin{array}{ccccccc}
[2][123][2][1]&\leftrightarrow&[123][12][1]&\leftrightarrow&[123][2][12]&\leftrightarrow&[3][123][12]\\
\updownarrow & & & & & & \updownarrow\\
[23][123][1]&\leftrightarrow&[23][2][123]&\leftrightarrow&[3][23][123]&\leftrightarrow&[3][2][123][2]
\end{array}$$
Le diagramme se complexifie pour un décagone (3 flips possibles pour chaque pavage). Un tout petit bout :
$$\begin{array}{ccccc}
&&[1234][123][12][1]&&\\
&\swarrow&\downarrow&\searrow&\\
[2][1234][23][12][1]&&[1234][2][123][2][1]&&[1234][123][2][12]
\end{array}$$ -
Je m'aperçois que j'ai fait une erreur en pensant que le nombre de sommets intérieurs de degré 3 pour les pavages d'un $2n$-gone est un invariant égal à $n-2$ (en particulier $3$ pour un décagone). Voici le contre-exemple d'un décagone pavé avec quatre sommets intérieurs de degré 3.
-
Donc pour la peine tu vas nous dessiner le graphe complet des flips du décagone :-D
[Edit : allez, juste le nombre suffira !] -
Faisable avec un peu de soin, mais pas ce soir.
Surtout, j'aimerais bien pouvoir dénombrer les "codes normalisés" de manière plus systématique. On verra ça plus tard.
En attendant, une solution du sudoku du week-end : -
Je crois bien qu'on a raté le plus évident des décagones avec 5 flips... (généralisable au cas n impair).
(figure honteusement récupérée sur le net) -
Effectivement, le $[4][234][2][1234][2]$ et son acolyte $[3][1234][3][123][1]$.
Je l'avais dans mon graphe, mais il me manquait une arête.
Je trouve $60$ pour le nombre de pavages du décagone (sans prendre en compte l'action du groupe diédral), mais comme c'est fait à la main il est fort possible que j'en ai oubliés (la preuve, j'avais oublié une arête).
Les orbites sous le groupe diédral, ça fait bien sûr beaucoup moins.
PS. J'en ai déjà repéré deux manquants, j'arrive à 62 et ce n'est peut être pas fini. Une révision sérieuse s'impose. -
Voilà une suite de polygones de 14 à 4 côtés.
Sur un polygone donné
on marque en orange une brochette.
On enlève cette brochette,
on ressoude les bords,
et on déforme le résultat pour obtenir le polygone régulier suivant.
Sur le polygone suivant la ligne de soudure est dessinée en jaune. -
Je n'ai pas encore réalisé ce calcul, mais dénombrer selon le nombre de losanges jaunes sur les côtés mérite sans doute un essai. Cela doit aller très vite avec des pièces à manipuler.
-
Bonjour,
Enseignons tout cela à un ordinateur, sur le modèle "lorsqu'on ne sait pas faire quelque chose, on l'enseigne". On part d'une figure Geogebra. Il s'agit d'un $2n$gone, avec $n=7$. Le contour est constitué des points $A_{j}\doteq u^{j}$ avec $u^{6}-u^{5}+u^{4}-u^{3}+u^{2}-u+1=0$ ($u$ est racine primitive d'ordre 14). On récupère la liste des points intérieurs par une mise en forme de l'historique:B:=A1 + A13 - xA0 ; C:=A10 + A12 - xA11 ; D:=A8 + A10 - xA9 ; E:=A2 + A4 - xA3 ; F:=A4 + A6 - xA5 ; G:=C + D - xA10 ; H:=A13 + C - xA12 ; R:=B + H - xA13 ; J:=A1 + R - xB ; K:=A7 + F - xA6 ; L:=G + H - xC ; M:=R + L - xH ; N:=A4 + M - xE ; P:=A7 + D - xA8 ; Q:=K + P - xA7 ;
On récupère de même la liste des losanges. Il y en a $n\left(n-1\right)/2$.poly1 :=[ A1, A0, A13, B ] ; poly6 :=[ A12, A13, H, C ] ; poly2 :=[ A10, A11, A12, C ] ; poly9 :=[ A2, A1, J, E ] ; poly3 :=[ A8, A9, A10, D ] ; poly10:=[ A7, A6, F, K ] ; poly4 :=[ A4, A3, A2, E ] ; poly17:=[ A8, A7, P, D ] ; poly5 :=[ A6, A5, A4, F ] ; poly7 :=[ A13, H, R, B ] ; poly12:=[ H, L, M, R ] ; poly8 :=[ A1, J, R, B ] ; poly13:=[ H, C, G, L ] ; poly11:=[ A10, C, G, D ] ; poly14:=[ E, J, R, M ] ; poly15:=[ A4, E, M, N ] ; poly19:=[ M, Q, K, N ] ; poly16:=[ A4, N, K, F ] ; poly20:=[ M, L, G, Q ] ; poly18:=[ A7, K, Q, P ] ; poly21:=[ Q, G, D, P ] ;
On calcule alors les brochettes. On part du segment $A_{j}A_{j+1}$. On cherche son losange. On supprime les deux sommets déjà vus, obtenant un autre segment. On cherche ses losanges, on supprime celui déjà vu, etc. Cela donne: \[ \begin{array}{c|cccccc} 1 & 1 & 7 & 12 & 20 & 21 & 17\\ 2 & 9 & 14 & 12 & 13 & 11 & 3\\ 3 & 4 & 15 & 19 & 18 & 17 & 3\\ 4 & 4 & 9 & 8 & 7 & 6 & 2\\ 5 & 5 & 10 & 18 & 21 & 11 & 2\\ 6 & 5 & 16 & 19 & 20 & 13 & 6\\ 7 & 10 & 16 & 15 & 14 & 8 & 1 \end{array} \] On sait que, au moins pour le pavage d'un polygone régulier (argument angle+surface), il y a exactement un losange par paire de brochettes. On fait donc un listing inverse et on l'imprime sur la figure.
Ensuite de quoi, on redéfinit le bord selon \[ A_{0}=A_{1}=1,\;\left(A_{j+1}=v^{j}\right)_{j=1..6},\;\left(A_{j+2}=v^{j}\right)_{j=6..11} \] avec $v^{4}-v^{2}+1=0$ (i.e. $v$ est une racine primitive 12ème de l'unité). On a donc identifié $A_{0}=A_{1}$ ainsi que $A_{7}=A_{8}$, et réparti les autres le long du cercle unité. Le résultat est remarquable:
Sans rien faire d'autre, la brochette $1$ est devenue invisible, les autres brochettes sont toujours là (avec un élément visible de moins chacune). et les faces $(4,7)$, $(3,6)$ et $(2,5)$ sont devenues des carrés !
Par ailleurs et indépendamment, on peut programmer la réorganisation du 2n-gone initial, en flippant successivement le long des brochettes successives. Et, en 12 flips, on obtient:
Tout cela, c'est facile. Revenons à la liste des intersection. Il paraît que l'on peut traduire le graphe ci-dessous en une tresse. Et même tresser le redressement qui fournit le pavage radial depuis le sommet A7. GBZM ne détaille pas la chose. C'est un style d'exposé comme un autre. Mais ceux qui opinent ne détaillent pas non plus. Mauvais pressentiment !
\[ \begin{array}{c|ccccccccccccccccccccc} polygon & 1 & 8 & 9 & 7 & 6 & 4 & 14 & 12 & 13 & 15 & 2 & 20 & 19 & 16 & 11 & 5 & 21 & 18 & 10 & 3 & 17\\ \hline br1 & 1 & 4 & 2 & 1 & 4 & 3 & 2 & 1 & 2 & 3 & 4 & 1 & 3 & 6 & 2 & 5 & 1 & 3 & 5 & 2 & 1\\ br2 & 7 & 7 & 4 & 4 & 6 & 4 & 7 & 2 & 6 & 7 & 5 & 6 & 6 & 7 & 5 & 6 & 5 & 5 & 7 & 3 & 3 \end{array} \]
A toutes fins utiles, je rappelle le dessin "explicatif" fourni par GBZM:
Par ailleurs $352654321235463524635$ se groupe en $\left(35\right)\left(26\right)54321235\left(46\right)\left(35\right)\left(246\right)\left(35\right)$ et traduit la figure 68584. L'algorithme de normalisation consiste à faire du tri à bulle... en ne faisant remonter la bulle que si la distance est supérieure ou égale à 2.
On obtient (facile) $565345623212345634523$ (comme indiqué), qui se groupe en $56\left(53\right)45\left(62\right)3212345\left(63\right)4\left(52\right)3$ conduisant à un graphe à 17 cases, au lieu du graphe initial à 14 cases.
Cordialement, Pierre. -
Bon, Soland ne commence pas sa numérotation avec 1, mais avec 0, et il ne part pas du côté tout en haut. Qu'à cela ne tienne, suivons la numérotation de Soland et voyons comment coder avec, en suivant sur les images ci-dessous :
1e étape : $[5]$ ou, en notation pythonesque $[5:6]$
2e : $[5][345]$ ou $[5:6][3:6]$
3e : $[5][345][234]$ ou $[5:6][3:6][2:5]$
4e : $[5][345][234][2]$ ou $[5:6][3:6][2:5][2:3]$
5e : $[5][345][234][2][1]$ ou $[5:6][3:6][2:5][2:3][1:2]$
6e : $[5][345][234][2][1][012345]$ ou $[5:6][3:6][2:5][2:3][1:2][0:6]$
7e : $[5][345][234][2][1][012345][2]$ ou $[5:6][3:6][2:5][2:3][1:2][0:6][2:3]$
8e : $[5][345][234][2][1][012345][2][1234]$ ou $[5:6][3:6][2:5][2:3][1:2][0:6][2:3][1:5]$
9e : $[5][345][234][2][1][012345][2][1234][3]$ ou $[5:6][3:6][2:5][2:3][1:2][0:6][2:3][1:5][3:4]$.
Voila, le code du pavage est fabriqué. -
Monsieur est magnanime.:-)
-
Juste pour complément, la suite recherchée est connue de l'OEIS, c'est A006245 ("number of rhombic tilings of 2n-gon")
-
Ha ha, mon 62 pour le décagone était donc juste !
-
Bon, c'est bien beau tout ça,
Coxeter s'est posé la question avant Christoph (facile d'imaginer que Christoph se doutait qu'il avait des ancêtres). On a tous (Christoph, Pierre, GBZM, Jaybe et moi) raconté nos salades: erreurs, tâtonnements et vérités, un peu comme des enfants qui savent que leur problème n'est pas né aujourd'hui mais veulent le chercher seulement "entre eux".
Domi (que je salue) a balancé Coxeter et Jaybe l'oeis. Le 62, et je le comprends (GBZM, pas le 62), a fait plaisir à GBZM et Christoph a dessiné une heureuse progression.
Reste que, quand je tape "1,1,1,6" sur oeis, je ne trouve rien concernant notre problème (à propos, savez-vous comment sont classées dans oeis les séquences? je m'attendais à ce que ce soit par ordre d'apparition et il n'en est rien).
Bref il reste déjà à prouver que le 62 de GBZM est trivial (i.e. énoncer la succession de trivialités qui mènent à lui, comme dirait CC (que je salue aussi et qui me manque, un con en déduirait-il que je le vénère), ensuite à prolonger "1,1,1,6" à l'infini si possible pour satisfaire pleinement Christoph.
Merci donc à Coxeter et oeis, mais, moi, je reste sur ma faim: j'ai progressé dans la compréhension, mais je n'ai pas encore compris.
Amicalement
Paul
Edit: complément -
Pour le 62, c'est vraiment trivial et ça demande juste un peu de soin en travaillant avec les codes.
Un code a un niveau qui est la somme de ses chiffres. Il est bien invariant par les transformations $ij\leftrightarrow ji$ pour $|i-j|>2$, il monte de $1$ pour les flips $i(i+1)i \to (i+1)i(i+1)$ (flips montants) et il descend de $1$ pour les flips $(i+1)i(i+1)\to i(i+1)i$ (flips descendants). Le code normalisé de niveau maximal est $[3][23][123][0123]$ (niveau 20) et le code normalisé de niveau minimal est $[0123][012][01][0]$ (niveau 10).
Il y a une involution sur l'ensemble des codes : on prend un code, on le lit à l'envers et on complète ses chiffres à $3$ ; cette involution fait par exemple passer du code de niveau minimal au code de niveau maximal, et vice-versa. L'involution change le niveau selon $t\mapsto 30-t$. (On remarquera que je numérote maintenant à partir de $0$, juste pour faire plaisir à Soland).
Ceci étant dit, il suffit maintenant de partir du niveau 20 et de suivre soigneusement les flips descendants pour arriver au niveau 15 (on peut s'arrêter là, le reste de la descente vient par l'involution). Allons-y, en faisant un tableau avec les codes normalisés !
Niveau 20
$$\begin{array}{c|c|c}
\mbox{code}&\mbox{flip} \uparrow &\mbox{flip }\downarrow\\
\hline
[3][23][123][0123]&0&3
\end{array}$$
Niveau 19
$$\begin{array}{c|c|c}
\mbox{code}&\mbox{flip} \uparrow &\mbox{flip }\downarrow\\
\hline
[23][2][123][0123]&1&2\\
[3][2][123][2][0123]&1&2\\
[3][23][12][0123][2]&1&2
\end{array}$$
Niveau 18
$$\begin{array}{c|c|c}
\mbox{code}&\mbox{flip} \uparrow &\mbox{flip }\downarrow\\
\hline
[23][123][1][0123]&1&3\\
[23][2][12][0123][2]&2&2\\
[3][123][12][0123]&1&2\\
[3][2][123][0123][1]&1&2\\
[3][23][1][0123][12]&1&3
\end{array}$$
Niveau 17
$$\begin{array}{c|c|c}
\mbox{code}&\mbox{flip} \uparrow &\mbox{flip }\downarrow\\
\hline
[2][123][2][1][0123]&1&2\\
[23][12][1][0123][2]&2&1\\
[23][123][0123][0]&1&2\\
[23][2][1][0123][12]&2&1\\
[123][2][12][0123]&1&2\\
[3][123][1][0123][1]&2&3\\
[3][2][12][0123][2][1]&1&2\\
[3][2][1][0123][2][12]&1&2\\
[3][23][0123][012]&1&2
\end{array}$$
Niveau 16
$$\begin{array}{c|c|c}
\mbox{code}&\mbox{flip} \uparrow &\mbox{flip }\downarrow\\
\hline
[123][12][1][0123]&2&1\\ %
[2][123][2][0123][0]&2&2\\ %
[23][12][0123][2][0]&2&1\\ %
[23][2][0123][012]&2&1\\ %
[123][2][1][0123][1]&2&1\\ %
[3][12][1][0123][2][1]&2&1\\ %
[3][123][0123][01]&1&2\\
[3][2][1][0123][12][1]&2&1\\
[3][2][0123][2][012]&2&2
\end{array}$$
Niveau 15
$$\begin{array}{c|c|c}
\mbox{code}&\mbox{flip} \uparrow &\mbox{flip }\downarrow\\
\hline
[123][12][0123][0]&2&1\\ %
[2][123][0123][1][0]&1&2\\ %
[23][1][0123][12][0]&1&2\\ %
[23][0123][1][012]&1&2\\ %
[123][2][0123][01]&2&1\\ %
[3][12][0123][2][01]&2&1\\ %
[3][2][0123][012][1]&2&1\\
[3][0123][12][012]&1&2
\end{array}$$
On peut vérifier que le nombre total de flips descendants du niveau $n+1$ correspond bien au nombre total de flips montants du niveau $n$. J'aurais pu dessiner le graphe pour faire plaisir aussi à Jaybe, mais j'ai eu peur que ça soit un peu brouillon. On peut aussi remarquer l'appariement par involution sur le niveau 15.
Récapitulons : 1 de niveau 20, 3 de niveau 19, 5 de niveau 18, 8 de niveau 17, 9 de niveau 16, ça fait 27. Plus encore 27 pour les niveaux 14 à 10, par involution, on arrive à 54. Et enfin 8 pour le niveau 15, voila les 62 ! -
Paul,
j'ai pris le problème en route et je trouve déjà très impressionnant que le nombre de losanges et leur nature soit parfaitement défini par le nombre de côtés du polygone . Pour le dénombrement des configurations modulo le groupe diédral , on change clairement de catégorie et il faut trouver un bon angle d'attaque . Michel propose des tresses , il y a sûrement d'autres approches mais ce n'est certainement pas simple .
Rien ne nous interdit de traiter le cas des petits polygones mais pour une généralisation il va falloir se montrer très original car du beau monde s'est déjà intéressé à l'affaire .
Un amical salut à toi aussi :-D
Joli problème en tout cas ( merci Chritoph ).
Domi -
Pour le cas des configurations du décagone, le (très joli !) lien de Domi fournit ce qu'il faut :
2 + 10 + 10 + 10 + 10 + 10x2 (symétrie) = 62. -
Je m'en doutais : Emergence d'archives, codes simples pour ceux qui les conçoivent, etc.
Comme pour Paul, il me reste de l'appétit.
J'aime bien GBZM qui bouffe son polygone avec ordre et méthode en partant d'un côté.
J'avais dans l'idée de coder la position des centres des losanges via leurs affixes, modulo le groupe des racines de l'unité,
genre $(12,e^2+e^7)$
Trop compliqué pour moi.
En attendant d'autres posts, voilà un pavage du 20-gone; groupe d'isométries $C_5$. -
Je ne voudrais pas ajouter des problèmes au problème ( en fait si :-D ) .
Le décompte des différents pavages modulo les symétries est plutôt pénible et je me suis posé un autre problème assez proche du sujet initial :
On pave un polygone équiangle à côtés entiers ( le plus petit étant égal à 1 ) avec des losanges de côté 1 . L'ensemble des losanges réalisant le pavage est-il toujours unique ?
Domi -
Ce polygone est impossible à paver avec des losanges entiers de côtés parallèles aux côtés du grand polygone. Une condition nécessaire est que les côtés opposés aient même longueur entière (suivre une "brochette").
PS. Tu peux commencer par un hexagone régulier. Par exemple sur le dessin de ce message (il est un peu rogné en haut et en bas), compter les losanges bleus, jaunes et roses, pour t'apercevoir qu'il y en a autant de chaque sorte. Puis ensuite, avec un hexagone qui n'est plus régulier mais a des côtés opposés parallèles de même longueur (disons les longueurs $m$, $n$ et $p$ pour les trois paires de côtés opposés), compter combien il y a de losanges de chaque sorte dans n'importe quel pavage. -
Oui , il faut que les côtés parallèles soient de même longueur .
Domi -
Bonjour,
Continuons à "expliquer" les choses à un ordinateur pour voir ce qui pourrait se cacher dans les coins.
Partons du code : 2,1,2,3,4,2,3,1,2,1. Ses éléments vont de $1$ à 4, il y a $10$ "lettres". On remarque que $4=n-1$, $10=n\left(n-1\right)/2$ pour $n=5$ Choisissons une base de $n+1$ points désignés ci-dessous par $A0,A1,A2,A3,A4,A5$. Si nous rencontrons la lettre $k$ dans le code, nous plaçons un nouveau nom dans la colonne $Ak$, et nous le définissons le point correspondant par "new=gauche - haut + droite". Cela définit aussi un nouveau losange par [gauche, haut, droite, new]. Puis on met la ligne à jour, remplaçant le point médian par le point nouveau. Et on itère. Cela donne:
On remarquera que le dernier nom attribué dans la colonne $Ak$ est $A\left(2n-k\right)$. A partir d'une base de $b=n+1$ points, nous avons construit $q$ nouveaux points et $q$ losanges. Cela fait donc $n+1+q$ points en tout, $q+1$ faces, et $\left(4q+2n\right)/2$ arêtes, vérifiant la relation d'Euler.
Si nous interprétons les points de base par $u^{0},u^{1},u^{2},u^{3},u^{4},u^{5}$ avec $u=\exp\left(i\pi/5\right)$, nous obtenons la figure ci-dessous (certains semblent préférer avoir $A_{0}A_{1}$ en haut, il suffit de faire tourner la table):
A gauche, il y a les numéros des losanges, à droite les noms des points et les brochettes (cela a déjà été décrit, on ne recommence pas). Si nous interprétons les points de base par $v^{0},v^{1},v^{1},v^{2},v^{3},v^{4}$ avec $v=\exp\left(i\pi/4\right)$, la même procédure d'affichage donne le dessin ci-dessous à droite. La procédure polygonplot appliquée à un losange de la brochette n° 2 donne des traits qui viennent se confondre avec les arêtes des losanges visibles.
Bien entendu, l'algorithme de décodage peut être utilisé pour coder un pavage donné. Par exemple, oublions les losanges de la brochette n°2, et identifions les bords de la coupure. C'est à dire substituons A1 = A2, B = A3, C = D, F = E, A7 = A6 dans les définitions des 21-6=15 losanges restants. Partons d'une ligne de base, par exemple $A0,A2,A3,A4,A5$.
On cherche un losange dont trois sommets sont sur la ligne de base. Ici, le losange A0,A2,A3,D. La place du sommet médian sur la ligne de base fournit le code. Puis on remplace le point médian par le quatrième point. Et on itère.
Les éléments en couleur ne font pas partie du codage (ils sont là pour comparer avec le tableau précédent). Le résultat est 1,2,3,1,2,1.
Le codage sous forme de tresse définit les sommets comme combinaisons linéaires à coefficients entiers des sommets de la ligne de base. A part le fait que ligne de base + diamètre délimite un convexe, il ne semble pas y avoir d'autres contraintes sur cette ligne brisée. Mais cela revient à partir d'un pavage avec $n(n-1)/2$ losanges et cela ne résoud (du verbe résoutre) toujours pas la question de peut-on avoir (pour un demi-bord convexe non régulier) des brochettes qui se recoupent ?
Cordialement, Pierre. -
Chacun suit son chemin :-D
Même si ça n'ajoute rien au comptage des pavages possibles , on peut remarquer que le problème s'inscrit dans le cadre plus général d'un polygone à côtés entiers avec un centre de symétrie .
Domi -
Bonjour et merci à tous,
la succession de "trivialités" que GBMZ a eu l'amicale patience de m'écrire m'a aidé à mieux comprendre. J'ai cherché un meilleur codage (i.e. consommant moins de caractères typographiques) que le sien et j'ai "presque" trouvé, au sens que j'obtiens une "presque" injection.
J'explicite mon codage du sien:
A chaque code de GBZM, concaténation de parenthèses, j'associe la liste des longueurs de ses parenthèses.
Exemples:
à $ [3 ][23 ][123 ][0123 ]$ ( premier (et seul) code de niveau $20$) j'associe $1234$;
à $[3 ][2 ][123 ][2 ][0123]$ (deuxième code du niveau $19$) j'associe $11314$;
à $[3 ][ 23][12 ][0123 ][2 ]$ (troisième code du niveau $19$) j'associe $12241$;
à $[3 ][2 ][12 ][0123 ][2][ 1 ]$ (septième code du niveau $17$) j'associe $112411$;
Il se trouve, sauf erreur, que seuls $2$ de mes codes ( i.e. presqu'aucun ;-)) sont ambigus, à savoir
-le $13141$ qui désigne tout à la fois
$[3 ] [ 123 ] [1 ] [0123 ] [1 ] $ (le sixième du niveau $17$ et le seul à $5$ flips, le beau, quoi!) et $[ 2 ] [123 ] [2 ] [0123 ] [ 0 ] $(le deuxième du niveau $16$), et
-son symétrique (reverse) , le $14131$.
Comptabilité:
-La somme des chiffres de chacun de mes codes est $10$ et chaque chiffre est inférieur à $4$ (c'est pas un scoop),
-chaque code est une permutation de $1234$ ou $11224$ ou $11134$ ou $111124$. (Hasard ou pas: au moins trois chiffres différents par code);
-toutes les permutations ($24$) de $(1234)$ sont des codes, $14$ codes distincts sont des permutations de $11224$, $14$ autres disticts de $11134$ et enfin $8$ distincts de $111124$. On rajoute $2$ à cause de l'ambiguité (je ne sais plus où mettre le tréma) ci-dessus et on trouve nos $62$.
Amicalement
Paul -
Juste pour voir si Soland a bien suivi mon explication sur le codage, le niveau d'un code et les flips, une petite question :
Quel est le nombre minimum de flips qui permettent de passer de son magnifique pavage de 20-gone dessiné plus haut au non moins magnifique, mais plus classique, pavage dessiné ci-dessous ? -
Bonjour
A tous, et en particulier à GaBuZoMeu. Cela faciliterait la vie si vous arretiez de parler "du" pavage de Soland. A peu près tous les pavages de ce fil sont "de Soland", et il faut fouiller pour voir duquel vous parlez. Ci-dessous une nomenclature (le numéro est celui de la première image utilisée sur ce forum).
Et donc le 20gone précédent est le pavage de Soland n°68780.
Cordialement, Pierre -
Le graal:
Un codage qui ne dépend pas de la numérotation des brochettes... -
J'ai pu trouver pas mal de ressources sur le net (Kenyon, Elnitsky, Nakamoto & al), mais pour le moment je n'ai rien trouvé sur la distance d'un graphe des flips (et comment trouver deux pavages pour lesquels le nombre de flips nécessaires pour passer de l'un à l'autre est maximal ?). Si quelqu'un voit passer cela...
Fait "amusant" : dans divers articles, la nomenclature change nettement, par exemple ce qu'on appelle flip est une rotation pour Kenyon, un hexagon-flip pour Elnitsky, un Y-rotation chez Nakamoto, idem pour d'autres objets (brochettes, etc.). -
Le dessin d'hexagone avec plein de petits losanges qui terminait la page précédente est emprunté à Kenyon, si je me souviens bien.
-
Utilisant les sommets $A0\cdots A10$ (cf dessin ci-dessous) comme ligne de base, je trouve pour description des sommets du pavage de Soland n°68780:
B = A0+A2-A1, C = A3+A0-A1, D = -A9+A2-A1, E = A3-A9-A1, F = A4+A6-A5, G = A6-A5+A3, H = A6-A5+A3+A0-A1, J = A4-A5+A7, K = -A5+A7+A3, L = -A5+A7+A3+A0-A1, M = A7+A3+A0-A1-A6, N = A7+A3-A1-A6-A9, P = A7-A1-A6-A9+A2, B2 = A7-A6-A9, R = -A8+A7-A6, S = A3-A2+A7-A6-A9, T = -A0+A8-A9, U = A7-A0-A9, V = A4-A5+A7-A0-A9, W = A4-A5+A7+A0-A1, Z = A4-A5+A7-A1-A9, Q = -A5+A7-A1-A9+A3, B1 = -A1+A8-A9, C1 = -A1-A9+A7, D1 = -A2+A3-A4, E1 = -A1+A3-A4, F1 = A8-A9-A1+A3-A4, G1 = A8-A9+A4-A5-A1, H1 = A3+A8-A9-A5-A1, I1 = A3-A5-A1, J1 = -A2+A3-A5, K1 = A8-A9-A2+A3-A5, M1 = -A5-A8+A7, L1 = -A2+A3-A5-A8+A7, N1 = -A9-A2+A3-A5+A7, O1 = -A5+A7-A9
D'où la question: est-ce que les coefficients de la décomposition des sommets en combinaisons linéaires des sommets de la ligne de base (aka polynômes non réduits en la racine primitive $u$) sont toujours $1,0,+1$ ?
Comme codages, je trouve (version brute et version normalisée) les codes suivants en partant des sommets $00$, $01$, $15$ (en bas) : $$[0,1,4,5,3,4,2,3,4,2,8,7,6,5,6,7,8,4,3,2,1,2,0,1,2,3,2,6,5,6,7,4,6,5,
6,7,4,3,4,5,6,2,3,1,2]\\
[8,7,4,5,6,3,4,0,1,2,3,4,5,6,7,8,6,4,5,6,7,6,2,
3,2,1,2,0,1,2,3,4,5,6,7,4,2,3,4,5,6,2,3,1,2]$$
$$[3,4,2,3,7,8,6,7,5,6,7,5,
4,5,6,7,8,3,2,3,4,1,0,3,2,3,1,2,3,4,5,3,7,6,7,8,5,4,5,6,7,3,4,2,3]\\ [7,
8,6,7,3,4,5,6,7,5,2,3,4,5,6,7,8,7,3,2,3,4,3,1,2,3,0,1,2,3,4,5,6,7,8,5,
3,4,5,6,7,3,4,2,3]$$
$$[1,2,0,1,5,6,4,5,3,4,5,3,2,3,4,5,6,7,8,1,0,1,2,1,5,
6,7,5,4,5,6,3,5,4,5,6,3,2,3,4,5,1,2,0,1]\\
[5,6,4,5,1,2,3,4,5,3,0,1,2,3,
4,5,6,7,8,5,6,7,5,4,5,6,5,1,0,1,2,3,4,5,6,3,1,2,3,4,5,1,2,0,1]$$
Par ailleurs, supprimer la brochette $7$ donne (en partant du $00$ de mon dessin:
$$[1,2,0,1,5,6,4,5,3,4,5,3,2,3,4,5,6,7,8,1,0,1,2,1,5,6,7,5,4,5,6,3,5,4,
5,6,3,2,3,4,5,1,2,0,1]\\
[5,6,4,5,1,2,3,4,5,3,0,1,2,3,4,5,6,7,8,5,6,7,5,
4,5,6,5,1,0,1,2,3,4,5,6,3,1,2,3,4,5,1,2,0,1]$$
D'où les questions: comment calculer le code obtenu en décalant d'un cran le demi-cercle de base ? Ou bien le code obtenu en supprimant une brochette ?
Cordialement, Pierre -
Toujours à propos du pavage de Soland n°68780.
Si l'on regarde la suite des flips permettant d'amener la brochette 1 sur le bord externe, puis la brochette 2 au bord externe de l'espace restant, etc, on trouve une suite de 57 flips:
$$ \left[ \begin {array}{ccccccccccccccccccccccc} M&{\it B1}&C&E&{\it F1
}&B&D&P&N&Q&{\it H1}&{\it I1}&{\it E1}&S&{\it K1}&{\it N1}&{\it L1}&{
\it J1}&{\it D1}&{\it O1}&{\it M1}&{\it B2}&R\\ P&Q&
N&{\it K1}&{\it H1}&{\it I1}&S&{\it N1}&D&{\it O1}\\
P&N&E&S\\
H&{\it G1}&Z&W&Q&L&P\\
G&{\it C1}&V&Z&K&W\\
F&J&V \end {array} \right]
$$
Cordialement, Pierre -
@pldx : tu ne réponds pas exactement à la question que j'avais posée à Soland (problème de choix du point de démarrage). Tu remarqueras d'ailleurs que le 20-gone de Soland a un sommet tout en bas, et pas d'arête horizontale.
Le niveau du premier codage que tu donnes est 177. Le niveau le plus bas est 120. Donc 57 est bien le nombre minimal de flips pour arriver au dessin final juste au-dessus de ce message. -
Tout code normalisé pour le pavage d'un $2n$-gone contient une unique suite $[0:n-1]$, qui représente l'histoire du brin n° 0 (je numérote à partir de $0$, toujours pour faire plaisir à Soland). C''est assez facile à démontrer.
On décale de telle façon que le brin $0$ devienne le dernier. Il est facile de voir, en contemplant un diagramme de tresse, que ceci revient aux opérations suivant sur le code normalisé :comment calculer le code obtenu en décalant d'un cran le demi-cercle de base ?
1°) repérer la suite $[0:n-1]$,
2°) tout ce qui est avant, le baisser de $1$,
3°) tout ce qui est après, l'augmenter de $1$,
4°) remplacer les éléments de la suite $[0:n-1]$ par leurs compléments à $n-2$,
5°) normaliser.
Exemple : on part, dans un décagone, de
$$[0123][012][01][0]\;.$$
1er décalage $3210123121$, normalisé en
$$[3][2][1][0123][12][1]\;.$$
2e décalage $2103210232$, normalisé en
$$[23][12][0123][2][0]\;.$$
3e décalage $1201321031$, normalisé en
$$[123][0123][1][01]\;.$$
4e décalage $0123210212$, normalisé en
$$[0123][2][12][012]\;.$$
5e décalage $3210323123$, normalisé en
$$[3][23][123][0123]\;,$$
qui est l'image du premier par l'involution, normal puisque l'involution correspond au demi-tour. -
Il y a une symétrie facile à décrire sur les codes de pavages. C'est la symétrie par rapport à la droite joignant les sommets du $2n$-gone qui bordent ce que tu appelles le "demi-cercle de base", c.-à-d. la réunion des $n$ côtés adjacents qui sont le point de départ des brochettes numérotées (des brins de la tresse).
Cette symétrie consiste tout simplement à lire le code à l'envers et à le normaliser.
Exemple : si on part de
$$[0123][012][01][0]$$
on obtient en lisant à l'envers $0102103210$, et en normalisant
$$[0123][012][01][0]\;.$$
Ah ben oui, ce pavage est symétrique par rapport à l'axe susdit !
En composant (d'un côté ou de l'autre) avec le demi-tour (qui, rappelons-le, consiste à lire le code à l'envers, remplacer les chiffres par leurs compléments à $n-2$ et normaliser, on obtient bien sûr la symétrie par rapport à la droite qui joint le sommet milieu du "demi-cercle de base" au sommet opposé : elle consiste à remplacer les chiffres par leurs compléments à $n-2$ et normaliser. Partant toujours de
$$[0123][012][01][0]$$
on obtient $3210321323$ et en normalisant
$$[3][23][123][0123]\;.$$ -
Bonjour,
L'image http://www.les-mathematiques.net/phorum/addon.php?8,module=embed_images,file_id=68900 comporte une arête horizontale... parce qu'il s'agit du 18-gone obtenu en supprimant la brochette 7 du pavage de Soland n° 68780 (le point A6 a été identifié avec A7, et ne se voit plus sur le demi-cercle de base).
Pour ce qui est de réduire le pavage de Soland n° 68780 à la forme "radiale depuis un point du bord", on fait migrer les brochettes. Selon le choix de direction, les brochettes vont vers le demi-cercle $\left[A_{0}\cdots A_{-1}\cdots A_{n}\right]$ pour $\delta=A_{k}-A_{k-1}$ (fig. de gauche) ou bien vers le demi-cercle $\left[A_{0}\cdots A_{1}\cdots A_{n}\right]$ pour $\delta=A_{k-1}-A_{k}$ (fig. de droite).
Le codage de la figure de gauche a pour masse 240 (masse maximale), le codage de la figure de droite a pour masse 120 (masse minimale). Sous l'action de $\rho$, les codes changent, et leur masse aussi. Par symétrie rotatoire, la période est 4... et $\rho^{2}$ agit comme un demi-tour. Et donc le plus proche pavage "radial depuis un point du bord" est distant de 41 flips du pavage initial.
\[ \begin{array}{cccc} \# & flips\uparrow & masse & flips\downarrow\\ 0 & 63 & 177 & 57\\ 1 & 41 & 199 & 79\\ 2 & 57 & 183 & 63\\ 3 & 79 & 161 & 41 \end{array} \]
Cordialement, Pierre. -
Un pavage du 12-gone à regarder dans l'ordre
$$
\begin{matrix} 1&2\\4&3\\5&6 \end{matrix}
$$
Une transition horizontale montre l'effet d'un flip,
Après une transition verticale, on a choisi les hexagones à flipper. -
Hum, Soland, visiblement l'ordre
$$\begin{matrix} 1&2\\4&3\\5&6 \end{matrix}$$
n'est pas cohérent avec l'ordre de tes dessins et avec tes explications. Pour retrouver la cohérence, il faudrait intervertir les deux dessins de la deuxième ligne.
PS. Soland a corrigé. -
Sur la page mise en lien par Domi, M. Alan Schoen dit avoir trouvé 49 "rosettes" différentes pour un dodécagone.
Je trouve que les 908 pavages du dodécagone se répartissent en 43 orbites sous l'action du groupe diédral $D_{12}$. Les cardinaux de ces orbites sont :
24, 24, 4, 24, 24, 24, 12, 8, 12, 8, 24, 24, 24, 24, 24, 24, 24, 12, 24, 24, 12, 24, 24, 24, 12, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 12, 24, 24, 24, 24, 24, 24, 24
Voici une liste de représentants des orbites :[(4, 1, 2, 3, 4, 2, 3, 0, 1, 2, 3, 4, 0, 1, 2), (3, 2, 3, 4, 1, 2, 3, 0, 1, 2, 3, 4, 3, 1, 0), (1, 2, 0, 1, 2, 3, 4, 2, 3, 2, 0, 1, 2, 0, 1), (1, 0, 1, 2, 3, 4, 3, 1, 2, 3, 1, 2, 0, 1, 2), (3, 4, 1, 2, 3, 4, 2, 1, 2, 3, 0, 1, 2, 3, 4), (3, 2, 3, 4, 1, 2, 3, 2, 0, 1, 2, 3, 4, 3, 0), (4, 3, 2, 1, 2, 3, 4, 2, 3, 2, 0, 1, 2, 3, 4), (1, 2, 3, 1, 0, 1, 2, 3, 4, 3, 1, 2, 1, 0, 1), (3, 1, 2, 3, 4, 1, 2, 3, 0, 1, 2, 3, 4, 1, 0), (1, 2, 3, 1, 2, 0, 1, 2, 3, 4, 3, 2, 1, 0, 1), (0, 1, 2, 3, 4, 1, 0, 1, 2, 3, 2, 1, 2, 0, 1), (0, 1, 2, 3, 4, 1, 2, 3, 0, 1, 2, 3, 0, 1, 0), (4, 2, 3, 4, 2, 0, 1, 2, 3, 4, 0, 1, 2, 3, 1), (3, 4, 2, 3, 2, 1, 2, 0, 1, 2, 3, 4, 2, 3, 2), (4, 3, 4, 2, 3, 1, 2, 3, 4, 3, 0, 1, 2, 3, 4), (4, 0, 1, 2, 3, 4, 1, 2, 1, 0, 1, 2, 3, 2, 1), (0, 1, 2, 3, 4, 3, 1, 2, 1, 0, 1, 2, 3, 2, 1), (4, 3, 2, 0, 1, 2, 3, 4, 0, 1, 2, 3, 2, 1, 2), (3, 2, 3, 4, 3, 2, 1, 2, 3, 4, 0, 1, 2, 3, 4), (3, 0, 1, 2, 3, 4, 3, 1, 2, 0, 1, 2, 3, 2, 0), (4, 2, 3, 4, 2, 1, 2, 0, 1, 2, 3, 4, 2, 3, 1), (1, 2, 3, 4, 2, 3, 1, 2, 0, 1, 2, 3, 4, 2, 0), (4, 3, 4, 2, 1, 0, 1, 2, 3, 4, 1, 2, 3, 1, 2), (2, 0, 1, 2, 3, 4, 2, 3, 2, 1, 2, 0, 1, 2, 3), (2, 3, 4, 1, 2, 3, 0, 1, 2, 3, 4, 3, 1, 0, 1), (4, 3, 2, 3, 4, 1, 0, 1, 2, 3, 4, 1, 2, 3, 1), (4, 3, 1, 2, 3, 4, 1, 2, 3, 2, 0, 1, 2, 3, 4), (2, 3, 1, 2, 0, 1, 2, 3, 4, 3, 2, 3, 0, 1, 0), (4, 3, 2, 3, 1, 0, 1, 2, 3, 4, 1, 2, 3, 2, 1), (2, 0, 1, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 2, 1), (3, 4, 3, 2, 3, 4, 1, 2, 0, 1, 2, 3, 4, 2, 3), (4, 1, 2, 3, 4, 1, 2, 0, 1, 2, 3, 4, 2, 0, 1), (1, 2, 3, 4, 0, 1, 2, 3, 4, 2, 1, 0, 1, 2, 1), (4, 2, 3, 4, 2, 3, 1, 2, 3, 4, 0, 1, 2, 3, 4), (2, 3, 4, 2, 0, 1, 2, 3, 4, 2, 0, 1, 2, 3, 0), (4, 2, 3, 1, 2, 1, 0, 1, 2, 3, 4, 3, 2, 3, 1), (3, 2, 1, 2, 0, 1, 2, 3, 4, 2, 3, 1, 2, 1, 0), (2, 1, 2, 3, 4, 3, 2, 3, 1, 2, 0, 1, 2, 3, 4), (3, 1, 2, 3, 4, 3, 0, 1, 2, 3, 4, 0, 1, 2, 0), (0, 1, 2, 3, 4, 2, 3, 2, 1, 2, 0, 1, 2, 3, 2), (1, 2, 3, 4, 1, 2, 3, 2, 0, 1, 2, 3, 4, 0, 1), (2, 3, 1, 2, 0, 1, 2, 3, 4, 2, 3, 2, 0, 1, 0), (3, 4, 2, 3, 2, 1, 0, 1, 2, 3, 4, 3, 1, 2, 3)]
À voir si c'est correct...
Ça ressemble bigrement à A090339 -
Bonsoir.
Voici les codes normalisés du 12gone 68974 introduit par Soland. Ces codes dépendent du choix du sommet par rapport auquel on démarre le demi-cercle de base.
\[ \begin{array}{rccrr} k & code & \mu & \uparrow & \downarrow\\ 0 & [2,3,0,1,2,3,4,0,1,2,3,2,1,0,1] & 25 & 5 & 15\\ 1 & [4,1,2,3,2,1,0,1,2,3,4,3,2,1,2] & 31 & 11 & 9\\ 2 & [3,4,0,1,2,3,4,1,2,3,0,1,2,3,0] & 29 & 9 & 11\\ 3 & [2,3,4,3,2,1,2,3,4,0,1,2,3,4,1] & 35 & 15 & 5\\ 4 & [1,2,3,2,1,0,1,2,3,4,3,2,1,2,0] & 27 & 7 & 13\\ 5 & [4,0,1,2,3,4,1,2,3,0,1,2,3,0,1] & 27 & 7 & 13\\ 6 & [3,4,3,2,1,2,3,4,0,1,2,3,4,1,2] & 35 & 15 & 5\\ 7 & [2,3,2,1,0,1,2,3,4,3,2,1,2,3,0] & 29 & 9 & 11\\ 8 & [4,1,2,3,4,1,2,3,0,1,2,3,4,0,1] & 31 & 11 & 9\\ 9 & [3,0,1,2,3,4,0,1,2,3,2,1,0,1,2] & 25 & 5 & 15\\ 10 & [4,2,3,2,1,0,1,2,3,4,3,2,1,2,3] & 33 & 13 & 7\\ 11 & [3,4,1,2,3,4,1,2,3,0,1,2,3,4,0] & 33 & 13 & 7 \end{array} \]
Par conséquent, cinq flips, pas mieux.
Cordialement, Pierre. -
@GBZM.
J'ai appliqué les algorithmes que tu as décrits (rotation et symétrie) aux 43 codes que tu as donnés. Cela donne effectivement les cardinaux indiqués pour chaque orbite... et leur somme fait 908. Comme il semble y avoir un certain consensus sur ce 908 (suite Sloane A006245) et que les algorithmes semblent être efficaces, cela semble contredire "Using a 'rhomb-shuffling' computer program, I once found forty-nine different rosettes for n = 6, but my program may have missed some" http://schoengeometry.com/b-fintil.html.
Cordialement, Pierre. -
Oui, c'est ce que je disais. En fait, j'ai d'abord établi la liste des 908 pavages (pas comme ce que j'avais expliqué pour les 62, mais par un procédé de récurrence qui insère des $0,1,\ldots,n-2$ dans des codes déjà construits pour des pavages de $2(n-1)$-gones). Ensuite, je les ai regroupés par orbites.
Un petit ennui, c'est que pour l'étape d'après ($14$-gone) je trouve $24\;218$ pavages au lieu des $24\;698$ de A006245. Mon algorithme d'insertion loupe vraisemblablement des situations qui se produisent pour des codes suffisamment longs. Il faudra que je revoie ça. -
Bonsoir.
En force brute. On part des 908 codes des 12gones. On insère le groupe $012345$ (en augmentant ce qui se trouve devant l'insertion). Il y a $15+1$ places pour cette insertion. Cela donne 14528 résultats. Il en faudrait 24698. Mais ce n'est pas grave. On applique le groupe diedral à chacun des 14528. En fait, on fait une copie de la liste, et on supprime les éléments obtenus par l'action diedrale. Quand on a vidé la liste de 14528, on se retrouve avec 922 orbites. Pour un total de 24698 éléments.
Evidemment, pour les 16gones on sait qu'il y a 1232944 codes pour (potentiellement) 38612 classes. Cela prendrait un peu plus de temps. 50 fois plus, c'est encore jouable. Pour les 18gones, 112.018.190 pavages cela fait 4535 fois plus que pour les 14gones. Rien que les écrire !
Cordialement, Pierre.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 8 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 16
+11 Invités