Petit jeujeu mathématique deviendra gros casse-tête

Page 3 sur 11 Précédent  1, 2, 3, 4 ... 9, 10, 11  Suivant

Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Levans le Mar 3 Mar 2015 - 20:36

Petitagore a écrit:Je suggérerais bien de prendre en compte (entre autres) le nombre de cases autour d'un sommet commun.

On peut partir de là, mais ce n'est pas suffisant. Les exemples avec peu de points ne sont pas très parlants, maison peut assez facilement construire des exemple ambigus.

Je pense qu'on pourra néanmoins s'accorder, dans un premier temps, sur cette condition suffisante d'égalité :
Si on peut déformer continuement une grille A en une grille B (en déplaçant les points de manière continue sans changer leurs connexions et sans se faire croiser deux arrêtes à aucun moment de la transformation) alors elles sont égales.

NB : le point formant les 4 coins ne peut évidemment pas bouger, et les points sur des bords doivent y rester
On peut noter que si on se cantonne à cette définition, alors les 3 grilles à 4 triangles sont différentes.

Il serait bon de réussi à mettre des termes mathématiques clairs sur la définition de l'égalité que l'on veut, si on veut traiter le problème rigoureusement. Wink

Stauk a écrit:Clairement, elle ne sont pas égales.
Il s'agissait surtout de montrer que la définition de l'égalité que l'on choisit est très importante, et qu'il est important de se mettre d'accord sur un expression rigoureuse de cette égalité. Wink
avatar
Levans
Rayures fidèles
Rayures fidèles

Messages : 144
Date d'inscription : 17/01/2015
Age : 25
Localisation : Région parisienne

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Stauk le Mar 3 Mar 2015 - 20:39

Levans a écrit:
NB : le point formant les 4 coins ne peut évidemment pas bouger, et les points sur des bords doivent y rester
On peut noter que si on se cantonne à cette définition, alors les 3 grilles à 4 triangles sont différentes.
Il serait bon de réussi à mettre des termes mathématiques clairs sur la définition de l'égalité que l'on veut, si on veut traiter le problème rigoureusement. Wink

En fait c'est un donut. Le carré qui englobe la grille, n'a que deux arrêtes (au lieu de 4 comme on pourrait le croire sur le dessin).
avatar
Stauk
Rayures flamboyantes
Rayures flamboyantes

Messages : 6462
Date d'inscription : 16/01/2015

http://www.staukwood.com/

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore le Mar 3 Mar 2015 - 20:46

Stauk a écrit:En fait c'est un donut.

Je sais que suis parfois aussi crétin qu'Homer Simpson, mais le terme un peu sérieux est tore.

J'ai raison, c'est un tore! Very Happy
avatar
Petitagore
Rayures flamboyantes
Rayures flamboyantes

Messages : 4009
Date d'inscription : 29/11/2011
Age : 58
Localisation : Ile-de-France

http://triancey.blogspot.com

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Levans le Mar 3 Mar 2015 - 21:02

Stauk a écrit:En fait c'est un donut. Le carré qui englobe la grille, n'a que deux arrêtes (au lieu de 4 comme on pourrait le croire sur le dessin).
Oui, oui, je n'ai jamais dit le contraire... Huh

Juste que l'on soit d'accord. je pense qu'on s'accorde pour dire que ces deux grilles sont différentes mêmes si elles ont les mêmes nombres de face touchant chaque sommet : (Erratum : il faut lire 9 et non 8 )



Reste à poser des mots mathématiques clairs là dessus

Par exemple :
- Si je prends une grille et la rotate d'un quart de tour, la nouvelle grille est-elle égale à la première ?
- Si je fais une symétrie par rapport à un des 4 axes du carré ?
avatar
Levans
Rayures fidèles
Rayures fidèles

Messages : 144
Date d'inscription : 17/01/2015
Age : 25
Localisation : Région parisienne

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Stauk le Mar 3 Mar 2015 - 22:00

Levans a écrit:
Stauk a écrit:En fait c'est un donut. Le carré qui englobe la grille, n'a que deux arrêtes (au lieu de 4 comme on pourrait le croire sur le dessin).
Oui, oui, je n'ai jamais dit le contraire... Huh
Juste que l'on soit d'accord. je pense qu'on s'accorde pour dire que ces deux grilles sont différentes mêmes si elles ont les mêmes nombres de face touchant chaque sommet : (Erratum : il faut lire 9 et non 8 )

En fait je sais pas comment tu obtiens 8. (ou 9, ou 13, ou n'importe quelle valeur ...). Techniquement y a qu'un seul sommet en fait, non ? Donc ça serait 13 ? C'est sûr que c'est plus simple à l'intérieur du carré ...



Levans a écrit:
Reste à poser des mots mathématiques clairs là dessus
Par exemple :
- Si je prends une grille et la rotate d'un quart de tour, la nouvelle grille est-elle égale à la première ?
- Si je fais une symétrie par rapport à un des 4 axes du carré ?

Ben ouais. Rotations okay. Symétries axiales okay. Symétries centrales aussi ?

J'ai beaucoup de mal à bien "comprendre" l'effet donut. (tore stu veux). Je dirais que deux grilles sont équivalentes, si d'une part chaque type de triangle est présent en quantité égale dans les deux grilles (deux triangles sont du même type, s'ils ont les même cardinalités à leur sommets (disons rangés par ordre décroissant au niveau des cardinalités pour rendre la comparaison plus aisée) et d'autres part, chaque couple de chemin minimaux (c'est à dire en traversant le moins de frontières possibles) entre deux triangles de type A et B existant sur une grille, existe aussi sur l'autre. (chai pas si chui bien clair). Ou le chemin est la donné des triplets de cardinalité des triangles traversés.

Exemple y a trois triangles 863 sur les schémas proposés.

Un seul 863 est connecté à 653. (appelons le Alphonse).
Pour que Alphonse rejoigne le 863 le plus proche il faut aller : 886 : 863 sur la grille de gauche.
Mais Alphonse : 863 directement sur la grille de droite.

Ergo les deux grilles sont différentes.
avatar
Stauk
Rayures flamboyantes
Rayures flamboyantes

Messages : 6462
Date d'inscription : 16/01/2015

http://www.staukwood.com/

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore le Mar 3 Mar 2015 - 23:47

Merci de toutes ces réflexions. J'ai beau m'intéresser au sujet depuis un bon moment, je pense que vous partez dans des directions où je me suis peu aventuré, c'est enrichissant.

Une remarque en passant: en général, autour d'un sommet d'une de mes grilles, il y a 5, 6 ou 7 cases (ou segments, c'est pareil); les valeurs comme 4 ou 8 sont beaucoup plus rares, les valeurs 3 et 9 ne se rencontrent presque jamais -- donc des exemples où on les fait apparaître sont un peu particuliers, pas vraiment représentatifs de mon petit jeujeu.

Je dis ça parce que si vous aboutissez à un nombre astronomique de grilles, mais en y incluant une ribambelle de grilles où il serait courant que les sommets voient converger 3 ou 9 segments (ou même davantage), ben ça ne correspondrait pas vraiment à ce que j'obtiens -- et donc le nombre astronomique que vous obtiendriez serait plus un maximum ultra-théorique qu'un minimum donnant un ordre de grandeur de ce qu'on peut obtenir en pratique. Si tout au contraire vous vous limitez à des sommets où ne convergent que 5, 6 ou 7 segments (je préfèrerais), là vous aboutirez à un nombre forcément inférieur à la diversité envisageable, et que je pourrai donc considérer comme un minimum, tant en théorie qu'en pratique. Pour moi ce serait une information plus précieuse, car je cherche à démontrer que la diversité de mes grilles est bel et bien gigantesque en pratique; j'aimerais pouvoir affirmer que le risque que je tombe deux fois sur la même grille avec des mots-graines différents peut être considéré comme tout à fait négligeable. Un maximum théorique m'intéresse nettement moins qu'un minimum pratique.

Mais je ne veux pas vous empêcher de réfléchir: c'est beau la science. Very Happy


Dernière édition par Petitagore le Mar 3 Mar 2015 - 23:54, édité 1 fois (Raison : meilleures formulations)
avatar
Petitagore
Rayures flamboyantes
Rayures flamboyantes

Messages : 4009
Date d'inscription : 29/11/2011
Age : 58
Localisation : Ile-de-France

http://triancey.blogspot.com

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore le Mer 4 Mar 2015 - 17:32

Il y a des grilles faciles, des grilles difficiles... et il y a aussi des grilles vexantes, qui récalcitrent indéfiniment, refusent de se laisser résoudre, alors même qu'elles tolèrent des tonnes de solutions. En voici une qui m'a particulièrement humilié: la grille "decembre".

Elle a l'air extrêmement banale... elle ne l'est pas tant que ça, car elle contient exclusivement des pentagones, des hexagones et des heptagones; aucun quadrilatère, aucun octogone, ça a vraiment l'air d'un cas d'école sur lequel les solutions doivent abonder. Et, de fait, elles abondent...

... sauf que pour des raisons qui m'échappent c'est toujours les solutions que j'envisage qui foirent! Du coup, mon propre solveur se donne la joie de m'humilier en me montrant que j'aurais pu essayer n'importe quoi d'autre que ce que j'ai envisagé, et que ça aurait marché...

Voici un inventaire (certainement très incomplet) des cavexes envisageables. Attention, ne faites pas comme moi, ne vous braquez pas sur le premier: c'est justement le seul qui paraît inutilisable -- et par un fait exprès, c'est justement la première idée qui m'est venue, et à laquelle bien entendu je me suis accroché comme un morbaque parce que parmi mes nombreuses qualités, j'ai celle d'être persévérant... y compris dans l'erreur.  Very Happy



A titre d'entraînement, vous pouvez essayer de redessiner ces cavexes (tous), puis essayer de les employer (sauf le premier!) pour résoudre la grille.

Je publierai les corrigés demain (s'il plaît à Dieu de me laisser le temps de le faire).
avatar
Petitagore
Rayures flamboyantes
Rayures flamboyantes

Messages : 4009
Date d'inscription : 29/11/2011
Age : 58
Localisation : Ile-de-France

http://triancey.blogspot.com

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore le Jeu 5 Mar 2015 - 10:20

Bon. Je rappelle que nous travaillons sur la grille "decembre", avec les images de cavexes publiées dans le post précédent.

Pour ceux qui ont manqué des épisodes, un cavexe est un ensemble de cases voisines (un coacervat) sur lequel il paraît envisageable de terminer la partie (car en toutes choses il faut considérer la fin): il y a dedans le polygone convexe qui va bien pour le coup final (en l'occurrence un heptagone, que je vous ai coloré en bleu pour que ce soit plus clair), et un certain nombre (trois ou quatre, en général) de triplets de cases susceptibles d'être pris "par trois" et donc coloriables en jaune. Surtout, ce cavexe encercle totalement le tore, l'expérience démontrant qu'en général (mais pas toujours, ce serait trop simple) il suffit de faire très attention à ne pas toucher le cavexe dans les premiers coups de la partie pour aboutir au score optimal visé.

Commençons par dessiner les cavexes; ça ne présente aucune vraie difficulté, mais ça vous entraînera à en imaginer vous-mêmes, vous verrez que ça n'est pas bien malin (du moins sur cette grille).

Premier cavexe de la figure (c'est, je le rappelle, la première idée qui me soit venue et également la plus mauvaise -- mais ça n'empêche pas de le dessiner: 11 12 19 4 18 (bleu), 15 21 14 (jaune).

Cavexe valide 0: 0 34 37 36 2 (bleu), 11 30 18 (jaune).

Cavexe valide 1: 3 4 18 11 12 (bleu), 15 37 29 30 (jaune).

Ah tiens, il y a une erreur dans ce cavexe (voir plus bas); elle est sans conséquence, mais saurez-vous la détecter?

Cavexe valide 2: 37 2 5 3 38 (bleu), 29 31 19 (jaune).

Cavexe valide 3: 34 0 37 35 2 (bleu), 11 9 22 (jaune).

Cavexe valide 4: 11 17 12 4 19 (bleu), 21 1 8 (jaune).

Cavexe valide 5: 7 27 14 13 8 (bleu), 25 28 41 (jaune).

Cavexe valide 6: 2 5 39 38 3 (bleu), 10 16 24 (jaune).

Cavexe valide 7: 29 17 18 16 24 (bleu), 10 37 2 (jaune).

Cavexe valide 8: 11 12 19 3 17 (bleu), 21 6 26 40 (jaune).

Enfantin, non?

Et maintenant les solutions intégrales sur la base de ces cavexes, c'est à peine plus difficile... avec un peu d'habitude Very Happy :

Avec le cavexe 0: 23 8 15 28 26 13 41 39 25 12 (hors du cavexe), 18 11 30 36 (dans le cavexe).

Remarque: Comme dans la plupart des solutions, le dernier coup, qui prend le polygone convexe final, est indifférent.

Avec le cavexe 1: 5 25 32 33 7 35 14 21 8 (hors du cavexe), 37 12 2 10 17 (dedans)... et cornegidouille, je m'étais gourré de polygone final dans mon schéma du post précédent (d'ailleurs ça m'avait titillé au moment de dessiner le cavexe, comme signalé plus haut); ben vous voyez, c'est pas grave, on s'en sort quand même; comme quoi ça n'est pas si malin que ça...

Avec le cavexe 2: 11 22 16 1 27 34 13 25 33 41 (hors du cavexe), 19 31 29 38 (dedans).

Avec le cavexe 3: 16 38 29 18 32 20 4 33 21 6 (hors du cavexe), 22 9 11 36 (dedans).

Avec le cavexe 4: 6 37 39 40 35 23 28 27 31 15 (hors du cavexe), 8 1 21 4 (dedans).

Avec le cavexe 5: 0 29 35 38 3 17 16 19 32 4 (hors du cavexe), 41 28 25 9 (dedans).

Avec le cavexe 6: euh... Bordel, je retrouve plus la soluce! Encore une idée à la con du solveur... Prenez patience, je vous la retrouverai (mais mes compliments à ceux qui la trouveront seuls).

Avec le cavexe 7: 25 5 32 33 7 35 14 21 12 8 (hors du cavexe), 2 10 37 29 (dedans).

Avec le cavexe 8: 24 2 38 32 23 28 0 15 9 (hors du cavexe), 40 26 6 21 4 (dedans).

Eh ben vous voyez, c'est pas si malin que ça...
avatar
Petitagore
Rayures flamboyantes
Rayures flamboyantes

Messages : 4009
Date d'inscription : 29/11/2011
Age : 58
Localisation : Ile-de-France

http://triancey.blogspot.com

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore le Jeu 5 Mar 2015 - 11:24

Ca y est, j'ai retrouvé la solution de la grille "decembre" avec le cavexe 6... et je l'ai retrouvée tout seul avec ma petite tête, en plus. La voici:

19 14 21 7 31 40 34 28 29 8 (hors du cavexe), 24 16 10 3 (dedans).

C'était pourtant simple. Very Happy
avatar
Petitagore
Rayures flamboyantes
Rayures flamboyantes

Messages : 4009
Date d'inscription : 29/11/2011
Age : 58
Localisation : Ile-de-France

http://triancey.blogspot.com

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Pieyre le Jeu 5 Mar 2015 - 23:55

Comme l'a fait remarquer Levans, on peut associer à toute grille trianceysque un graphe. Il est non planaire (puisqu'il se déploie sur un tore) mais localement planaire. Plus précisément, dans la mesure où sa nature non planaire correspond à un bord de la surface (par exemple les côtés du carré de la représentation plane), on doit pouvoir se restreindre pour nombre de propriétés à étudier le graphe planaire obtenu par coupure selon ce bord. En effet, de même que le bord d'une surface continue est de mesure nulle, la frontière d'une surface discrète contribue, pour certaines propriétés, d'une façon qui tend vers 0 quand la discrétisation devient plus précise.

On sait déjà que le nombre de triangles est le même sur les représentations planaire et torique.
Le nombre de sommets est plus important sur la représentation planaire, mais on sait lesquels il faut identifier pour obtenir le nombre correspondant dans la représentation torique. Et, plus le nombre de sommets intérieurs augmente, plus on peut considérer l'un comme une approximation de l'autre.
Pour le nombre d'arêtes, le cas est assez semblable. Pour un nombre important de triangles, il doit donc être de même ordre sur les deux représentations.

Reste le nombre de grilles planaires, qui doit être en rapport avec ce qu'il serait sur le tore, mais de façon peut-être un peu plus complexe. En effet il s'agit cette fois de juger de la configuration globale de la grille. Le nombre de grilles apparentes (sur le carré correspondant au jeu) est donc là aussi supérieur au nombre grilles réelles, mais, du fait des symétries possibles, on pourrait avoir à diviser le premier nombre par un certain facteur.

Concernant plus généralement le nombre de graphes connexes à n sommets, quelques recherches sommaires me conduisent à penser que ce nombre doit être une exponentielle de n. Mais il ne semble pas y avoir d'estimation précise. Ainsi, on notant p(n) le nombre de graphes planaires connexes à n sommets, je trouve que 1/n × log2 (p(n)) tend vers une certaine constante c (entre 3 et 6 – la valeur n'est pas fixée). Ce qui donnerait p(n) équivalent à 2^(cn) lorsque n tend vers l'infini. Par ailleurs, pour les premiers graphes de cette sorte (en commençant à zéro sommet), on obtiendrait le nombre exact de graphes : 1, 1, 1, 2, 6, 20, 99, 646, 5974, 71885...

Maintenant, cela concerne un nombre de graphes plus divers que ceux correspondant aux grilles de Petitagore, comme il l'a lui-même remarqué. C'est-à-dire qu'on obtient toujours une majoration et non une minoration. Dans la mesure où les restrictions imposées aux grilles convenables sont importantes (la distance bornée entre sommets, et surtout le fait que tout triangle doit en en toucher exactement trois autres), il pourrait y avoir une estimation plus précise, peut-être même faisant intervenir des structures mathématiques moins complexes que le cas général. À lire un peu sur le sujet, je ne crois pas qu'on pourra facilement s'en sortir. Mais rien n'est certain. Il faudrait y passer du temps.

Pieyre
Rayures vénérables
Rayures vénérables

Messages : 19817
Date d'inscription : 17/03/2012
Localisation : Quartier Latin

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore le Ven 6 Mar 2015 - 8:57

Merci, Pieyre, de ces explications, même si elles expriment mieux (en termes mathématiques) la complexité du problème qu'elles ne le résolvent...

A défaut d'une mesure exacte, j'ai envisagé de me contenter d'une estimation par extrapolation. Je m'explique. Avec, disons, douze cases, la variété des grilles est déjà grande, mais pas forcément incommensurable, et avec quatorze non plus. Je peux me contenter de faire apparaître des tonnes de grilles au hasard, les compter, et constater qu'avec 14 cases j'en obtiens... un certain nombre de fois plus qu'avec 12, après quoi yorapuka extrapoler la tendance jusqu'à 30, 40, 50 cases. Ca ne serait pas hyper-rigoureux, mais ça mènerait à un résultat qui ne serait pas archi-faux (et qui serait sans l'ombre d'un doute sous-estimé et non surestimé, donc exploitable pour affirmer l'existence d'une gigantesque variété).

Cela dit, il faudrait en effet (ça a été évoqué plus haut par Levans) que je parvienne à répondre par oui ou par non et sans erreur à la question "telle grille est-elle différente de telle autre", ce qui n'est pas évident, au moins compte tenu des symétries. D'un point de vue algorithmique, il me serait assez facile de faire l'inventaire des nombres de segments partant de chaque sommet, de classer tout ça pour chaque grille, et de conclure avec certitude, chaque fois que j'obtiens deux classements différents, que je suis en présence de deux grilles différentes; évidemment, ça me ferait sous-estimer considérablement la diversité des grilles, mais ça pourrait me permettre d'obtenir un nombre minimal de grilles différentes, et un taux d'accroissement minimal de la complexité chaque fois qu'on ajoute un sommet  -- donc j'aboutirais bien, en extrapolant ça, à une sous-estimation minimale, qui pour moi serait précieuse (y compris si elle était plusieurs milliards de fois inférieure à la quantité réelle).

C'est beaucoup de tintouin pour obtenir un résultat archi-sous-estimé... Mais je soupçonne que ça pourrait fournir des idées pour aboutir à une démarche plus rigoureuse.

En tout cas, là, tout de suite, j'avoue que j'ai un peu la flemme. Very Happy
avatar
Petitagore
Rayures flamboyantes
Rayures flamboyantes

Messages : 4009
Date d'inscription : 29/11/2011
Age : 58
Localisation : Ile-de-France

http://triancey.blogspot.com

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore le Ven 6 Mar 2015 - 9:11

Au fait, personne n'a trouvé ce qui foirait il y a trois posts dans ma façon de dessiner mon cavexe 1? Ce n'est pas très difficile à remarquer (et c'est en plus très pédagogique pour la résolution des grilles, raison pour laquelle je vous titille à ce sujet), mais c'est un peu plus difficile à exprimer en termes mathématiques rigoureux... même que je le ferai plus tard parce que là j'ai un train à prendre.
avatar
Petitagore
Rayures flamboyantes
Rayures flamboyantes

Messages : 4009
Date d'inscription : 29/11/2011
Age : 58
Localisation : Ile-de-France

http://triancey.blogspot.com

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore le Ven 6 Mar 2015 - 16:00

Personne ne répond à ma question sur le cavexe foireux de la grille "decembre"... C'est dommage car ça tend à faire penser que je ne suis pas parvenu à vous faire vraiment comprendre l'intérêt d'un cavexe bien formé pour la résolution d'une grille et j'en suis fort marri.

Bon, ben je vous explique, et pardon si j'ai l'air de me répéter un peu, mais c'est important.

Dessiner un cavexe, c'est fantasmer sur la fin de la résolution d'une grille. Les coups que l'on joue pour dessiner le cavexe sont voués à être rejoués en ordre inverse, à la fin de la résolution d'une grille. Il faut donc se limiter à construire le cavexe avec des coups "réversibles", qui conduiraient à prendre les mêmes groupes de trois cases dans un sens chronologique comme dans l'autre. Et cela implique qu'un bon "coup de cavexe" soit constitué de trois cases ayant toutes deux voisins à l'intérieur du cavexe, le troisième voisin étant à l'extérieur d'icelui.

Pour le dire autrement, il faut dessiner le cavexe comme une accumulation de bosses de trois cases, bombées avec un creux vers l'intérieur du cavexe, et surtout ne comportant jamais une pointe cornue sortant du cavexe avec deux côtés voisins de cases n'appartenant pas à celui-ci.

Ouais, c'est bien compliqué, ça sera plus clair si vous envisagez la chose visuellement. Retournez donc, siouplaît, sur la grille "decembre".

Je dessine le polygone final (un heptagone) en bleu en cliquant par exemple sur 16, 17, 30, 23 et 18. A y est, vous visualisez l'heptagone bleu?

Maintenant, si je clique 37, j'obtiens trois cases jaunes ayant toutes et chacune deux voisins dans le cavexe. Pour la case 36, ce sont les cases 29 et 37. Pour la case 38, ce sont 30 et 37, et pour la case 37, ce sont évidemment 36 et 38. Tous ces numéros désignent des cases faisant partie du cavexe.

Continuons. Si je clique 10, je prends trois cases colorées en jaune. La case 15 a deux voisins dans le cavexe (10 et 16), la case 11 a deux voisins dans le cavexe (10 et 17), et la case 10 a deux voisins dans le cavexe (15 et 11), donc tout va bien.

Terminons. Si je clique 2, je prends là encore trois cases colorées en jaune. La case 1 a deux voisins dans le cavexe (2 et 10), la case 3 a deux voisins dans le cavexe (11 et 2) et la case 2 a elle aussi deux voisins dans le cavexe vu qu'elle en a même trois (37, 1 et 3). Donc mon cavexe est valide, hallelujah.

Et si j'agrandis encore le cavexe (ce qui n'est pas nécessaire, mais permis), je peux cliquer sur 12, et j'obtiens trois nouvelles cases jaunes ayant chacune deux voisins dans le cavexe; pour 4, ce sont les cases 3 et 12; pour 19, ce sont les cases 18 et 12, et pour 12, ce sont les cases 4 et 19. Tout baigne.

Mais ça, c'est la solution -- valide -- que j'aurais dû vous indiquer. Or je vous en ai indiqué une autre, qui, elle, est erronée.

Je vous ai dit (par erreur) de colorer en bleu un autre heptagone que l'heptagone final, par 3, 4, 18, 11, 12. Jusque là, ça a l'air d'aller.

Puis je vous ai dit de cliquer 15. C'est valide, ça prend trois cases jaunes ayant toutes et chacune deux voisins dans le cavexe: 10 qui a pour voisins 15 et 11, 16 qui a pour voisins 15 et 17, et 15 qui a pour voisins 10 et 16. Jusque là, ça va donc encore.

Mais ensuite, je me suis trompé. Là, je vous ai dit de cliquer sur 37, ce qui certes prend trois cases jaunes (37, 1 et 2), mais il y a un mais. La case 1 a bien deux voisins dans le cavexe (10 et 2), 2 a bien deux voisins dans le cavexe (1 et 3), mais 37 n'a qu'un voisin (la case 2) dans le cavexe, contre deux voisins hors du cavexe (36 et 38).

Et là, c'est raté. Si on rejoue cette séquence à l'envers, 36 et 38, qui sont hors du cavexe et donc censées être déjà prises à ce stade du récit, auront forcément déjà coloré la case 37. Donc nous sommes en présence d'un cavexe mal pensé.

Je sais, dit comme ça, ça a pas l'air simple... mais en fait, il suffit de se rendre compte que la case 37 a l'air d'une corne isolée sortant du cavexe, au lieu d'appartenir à une bosse de trois cases s'ajoutant à un cavexe qui garde un sympathique aspect gonflé et rondouillard. Visuellement, ça se voit au premier coup d'oeil, et l'abondant baratin logique que je viens de vous débiter est complètement superflu pour un joueur entraîné qui a appris à reconnaître la forme rondouillarde d'un cavexe en formation, et la forme cornue et diabolique d'un cavexe foireux.

Le diable est dans les détails... et dans les cornes du cavexe.


Dernière édition par Petitagore le Ven 6 Mar 2015 - 22:43, édité 1 fois (Raison : légère erreur d'observation de la grille)
avatar
Petitagore
Rayures flamboyantes
Rayures flamboyantes

Messages : 4009
Date d'inscription : 29/11/2011
Age : 58
Localisation : Ile-de-France

http://triancey.blogspot.com

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore le Sam 7 Mar 2015 - 9:22

Bon. M'inspirant des travaux et des schémas de Levans (merci à lui), je poursuis sur mon idée de noter de façon concise mais relativement complète les propriétés d'une grille, de façon à pouvoir affirmer sans risque d'erreur que deux grilles sont différentes, en dépit des symétries et des bizarreries d'affichage qu'entraîne la nature torique du bazar.



Voici une grille de 18 cases et donc 9 sommets (sur un tore, les cases sont bougrement plus faciles à compter que les sommets). Sauf erreur ou omission, un de ces sommets (en bas à droite) est au centre d'un quadrilatère, deux sont au centre d'un pentagone, quatre sont au centre d'un hexagone et deux d'un octogone (1 + 2 + 4 + 2 = 9, le compte est bon).

On pourrait noter ça de façon concise:
9
4 : 1
5 : 2
6 : 4
8 : 2

avec bien sûr un classement rigoureux du nombre de cases autour d'un sommet (ici, en ordre croissant).

Et de façon encore plus concise (pour faciliter les traitements informatiques, par exemple avec le programme sort d'Unix pour ceux qui connaissent): 9;4:1;5:2;6:4;8:2. C'est pas super-lisible pour un humain, mais un ordinateur s'en sort très bien, arrive sans problème à classer des inventaires de descriptifs de ce type et du coup, quand deux grilles auront des descriptifs différents, on pourra assurer sans l'ombre d'un doute qu'elles sont différentes.

L'inverse n'est pas vrai, mais c'est un début.

Je poste déjà ça, et je reviens ensuite avec un perfectionnement.
avatar
Petitagore
Rayures flamboyantes
Rayures flamboyantes

Messages : 4009
Date d'inscription : 29/11/2011
Age : 58
Localisation : Ile-de-France

http://triancey.blogspot.com

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore le Sam 7 Mar 2015 - 9:43

Dans la notation que je viens de définir, plusieurs grilles très différentes peuvent avoir le même descriptif. Avec neuf sommets, ça permettrait déjà de faire un peu le tri, mais quand on va atteindre la vingtaine ce sera nettement insuffisant. Je propose donc un perfectionnement (une chinoiserie, même, car ça devient assez complexe -- mais toujours gérable par un programme comme le sort d'Unix): noter non seulement le nombre de cases autour de chaque sommet, mais aussi le nombre de cases autour des sommets à la périphérie du polygone convexe ayant le sommet pour centre.

Ouh la, que ce que je dis est compliqué. Reprenez la figure du post précédent, regardez le quadrilatère en bas à droite. Autour du sommet central marqué du chiffre 4, il y a deux sommets marqués du chiffre 6 et deux du chiffre 8. Je propose qu'au lieu de noter juste 4, on détaille un peu: 4 (6 : 2; 8 : 2).

Je sais, ça ne lève pas toutes les confusions. Sur l'exemple dont je vous parle, si on fait le tour des sommets du périmètre, on lit dans l'ordre 6 - 8 - 6 - 8, mais ça pourrait aussi être 6 - 6 - 8 - 8 et dans ce cas on aurait de toute évidence deux quadrilatères différents. Je pense quand même que si on applique ce mode de notation pour l'ensemble de la grille, jusqu'à une vingtaine de cases il sera vraiment bien rare que deux grilles différentes aient exactement parfaitement le même descriptif -- donc compter les descriptifs différents permettra de se faire une idée très légèrement sous-estimée (je préfère ça que le contraire) de la diversité des grilles.

Bon, maintenant, je dois admettre que la notation ne sera pas super-concise ni super-lisible, puisqu'elle donnera quelque chose du genre (l'exemple est réel et correspond à la figure du post précédent -- sauf erreur ou omission):

neuf sommets: 9;
sommets de quadrilatères: 4(6:2;8:2):1;
sommets de pentagones: 5(5:1;6:3;8:1):2;
sommets d'hexagones:6(4:1;5:1;6:1;8:3):1;6(5:2;6:2;8:2):3;
sommets d'octogones: 8(4:1;5:1;6:5;8:1):2.

Surtout n'hésitez pas à me signaler une erreur... Very Happy

Et donc, à l'usage du sort d'Unix, ça deviendrait un truc super-simple d'un point de vue informatique (non, je blague pas, c'est simple et à lire et à écrire... quand le boulot est fait par un programme informatique):

9;4(6:2;8:2):1;5(5:1;6:3;8:1):2;6(4:1;5:1;6:1;8:3):1;6(5:2;6:2;8:2):3;8(4:1;5:1;6:5;8:1):2

Sans qu'il soit tout à fait exclu que deux grilles différentes aient le même descriptif, je pense qu'on peut dire raisonnablement que jusqu'à une vingtaine de sommets ça ne sera quand même pas très fréquent en proportion. Un descriptif permettra donc d'identifier une grille avec un peu le même taux d'erreur qu'un ADN permet d'identifier un criminel.

Des objections? Des questions? D'autres idées?

Quelqu'un a suivi? Very Happy

(ton désespéré) Au moins la démarche générale?


Dernière édition par Petitagore le Dim 8 Mar 2015 - 8:24, édité 2 fois (Raison : faute de frappe)
avatar
Petitagore
Rayures flamboyantes
Rayures flamboyantes

Messages : 4009
Date d'inscription : 29/11/2011
Age : 58
Localisation : Ile-de-France

http://triancey.blogspot.com

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Pieyre le Sam 7 Mar 2015 - 11:54

Je pense que c'est une voie où il sera plus facile de trouver une minoration en effet (même si une description théorique précise du graphe torique correspondrait peut-être à un cas déjà traité dans la littérature).

J'avais pensé à une façon un peu différente, mais en m'inspirant aussi d'une description des grilles. J'envisageai de partir d'une grille régulière de triangles reliés par six angles, c'est-à-dire correspondant à un pavage par des hexagones dans la représentation duale, que j'adopte par la suite pour exprimer les choses plus facilement.

À partir de ce pavage hexagonal, qui correspond déjà à une grille possible, on peut se demander de combien de façon le transformer pour obtenir d'autres grilles, et cela en modifiant juste quelques hexagones.

Par exemple, si l'on transforme un hexagone en pentagone, cela peut se répercuter juste sur un autre hexagone relié au premier par un côté, qui deviendra lui-même un pentagone, le reste de la structure restant inchangée. Combien de grille peuvent comporter un tel double pentagone ? Eh bien une seule, par translation ou rotation de la grille sur le tore. Mais, si l'on introduit un autre double pentagone un peu plus loin, on aura déjà toute une série de grilles : il suffit de compter de combien de façons deux doubles pentagones peuvent être diversement éloignés et diversement orientés l'un par rapport à l'autre.

De même on peut transformer un hexagone en carré, avec deux hexagones voisins qui deviennent des pentagones, et établir un comptage du nombre de grilles possible en disposant deux figures de ce genre sur le pavage.

Et puis on peut associer les deux motifs : double pentagone et carré + double pentagone, pour en obtenir d'autres.

Il s'agirait d'établir une liste des modifications locales du pavage hexagonal qui pourrait être combinées de sorte que le nombre de leurs dispositions serait facile à établir.

Maintenant, pour une grille d'une vingtaine de triangles, je ne pense pas que l'on pourra dépasser l'ordre de la centaine. Ou alors il faudrait faire intervenir de nombreux assemblages de polygones, ce qui pourrait être fastidieux.

Pieyre
Rayures vénérables
Rayures vénérables

Messages : 19817
Date d'inscription : 17/03/2012
Localisation : Quartier Latin

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore le Sam 7 Mar 2015 - 12:35

C'est pas bête du tout, ça, Pieyre... Very Happy

Mais immédiatement je me demande à quoi pourrait ressembler un assemblage d'hexagones représenté sur un schéma carré (ne coupant évidemment pas une case triangulaire de part et d'autre des contours du carré, sinon ça ne ressemblerait plus à mes grilles). Ca n'est sûrement pas impossible (quitte à déformer pas mal les hexagones à proximité des bords et des coins du carré), mais je n'arrive pas à me le figurer -- or le faire m'aiderait à réfléchir.

Donc... j'y réfléchis! Very Happy
avatar
Petitagore
Rayures flamboyantes
Rayures flamboyantes

Messages : 4009
Date d'inscription : 29/11/2011
Age : 58
Localisation : Ile-de-France

http://triancey.blogspot.com

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Pieyre le Sam 7 Mar 2015 - 13:36

Dans ton maillage par des triangles, il était nécessaire, pour des raisons pratiques, et heureusement possible, qu'ils entrent sans être coupés dans le schéma carré. Mais, dans la représentation duale, les polygones de Voronoï ne peuvent pas respecter la même contrainte.

Peut-être pourrais-tu dessiner cette représentation duale sur tes grilles. Il suffit de relier les centres de gravité de tous les triangles qui se touchent par un côté (et tenir compte des triangles ayant un côté sur l'un des bords du carré, en traçant un segment horizontal ou vertical vers le bord). Je crois que cela peut aider à se représenter la structure d'une grille. Déjà il y a moitié moins de polygones que de triangles, et puis leur diversité de forme permet sans doute de se représenter mieux en quoi deux grilles sont ou non équivalentes.

Pieyre
Rayures vénérables
Rayures vénérables

Messages : 19817
Date d'inscription : 17/03/2012
Localisation : Quartier Latin

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore le Sam 7 Mar 2015 - 18:59

Bon, je ne sais pas si ça fera beaucoup avancer le schmilblick, mais je suis parvenu à dessiner un réseau hexagonal sur la représentation carrée d'un tore. Bel effort (c'était prise de tête, ce truc...).



Et maintenant que j'arrive à le concevoir, je n'aurais pas forcément beaucoup de difficultés à en faire une grille clicable, histoire de l'étudier plus commodément. Je vous tiendrai au courant si j'y arrive. Very Happy


Dernière édition par Petitagore le Sam 7 Mar 2015 - 22:54, édité 1 fois (Raison : pétouille orthographique)
avatar
Petitagore
Rayures flamboyantes
Rayures flamboyantes

Messages : 4009
Date d'inscription : 29/11/2011
Age : 58
Localisation : Ile-de-France

http://triancey.blogspot.com

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Pieyre le Sam 7 Mar 2015 - 19:17

Tes hexagones sont disposés de façon oblique. Il y a aussi une configuration tu aurais deux hexagones de côtés égaux au même niveau vertical.
Enfin, quand je dis oblique, c'est par rapport à l'horizontale. Par rapport à la verticale, ils sont alignés.

On peut obtenir une telle configuration en traçant un réseau de triangles équilatéraux et en appliquant dessus une grille carrée passant par des sommets.

Pieyre
Rayures vénérables
Rayures vénérables

Messages : 19817
Date d'inscription : 17/03/2012
Localisation : Quartier Latin

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore le Sam 7 Mar 2015 - 19:23

Mais je suis vraiment une nouille, moi! Il y a une représentation beaucoup plus facile à comprendre:



... mais on n'a pas tout perdu, car ceci nous fournit un merveilleux exemple du fait que deux représentations graphiquement très différentes peuvent servir à décrire un seul et unique assemblage de polygones sur un tore. Je suis bien content d'avoir trouvé cet exemple, tiens.

Soit dit en passant, selon la logique que j'ai expliquée plus haut, cette grille serait notée 12;6(6:6):12 -- et ce dans les deux cas, bien évidemment.

Ce qui serait nettement plus clair, n'est-il pas vrai? Very Happy
avatar
Petitagore
Rayures flamboyantes
Rayures flamboyantes

Messages : 4009
Date d'inscription : 29/11/2011
Age : 58
Localisation : Ile-de-France

http://triancey.blogspot.com

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore le Sam 7 Mar 2015 - 19:40

Pieyre a écrit:On peut obtenir une telle configuration en traçant un réseau de triangles équilatéraux et en appliquant dessus une grille carrée passant par des sommets.

Je serais preneur d'un petit dessin. Twisted Evil
avatar
Petitagore
Rayures flamboyantes
Rayures flamboyantes

Messages : 4009
Date d'inscription : 29/11/2011
Age : 58
Localisation : Ile-de-France

http://triancey.blogspot.com

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Pieyre le Sam 7 Mar 2015 - 20:31

Voici ! tu m'excuseras de la mauvaise qualité, mais j'ai préféré faire ça avec mes petites mains.



Pieyre
Rayures vénérables
Rayures vénérables

Messages : 19817
Date d'inscription : 17/03/2012
Localisation : Quartier Latin

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore le Sam 7 Mar 2015 - 22:53

Oui, c'est concevable, mais ça oblige à répartir certaines cases de part et d'autre du tore -- ce qui empêche de considérer ta figure comme une grille Triancey orthodoxe. Razz

Par ailleurs, ta figure a une superficie de vingt cases (sauf erreur de ma part, le réseau hexagonal exige que le nombre de cases soit un multiple de six). Il faudrait abaisser le trait inférieur d'un demi-triangle équilatéral pour passer à une superficie de vingt-quatre cases et faire en sorte que les motifs se correspondent bien en haut et en bas. Mais on comprend l'idée.

N'empêche, pour les raisonnements que tu te proposais d'effectuer, je pense que ma deuxième figure, hyper-régulière, est très facile à exploiter et à comprendre.
avatar
Petitagore
Rayures flamboyantes
Rayures flamboyantes

Messages : 4009
Date d'inscription : 29/11/2011
Age : 58
Localisation : Ile-de-France

http://triancey.blogspot.com

Revenir en haut Aller en bas

Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Pieyre le Sam 7 Mar 2015 - 23:17

Moi aussi j'ai eu tendance à ne pas compter tous les triangles. Mais regarde bien : il y en a 24, et la grille est orthodoxe.

Par ailleurs, je ne prétendais pas imposer un modèle, mais indiquer une méthode simple pour obtenir une grille régulière. Et je reconnais que ta grille a l'avantage de présenter des triangles identiques, notamment de même aire, ce qui évite de se poser la question que tu as soulevée des triangles trop petits pour être acceptables.

Pendant que j'y suis, à ce sujet, j'ai l'impression que dans ta version commerciale, les triangles ne sont pas de même aire, justement. C'est-à-dire qu'y placer les pièces triangulaires bicolores, forcément des triangles équilatéraux, pourrait les recouvrir plus ou moins. N'y aurait-il pas une transformation simple de la grille, qui consisterait à déplacer juste un peu les sommets, de sorte que tous les triangles soient de même aire ?

... Je comprends un peu tardivement la référence à la superficie. Bon, alors j'ajoute que si la superficie est bien de 20 triangles équilatéraux, il me semble que cela importe peu. Il y a en a bien 24 en tout, certains entiers et certains demi-entiers. Mais c'est juste une question de découpage.
Ce qui est vrai c'est que, sur le tore, le fait de couper les triangles en deux fait que le maillage n'est pas régulier. Alors que le tien l'est. C'est d'ailleurs intéressant. La figure de référence, c'est le tore. On ne peut pas conserver toutes les propriétés de son maillage régulier sur le carré; aussi il faut choisir d'en sacrifier au moins une. J'ai sacrifié la régularité de certains triangles du bord; tu as sacrifié l'équilatéralité.

... J'ajoute encore une chose (j'ai l'esprit de l'escalier). Et si tu envisageais dans ta version commerciale une grille hexagonale ? C'est tout de même plus en rapport avec le triangle que ne l'est le carré... Alors il pourrait y avoir ou bien deux joueurs, ou bien quatre, ou bien six. Pour six, il suffirait de disposer de dés cubiques à six couleurs à la place des triangles bicolores. Pour quatre il est moins évident de trouver une pièce acceptable, dans la mesure où le tétraèdre ne peut reposer sur sa pointe pour montrer la couleur du joueur... Mais on doit pouvoir trouver une solution.

Pieyre
Rayures vénérables
Rayures vénérables

Messages : 19817
Date d'inscription : 17/03/2012
Localisation : Quartier Latin

Revenir en haut Aller en bas

Page 3 sur 11 Précédent  1, 2, 3, 4 ... 9, 10, 11  Suivant

Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum