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

loulou38 a écrit:Il y a un problème : quand les cases sont prises par trois, la figure jaune est un pentagone ...  

Plaisantin. Certes, quand l'hexagone touche un bord, il arrive que deux de ses côtés soient alignés sur le bord, ce qui donne à l'ensemble de six cases l'aspect d'un pentagone; mais là, on pinaille. S'il y a six triangles autour d'un sommet, j'appelle ça un hexagone quand bien même ça serait carré!

D'autre part, je suppose qu'on tient compte des raccords toriques, et donc il peut y avoir du jaune en deux morceaux ?

Oui, c'est permis. Cela dit, il n'est vraiment nécessaire d'en tenir compte que sur une des 34 grilles.

Pieyre a écrit:Je propose une conjecture : le nombre de triangles est toujours pair.

On peut en faire un théorème.  

Cela doit se démontrer facilement par récurrence, en envisageant les différents cas d'ajout d'un nouveau triangle : il faut commencer par un sommet, couper un côté, et rejoindre un ou plusieurs sommets, d'où un nombre pair de triangles supplémentaires.

Je me souviens d'avoir lu dans une rubrique de jeux un problème ainsi conçu: "Dans le village de Trifouilly-les-oies, tous les habitants ont trois amis. Démontrez que le nombre d'habitants de Trifouilly est pair." Je ne me souviens plus de la démonstration, seulement que je l'avais trouvée très élégante. Je ne vais pas la chercher maintenant, mais je crois qu'elle est quelque part dans la pile de bouquins à côté de ma cheville gauche.  

Si l'on considère la dualité entre ton maillage obtenu, ici par des triangles (partition de Delaunay) et le pavage associé (polygones de Voronoï), on obtient une autre conjecture : le nombre de pavés est moitié du nombre de triangles.
Cela doit se démontrer par une récurrence semblable.

Maintenant, à quoi ça peut servir ? Je ne sais pas.

Moi non plus, mais je trouve quand même ça fascinant!

Petitagore a écrit:Je me souviens d'avoir lu dans une rubrique de jeux un problème ainsi conçu: "Dans le village de Trifouilly-les-oies, tous les habitants ont trois amis. Démontrez que le nombre d'habitants de Trifouilly est pair." Je ne me souviens plus de la démonstration, seulement que je l'avais trouvé très élégante.

Là, tu me ramènes à une préoccupation que j'ai eue lors de mes chères études : pourquoi est-ce que je me suis aussi souvent lancé dans une solution technique alors qu'il existait une solution plus conceptuelle, c'est-à-dire plus élégante ?

Bon, dans ton problème, j'en tiens toujours pour ma récurrence.
Déjà, il y a un cas élémentaire où la contrainte est réalisée : le nombre d'habitants est quatre, donc pair, chacun étant ami des trois autres.

Ensuite, on suppose que cette contrainte est réalisée pour un nombre d'habitants pair. Et on tente d'introduire un nouvel habitant, qui devra être ami avec trois autres, disons a, b et c, quitte à eux de rompre une relation d'amitié qui existait jusque là.

Je trouve quatre cas, où la contrainte échoue :
— a, b et c n'avaient pas de relation d'amitié entre eux; ils rompent chacun avec un habitant; parmi ces trois-là, deux peuvent nouer une nouvelle relation d'amitié, mais le troisième se retrouve avec deux amis; ça ne marche donc pas;
— entre a, b et c, il y avait juste une relation d'amitié, disons entre a et b; si a et b rompent, ils conservent trois relations d'amitiés; mais c doit rompre avec un ami, qui lui reste avec deux amis, comme dans le cas précédent;
— entre a, b et c, il y avait deux relations d'amitié, disons entre a et b et entre a et c; a ne peut rompre ces deux relations pour son nouvel ami, sinon à n'avoir plus que deux amis; et donc c'est b ou c qui se retrouve dans le cas précédent;
— a, b et c étaient mutuellement amis; si a rompt sa relation avec b, il ne peut la rompre avec c; aussi c se retrouve encore dans le cas précédent.

Au contraire, si l'on introduit non pas un mais deux nouveaux habitants, là il y a une solution simple. On choisit a, b et c mutuellement amis, ils rompent leurs relations (chacun en a deux en moins) et ils établissent une relation avec les deux nouveaux (deux en plus).

Maintenant, je suis sûr que quelqu'un va nous trouver une démonstration plus élégante, et j'en serai mortifié !


Quelques minutes plus tard...
Argh ! J'ai trouvé... Supposons une relation d'amitié entre a et b comme une flèche de a vers b associée à une flèche de b vers a. Si tous les habitants ont trois amis, et qu'il y a n habitants, cela fait donc 3 × n flèches. Si n est impair, ce nombre est impair. Or les flèches correspondant aux relations d'amitiés étant réciproques sont forcément en nombre pair.

Pieyre a écrit:Là, tu me ramènes à une préoccupation que j'ai eue lors de mes chères études : pourquoi est-ce que je me suis aussi souvent lancé dans une solution technique alors qu'il existait une solution plus conceptuelle, c'est-à-dire plus élégante ?

Eh bien c'est exactement la problématique de mon casse-tête, comme nous allons bientôt le voir! Il a donc de grandes chances de te plaire.  

Bon, dans ton problème, j'en tiens toujours pour ma récurrence.

Je ne dis pas que tu as tort, mais moi aussi ça me rappelle mes cours de maths, ce moment douloureux où, comme disait Coluche, une fois que le prof avait fini sa réponse je ne comprenais même plus ma question...

Déjà, il y a un cas élémentaire où la contrainte est réalisée : le nombre d'habitants est quatre, donc pair, chacun étant ami des trois autres.

Jusque là, j'ai compris! Mais après, ça s'est salement gâté.  

Argh ! J'ai trouvé... Supposons une relation d'amitié entre a et b comme une flèche de a vers b associée à une flèche de b vers a. Si tous les habitants ont trois amis, et qu'il y a n habitants, cela fait donc 3 × n flèches. Si n est impair, ce nombre est impair. Or les flèches correspondant aux relations d'amitiés étant réciproques sont forcément en nombre pair.

Je vais aller boire un ou deux litres de café, parce que là, c'est tellement brillant que je ne pige rien...

Petitagore a écrit:

Argh ! J'ai trouvé... Supposons une relation d'amitié entre a et b comme une flèche de a vers b associée à une flèche de b vers a. Si tous les habitants ont trois amis, et qu'il y a n habitants, cela fait donc 3 × n flèches. Si n est impair, ce nombre est impair. Or les flèches correspondant aux relations d'amitiés étant réciproques sont forcément en nombre pair.

Je vais aller boire un ou deux litres de café, parce que là, c'est tellement brillant que je ne pige rien...

C'est nécessairement réciproque l'amitié ? Si on suppose que la relation peut être unilatérale, le fait que tout le monde ait trois amis implique t'il encore un nombre pair de personnes ? Ne peut t'on pas être ami avec soi même ?

Bon, je mets très partiellement fin à mon teasing éhonté. Le but à atteindre sur ces grilles-là (où les réactions en chaînes prenant trois cases les colorent en jaune, toutes les autres cases prises étant bleues), c'est d'atteindre sur chaque grille le maximum envisageable de cases jaunes. Et vous vous rendrez vite compte que c'est très difficile (mais pas impossible).

Et c'est quoi, "le maximum de cases jaunes"?

Je vous donne la réponse brute (au risque d'ailleurs de vous décourager, mais nous verrons qu'en dépit de la difficulté cet optimum théorique est bel et bien accessible à un humain... qui a vraiment compris comme Pieyre aime faire ):

Dans l'immense majorité des cas, l'optimum en cases jaunes est égal au nombre total de cases de la grille diminué de 7, 8 ou 9. Il y a des exceptions, mais dans l'immense majorité des cas on peut se rendre compte qu'on est en présence d'une exception (où il faut sacrifier 10 cases bleues, ou encore, beaucoup plus rare, où il suffit d'en sacrifier 6).

Déjà, comment sait-on si c'est 7, 8 ou 9? Ça, ce n'est vraiment pas très malin... et j'en profite aussitôt pour confesser que j'ai joué plusieurs mois à mon propre casse-tête (horriblement mal, donc) sans avoir même eu l'idée de me poser la question (non mais, quel nul...).

stauk a écrit:C'est nécessairement réciproque l'amitié ? Si on suppose que la relation peut être unilatérale, le fait que tout le monde ait trois amis implique t'il encore un nombre pair de personnes ? Ne peut t'on pas être ami avec soi même ?

Ici, c'est pas de la philo, c'est des maths, espèce de sale chahuteur. En mathématiques, l'amitié est réciproque ou n'est pas, et elle n'est pas réflexive.

(mais si tu veux vraiment faire de la philo, je te dirai qu'un des fondements de l'amitié est la complémentarité, et qu'on ne saurait être le complémentaire de soi-même)

En tout cas, merci de considérer cette question comme totalement hors sujet.

Supposons une relation d'amitié entre a et b comme une flèche de a vers b associée à une flèche de b vers a. Si tous les habitants ont trois amis, et qu'il y a n habitants, cela fait donc 3 × n flèches. Si n est impair, ce nombre est impair. Or les flèches correspondant aux relations d'amitiés étant réciproques sont forcément en nombre pair.

Ce qui m'embête avec ta proposition, c'est que tu sembles introduire la notion de "demi amitié" (une flèche), et je trouve ça un peu tordu, et pour tout dire ça me perturbe !

Une autre formulation serait d'introduire la notion d'amitié (qui implique nécessairement deux individus), et la notion du nombre d'amis d'un individu.
Alors si on parle de la somme du nombre d'amis des individus présents (Appelons là S), on retrouve la propriété que tu évoques.

Si n individus sont présents, et qu'aucun n'a d'amis, alors S vaut 0.
Pour chaque amitié qu'on ajoute alors S est incrémenté de 2. (Si on enlève une amitié, alors S est décrémenté de 2). Il n'y aucune autre façon de modifier S. Si maintenant on suppose que la somme S = 3*n (chaque individus a 3 amis), alors on sait que S est paire, puisque les variations de S ne se font que par cran de deux, et S ne peut donc qu'être paire avec une forme S= p * 2.   Et en effet comme tu l'as fait remarquer pour que 3*n soit pair, cela implique que n soit pair, puisque 3 n'est jamais un multiple de deux par lui même.

J'ai retrouvé mon bouquin (en fait, il était dans la caisse près de ma cheville droite). Il s'agit de "200 nouveaux problèmes du Monde" (le journal "le Monde"), par Elisabeth Busser et Gilles Cohen, aux éditions Pole, Paris, 2007.

Ce problème est paru dans "le Monde" le 8 juin 2004. Voici l'énoncé, page 95:

Elisabeth Busser et Gilles Cohen a écrit:La ville aux trois amis

Dans cette ville, chaque habitant a exactement trois amis, pas un de plus, pas un de moins.

Sauriez-vous montrer que cette ville a un nombre pair d'habitants?

La situation est-elle possible avec tout nombre pair d'habitants?

Mais je suppose que vous serez plus intéressés par la solution, p. 110:

Les mêmes a écrit:Soit N le nombre d'habitants de la ville. Imaginons un graphe où les noeuds sont les habitants, et où une arête joint deux habitants quand ils sont amis. Comptons le nombre A d'arêtes.

En multipliant le nombre trois d'arêtes qui partent de chaque noeud par le nombre N de noeuds, chaque arête est comptée deux fois.

Donc A = 3N / 2. Mais A est un entier, ce qui impose que N soit pair (note de Petitagore: ce qu'il fallait démontrer).

Voici un graphe montrant qu'avec un nombre pair d'habitants, la situation est toujours possible.



Il est évident que la ville en question, comme le fait justement remarquer Jean-Marc Merrien (44000 Nantes), doit avoir plus de deux habitants!

Et ça (sans vouloir te dénigrer, Pieyre), je le comprends.

Bon. Maintenant que nous sommes tous convaincus que le nombre de cases d'une grille Triancey est toujours pair (ce qui, à vrai dire, n'est d'aucune utilité pour résoudre ce casse-tête, mais c'est pas grave, c'est beau la science), je reviens sur mon affirmation de tout à l'heure:

Dans l'immense majorité des cas, l'optimum en cases jaunes est égal au nombre total de cases de la grille diminué de 7, 8 ou 9.

En fait, plutôt que 7, 8 ou 9, il faut comprendre: deux cases isolées plus un pentagone, un hexagone ou un heptagone (ce qui nous permet de comprendre pourquoi il n'est pas nécessaire d'avoir à sa disposition un programme solveur pour déterminer quel est l'optimum).

Un petit croquis valant toujours mieux qu'un long discours, voici quelques images de grilles résolues (les cases sacrifiées y sont colorées dans une autre couleur que le bleu, mais ça ne change évidemment rien). Je pense qu'avec ces exemples vous allez comprendre seuls... même que je vais laisser à nos matheux patentés la joie de l'expliquer eux-mêmes!

Eh bien quoi? Nos matheux patentés font défection?

C'est probablement dû au fait qu'ils ont des choses plus intéressantes à faire (en fait, je les comprends), mais comme j'ai moi-même subi d'horribles humiliations en cours de maths au lycée (sans être tout à fait nul, j'étais quelquefois noté sous la moyenne, voire très au-dessous), je vais perfidement supposer que c'est parce que l'élégance de la démonstration d'Elisabeth Busser et Gilles Cohen leur a fait craindre de se rendre ridicules en échafaudant des théories emberlificotées pour expliquer des choses qui tombent sous le sens.

Car en effet, mon affirmation que (j'insiste lourdement) l'optimum en cases jaunes est égal au nombre total de cases de la grille diminué de 7, 8 ou 9, ou plutôt diminué de deux cases plus un pentagone, un hexagone ou un heptagone... eh bien ça tombe sous le sens.

Ce qui n'empêche pas que j'ai moi-même mis plusieurs mois pour m'en apercevoir, et alors même que j'avais le concours de mon infaillible solveur de grilles (mis au point par mes petites cellules grises, quand même: si je suis un mathématicien assez nul, je me débrouille comme analyste-programmeur).

Pourquoi deux plus un pentagone, un hexagone ou un heptagone? Elémentaire, mon cher Watson. Testez un peu ce que je vais dire à partir des grilles disponibles, et vous verrez que c'est en fait assez évident.

Théorème du premier coup. Le premier clic qu'on fait sur une grille colore toujours une case et une seule, parce que... (bon, je vais faire semblant de l'expliquer sinon ça ne serait pas un théorème, mais ça tombe un peu sous le sens, non?) parce que pour déclencher une réaction en chaîne, il faut qu'une case se trouve avoir deux voisins déjà colorés, or après le premier clic, les cases vides ont toutes ou zéro ou un voisin, aucune ne saurait en avoir deux. Enfin bref. Le premier clic ne prend qu'une case, qu'il colore donc en bleu, c'est complètement évident.

Théorème du deuxième coup. De deux choses l'une: ou la deuxième case colorée déclenche une réaction en chaîne avec l'aide de la première, ou pas; dans ce dernier cas, par définition, nous avons donc deux cases isolées (les deux cases isolées qu'on voit parfaitement sur ma petite collection du post précédent); et s'il y a réaction en chaîne, cette réaction en chaîne ne saurait prendre qu'une case (située entre les deux cases cliquées), donc c'est un coup qui prend deux cases et non trois, donc ça ne colore pas en jaune, donc ça ne mène pas à un score optimal (et c'est donc de mauvaise stratégie, car au lieu de diminuer le nombre de cases "prenables en jaune" de deux comme dans le cas précédent, ça monte inutilement à trois).

Exception: Si la première case cliquée (colorée en bleu) est située dans un quadrilatère, les trois autres cases du quadrilatère peuvent être prises en un seul coup (et donc être colorées en jaune). Mais primo beaucoup de grilles ne comportent aucun quadrilatère, deuxio quand elles en comportent un, en général il n'est pas possible de continuer à colorer en jaune sur la base de ce quadrilatère. Je vous le démontrerai plus rigoureusement quand j'aurai le temps (ce qui sera délicat car là encore il y a de rares exceptions), mais il vous est facile de vous en convaincre expérimentalement.

Remarque. Si la première case cliquée est située dans un pentagone, il est possible (quoique rarement souhaitable) de jouer le deuxième coup sur une voisine de cette case située dans le même pentagone -- après quoi le troisième coup pourra prendre "par trois", en jaune, les trois cases restantes du pentagone. C'est possible mais il est rarement utile de le prendre en compte, sauf sur certaines grilles extrêmement particulières et rarissimes, sur lesquelles ce serait effectivement le seul moyen d'amorcer une séquence gagnante; mais je dis cela à l'intention des seuls hyper-spécialistes, les débutants que vous êtes encore peuvent donc allègrement oublier cette remarque.

Théorème du dernier coup. On ne peut jamais éviter que le dernier coup joué (quand la grille est déjà archi-remplie, peu importe que ce soit avec des cases jaunes ou bleues; faites l'essai! pour faire l'essai, peu importe la couleur des cases), dernier coup qui va donc achever de remplir la grille... on ne peut jamais éviter que ce dernier coup ne prenne un polygone convexe (un pentagone, un hexagone ou un heptagone, occasionnellement un quadrilatère ou un octogone), ou, pire encore, un couloir traversant toute la grille. Dans tous ces cas, le nombre de cases prises simultanément étant supérieur à 3, ces cases prises au dernier coup ne pourront pas abonder le score optimal... et on peut donc calculer le score optimal en soustrayant du nombre total de cases de la grille, outre les deux cases sacrifiées lors des deux premiers coups, le polygone convexe qu'on est sûr de devoir sacrifier au dernier coup.

Exception théorique: il est théoriquement possible de terminer de remplir une grille sur un coup gagnant si cette grille comporte un "trilatère": trois cases réunies autour d'un sommet commun, et formant donc à elles trois un triangle qui les englobe. Ce polygone convexe de trois cases peut donc, en théorie, être pris en jaune par un ultime coup gagnant. Seulement l'immense majorité des grilles ne comportent aucun "trilatère" de ce type (exemple d'une exception: les cases 6, 7 et 8 de cette grille)... et même quand il y en a un il n'est pas évident qu'il soit même envisageable de l'utiliser pour un score optimal -- mais ça je vous laisse découvrir pourquoi.

Et maintenant, je vous l'affirme avec la puissante autorité que me donnent les innombrables résultats obtenus avec mon solveur: entre les deux cases sacrifiées au début et le polygone convexe sacrifié à la fin (toutes cases colorées en bleu), il est pratiquement toujours possible de réussir une série ininterrompue de coups gagnants (les exceptions sont rarissimes, même que je me suis constitué un petit musée de ces grilles exceptionnelles tellement j'ai peur de ne jamais les revoir).

Voilà. Tout cela est bavard mais, en fait, tombe plus ou moins sous le sens.

Toujours personne pour m'expliquer comment on sait s'il faut jouer le dernier coup sur un pentagone, un hexagone ou un heptagone? (j'ai moi-même mis des mois à trouver la réponse à cette question, mais cela démontre à quel point je suis vraiment un très mauvais matheux)

Bon, ben visiblement personne ne trouve quoi répondre à ma question, qui n'est pourtant pas une question piège... Ça me rassérène un peu, car moi, quand j'ai trouvé la réponse au bout de plusieurs mois, je me suis senti un peu mortifié de n'y être pas arrivé bien avant.

Quel con, mais putain, quel con, mais c'est pas possible d'être aussi con, bon Dieu, quel couillon, quel âne, et ça se dit surdoué en plus, pauvre nouille...

Mon jeu (c'est bien moi qui en suis l'auteur) s'appelle "partrois". Il consiste à prendre les cases trois par trois. Il colorie en jaune les cases qu'on prend trois par trois. Donc? Donc? Donc?

Non? Toujours pas? Vous êtes conscients que vous êtes en train de vous montrer aussi crétins que moi (bon, nettement moins longtemps, mais quand même...)?

Eh bien quand on veut prendre un ensemble de cases trois par trois, il est peut-être intelligent de commencer par se demander si leur nombre est un multiple de trois, eh!

Eh oui. C'est pas plus malin que ça. Et j'ai mis plusieurs mois à en prendre conscience. Et non, je suis pas fier.

Or donc, quand vous cherchez à résoudre une grille de n cases, que vous avez pigé que vous deviez sacrifier deux cases au début et un polygone convexe à la fin, ben pour savoir de quel type de polygone il s'agit... il suffit de compter et de faire une division par trois.

J'ai N cases, j'en soustrais deux, reste N - 2. N - 2 est-il un multiple de trois? Si oui, il faudra que je termine sur un hexagone. Si N - 2 est un multiple de trois majoré de un, il faudra que je termine sur un heptagone. Si N - 2 est un multiple de 3 minoré de un, il faudra que je termine sur un pentagone. Voilà, c'est pas plus malin que ça.

Récapitulatif des scores optimaux les plus courants

Code:

Nb de   Score     Dernier      Cases
cases  optimal     coup        bleues
 36      27     heptagone    2 + 7 = 9
 38      30     hexagone     2 + 6 = 8
 40      33     pentagone    2 + 5 = 7
 42      33     heptagone    2 + 7 = 9
 44      36     hexagone     2 + 6 = 8
 46      39     pentagone    2 + 5 = 7

Et quand on a compris ça, ben... On n'a pas encore atteint le score optimal théorique, mais au moins on cesse de s'escrimer sur des hypothèses absurdes. Quand vous êtes en train de remplir la grille avec vos cases jaunes, si dans l'espace de cases noires qui reste il n'y a pas le polygone convexe qui va bien (voir ci-dessus)... ben c'est tout à fait inutile d'insister: vous n'atteindrez pas le score optimal parce que l'arithmétique, l'impitoyable arithmétique, ne vous le permettra pas.

Saleté d'arithmétique à la noix, toujours là pour vous emmerder même quand vous croyez être tranquillement en train de vous escrimer sur des problèmes purement logiques à base trigonométrique.

Et comme dirait Homer Simpson: D'oh!

Je n'ai pas beaucoup de feedback sur ce fil (en clair, je monologue), pourtant je vois bien d'après le compteur que j'ai toujours des lecteurs... N'hésitez pas à raconter votre vie, vos efforts infructueux, les scores plus ou moins insatisfaisants que vous rencontrez en essayant les grilles disponibles... Ça peut donner matière à des développements pédagogiques. Certes, par inexpérience, vous risquez de dire des choses qui se révéleront ensuite un peu naïves... mais vous ne serez jamais aussi ridicules que moi qui ai mis plusieurs mois à comprendre qu'une division par trois était pertinente dans un jeu où on prend les cases trois par trois, et dont en plus j'étais moi-même l'auteur.

En fait, ce fil de discussion est une manière de confession publique de ma sottise, en même temps qu'un éloge de cette bonne vieille méthode cartésienne: en appliquant méthodiquement les quatre règles de la raison du bon père Descartes, j'ai pu venir à bout du problème que je m'étais proposé. Et même si j'y suis parvenu d'une façon très lente et au départ très peu élégante... au bout du compte je me suis trouvé moins bête qu'au début et le processus qui s'est donc déroulé dans mon cerveau débile de surdoué est fort comparable à ce que sait faire la méthode scientifique même quand elle est appliquée par une espèce aussi vile et stupide que l'espèce humaine.

Trêve de philosophie à deux balles, je vous concocte quelques images pour vous montrer la résolution d'une grille (j'ai choisi la grille "janvier", qui est une des plus simples; vous pouvez vous y coltiner pendant que je termine mon polycopié), et ensuite je reviens. Entre-temps, n'hésitez pas à réagir, à poser des questions, à me montrer que vous êtes vivants et intéressés, quoi, merde.

Nota à l'usage de ceux qui relisent ce fil: c'est dans ce post fondamental, un peu plus loin, que j'ai introduit la très importante notion de cavexe, et par la même occasion le non moins important théorème de l'avant-dernier coup -- cherchez un peu plus bas l'intertitre vert portant ce nom.

Or donc, comme je le disais dans le post précédent, nous allons travailler sur la résolution de la grille "janvier" que je vous reproduis ci-dessous:



C'est une grille de 38 cases. Je ne le sais pas parce que je les ai comptées une par une, mais parce que je vois en bas à droite une case 37. C'est mon programme qui opère la numérotation, de gauche à droite et de haut en bas, et comme tout informaticien qui se respecte, je lui ai imposé de commencer la numérotation à 0... donc si le plus grand numéro est 37, ça veut dire qu'il y a 38 cases. Oui, d'accord, c'est pas super-clair, mais je ne l'ai pas fait pour le plaisir de vous confusionner, c'est juste la façon de faire des informaticiens, sale race à laquelle j'appartiens.

Or donc, il y a 38 cases. Si j'en sacrifie deux pour commencer la résolution de la grille, il en restera 36, qui est un multiple de trois. Donc je devrai terminer sur un hexagone (merci de vous reporter aux épisodes précédents de cette passionnante saga pour comprendre ce que je vous raconte).

Un hexagone. Où que c'est-il qu'il y a un hexagone? Tiens, ben j'en vois un beau, là, dans le coin inférieur gauche.



Si, si, je vous assure, c'est un hexagone. Ne me dites pas que vous ne lui voyez que cinq côtés, on s'en fout, pour ce jeu un polygone convexe est appelé un hexagone dès l'instant qu'il regroupe six cases triangulaires autour d'un sommet commun, or c'est le cas.

Et pourquoi l'ai-je entièrement représenté en bleu? Parce que c'est sur cet hexagone que j'ambitionne de terminer la résolution de la grille, et le coup final n'est jamais un coup gagnant (nous avons déjà vu cela sous le nom de théorème du dernier coup). Vous avez bien compris: je commence par la fin. En toutes choses il faut considérer la fin, dit le poète (La Fontaine, le Renard et le Bouc), et il a foutrement raison, le poète: au début de la résolution d'une grille, on fait un peu ce qu'on veut, c'est à la fin que c'est délicat.

Théorème de l'avant-dernier coup

Donc, commençons par la fin, et interrogeons-nous donc sur l'avant-dernier coup, celui qui précédera la prise de notre hexagone.

Cet avant-dernier coup, lui, devra être un coup gagnant, prenant trois cases, pas une de plus pas une de moins. Et il faudra que ces trois cases contribuent à encercler notre hexagone final. Donc cet avant-dernier coup se jouera sur un polygone convexe marié à notre hexagone final, c'est-à-dire ayant avec lui un certain nombre de cases en commun.

De combien, le certain nombre?

De deux, oui, c'est cela: il va falloir jouer l'avant-dernier coup sur un polygone convexe marié à l'hexagone final et marié avec lui... Or, si vous ne l'avez pas encore remarqué je vous le signale: sur les grilles Triancey, dans l'immense majorité des cas, quand deux polygones convexes ont des cases en commun, ils n'ont pas un nombre quelconque de cases en commun mais tout simplement deux.

In other words: l'avant-dernier coup de la partie (je vous rappelle que je suis en train de raisonner à l'envers) devra être joué sur un pentagone.

Eh bien, ça, vous pouvez le marquer sur vos cahiers et le souligner en rouge (mais moi je suis daltonien):

L'avant-dernier coup d'une partie à score optimal est toujours joué sur un pentagone.



Et l'avant-avant-dernier coup, alors, l'antépénultième comme que disent ceux qu'ils ont du vocabulaire? Ben lui aussi il devra être joué dans le voisinage... tiens, ben sur un pentagone aussi, tant qu'on y est.



Et le coup encore avant? Ben lui aussi dans le voisinage... mais non, pas sur la case 29: il s'agit de prendre les cases trois par trois, or cette belle coloration bleue nous renseigne sur le fait que ce serait une mauvaise idée que de viser les cases 22, 29 et 23 en oubliant l'existence de la case 36.



Allez, en tâtonnant un peu, voici donc, colorées très majoritairement en jaune et donc "par trois", l'ensemble de cases sur lequel je compte terminer la résolution de la grille (je vous rappelle que jusqu'ici j'ai raisonné à l'envers parce qu'en toutes choses il faut considérer la fin).

Un peu de vocabulaire: j'appelle cet ensemble de cases grossièrement patatoïde, et déjà assez massif pour encercler totalement le tore, un coacervat cavexe, voire un cavexe. Ce n'est pas pour le plaisir d'employer des termes pédants et absents du dictionnaire, c'est parce que cette notion est tellement essentielle pour la résolution des grilles qu'il faut un terme pour en parler. En gros, une grille est résolue aux trois quarts lorsqu'on est parvenu à dessiner un cavexe où tout est jaune sauf le polygone final.

C'est quoi un coacervat (ce mot, lui, existe dans les bons dictionnaires)? En gros, c'est une tache d'huile, un patatoïde, un blob. Le mot cavexe, lui, est un néologisme petitagoresque, et ça veut dire "un truc qui n'est à proprement parler ni concave ni convexe".



Bon. Regardez le bien, ce blob cavexe ci-dessus, photographiez-le mentalement, faites-en une copie d'écran si nécessaire. Car à partir de maintenant nous allons cesser de raconter l'histoire à l'envers à partir de la fin. Maintenant, le but du jeu est de remplir avec des cases colorées (et jaunes, autant que possible) toutes celles qui étaient noires sur l'image du cavexe.

Ou pour le dire autrement: nous avons défini une stratégie! Yeeessss!

Alors allons-y gaiement:



C'est cela, oui...



Pas mal...



Ach, scheisse, verflixt et cornegidouille, caramba encore raté. C'est pas grave, les touches de magnétoscope c'est pas fait pour les chiens...



Encore un effort...



A y est! On a coloré l'inverse du cavexe avec plein plein de jaune, c'est bon, c'est gagné, yapuka appliquer le plan génial élaboré quand on réfléchissait sur le cavexe. Allons-y.



C'est bon...



Oui, c'est bon, je sens que ça vient...



Ce coup-ci, j'y suis presque...



Allez, plus qu'un et c'est fini...



Yipppeeeeeeee!

Maman, maman! Viens voir! J'ai résolu ma première grille Triancey, je suis le meilleur!

J'essaie de résumer la situation telle que je la vois.

Tu considères un maillage par des triangles de la surface d'une partie connexe (en un seul morceau) et bornée (pas de morceau qui part à l'infini) de R³.
Pour une question de représentation en deux dimensions, tu as choisi un tore (ou plutôt tu es parti de la représentation classique avec des bords apparents d'une surface sans bord, qui se trouve être un tore, mais je considère les choses comme un matheux, tu m'en excuseras).
Est-ce que cela conditionne les problèmes que tu te poses ensuite, ou auraient-ils été les mêmes si tu avais choisi un volume sans trou, autrement dit une sphère ? C'est difficile à dire comme ça, mais il serait intéressant de se poser la question. Peut-on représenter en deux dimensions la surface d'une sphère maillée par des triangles ? On dispose de plusieurs représentations de la surface terrestre. Le problème, ce serait de bien visualiser où se recollent les triangles. À essayer, non ?

Alors tu définis un système de remplissage de la grille obtenue, où la coloration d'un triangle peut se répercuter automatiquement en la coloration d'autres triangles.
Cela permet d'envisager deux optimisations possible : soit colorer le minimum de triangles avant la fin du remplissage, soit en colorer le maximum. Enfin, il y a aussi d'autres possibilités : placer le plus de triangles non jointifs, le plus de triangles joints au plus par deux, par trois, etc., former telle figure isolée, plusieurs de ces figures non jointives, par exemple former un anneau, plusieurs anneaux, etc.
J'ai un peu réfléchi à la première possibilité, c'est-à-dire colorer le minimum de triangles. J'ai dans l'idée qu'il est utile de considérer pour un triangle donné l'ensemble des triangles qui ont un sommet commun avec lui, et de placer le suivant à l'extérieur de cette zone, mais la touchant. Enfin, je ne suis pas allé plus loin. Il faudrait pratiquer, et ce n'est pas simple avec deux navigateurs qui tournent sur une bécane qui rame déjà avec un seul...
D'ailleurs tu n'as pas indiqué me semble-t-il si tu avais fait des trouvailles à ce sujet...

Ensuite tu définis un autre système de remplissage de la grille, avec deux couleurs, ce qui donne une orientation toute différente au problème. Ce qui semble intéressant, c'est d'obtenir davantage de triangles d'une couleur que d'une autre (le plus de triangles jaunes, parce que le plus de bleus, ce soit être trivial : on doit pouvoir tout colorer en bleu, non ?) Y aurait-il d'autres possibilités ? Sans doute : obtenir le maximum de composantes connexes jaunes ou bleues par exemple, ou un pavage plus ou moins régulier de triangles jaunes et bleus, etc.
Là tu énonces une conjecture sur le nombre minimal de triangles bleus restant, basée notamment sur un critère de divisibilité par 3, et une méthode de résolution, dont je n'ai pas compris si elle était générale.

Bon, qu'est-ce que tu peux maintenant attendre d'un matheux ? S'il s'agit de démontrer un résultat sur un type de grille, il serait sans doute plus facile de considérer un problème plus général, selon l'ensemble des grilles où le problème peut se poser. De plus, il serait intéressant de raisonner sur des grilles particulières, comme des grilles minimales ou des grilles composées avec un maillage régulier (les triangles ayant pour sommet un point donné formant un hexagone). En effet, les mathématiciens apprécient particulièrement les cas limites quand il s'agit étudier un ensemble étendu de cas. Alors on pourrait considérer, après avoir résolu de façon complète ces cas limites, d'agrandir la grille ou d'introduire des imperfections (un quadrilatère, un pentagone, un heptagone... d'ailleurs jusqu'où peut-on aller dans les polygones à n côtés, – autant qu'on veut, non ?) et de voir comment cela modifie la méthode simple...

Voilà. Je n'apporte pas de réponse pour le moment. D'ailleurs je soupçonne qu'il faudrait que je me replonge dans un ouvrage de morphologie mathématique, et je n'en ai pas ouvert un depuis quinze ans ! Il faudra que je reparte des bases...

Pieyre a écrit:Pour une question de représentation en deux dimensions, tu as choisi un tore (ou plutôt tu es parti de la représentation classique avec des bords apparents d'une surface sans bord, qui se trouve être un tore, mais je considère les choses comme un matheux, tu m'en excuseras).
Est-ce que cela conditionne les problèmes que tu te poses ensuite, ou auraient-ils été les mêmes si tu avais choisi un volume sans trou, autrement dit une sphère ?

Je pense que -- au moins pour ma façon de jouer -- ça ne changerait rien d'être sur la surface d'une sphère plutôt que sur un tore; le défi intellectuel resterait le même, et les principes de résolution également (deux cases sacrifiées au début, polygone convexe sacrifié au dernier coup, nécessité d'élaborer un "cavexe" pour ne pas se perdre dans des hypothèses absurdes). En revanche, ça rendrait l'affichage nettement plus problématique. Bien sûr, de nos jours, un affichage en 3D avec des faces cachées est quelque chose de très courant -- mais il serait quand même difficile de réprésenter ça en Javascript, surtout si on espère faire tourner ça sur un petit téléphone mobile pas puissant. Or, pour moi, il s'agit d'un petit jeujeu voué à distraire le voyageur de banlieue qui s'ennuie dans son train (hypothèse réelle: ça m'arrive tout le temps -- et en effet, j'ai beaucoup joué à ce jeu dans le train sur mon téléphone mobile).

C'est difficile à dire comme ça, mais il serait intéressant de se poser la question. Peut-on représenter en deux dimensions la surface d'une sphère maillée par des triangles ? On dispose de plusieurs représentations de la surface terrestre. Le problème, ce serait de bien visualiser où se recollent les triangles. À essayer, non ?

De manière générale, oui. Pour ce jeu-là avec ces règles-là, à mon sens ça n'apporterait rien.

Alors tu définis un système de remplissage de la grille obtenue, où la coloration d'un triangle peut se répercuter automatiquement en la coloration d'autres triangles.

Pour cette variante-ci, la coloration n'est qu'une facilité d'affichage, la question cruciale ici est le nombre de cases prises simultanément, les deux couleurs ne servent qu'à rendre plus visibles certaines valeurs de ce nombre. En revanche -- mais c'est une autre histoire -- on peut aussi faire des choses assez rigolotes sur ce genre de grilles en voyant comment deux couleurs peuvent se partager la surface. C'est la base de la version "commerciale" (je veux dire: que je ne me suis pas encore résigné à ne pas vendre) de mon jeu, dont parle abondamment (quoique pas mathématiquement) mon site web. C'est intéressant aussi, mais c'est une autre histoire.

Cela permet d'envisager deux optimisations possible : soit colorer le minimum de triangles avant la fin du remplissage, soit en colorer le maximum. Enfin, il y a aussi d'autres possibilités : placer le plus de triangles non jointifs, le plus de triangles joints au plus par deux, par trois, etc., former telle figure isolée, plusieurs de ces figures non jointives, par exemple former un anneau, plusieurs anneaux, etc.
J'ai un peu réfléchi à la première possibilité, c'est-à-dire colorer le minimum de triangles. J'ai dans l'idée qu'il est utile de considérer pour un triangle donné l'ensemble des triangles qui ont un sommet commun avec lui, et de placer le suivant à l'extérieur de cette zone, mais la touchant. Enfin, je ne suis pas allé plus loin. Il faudrait pratiquer, et ce n'est pas simple avec deux navigateurs qui tournent sur une bécane qui rame déjà avec un seul...
D'ailleurs tu n'as pas indiqué me semble-t-il si tu avais fait des trouvailles à ce sujet...

J'y ai un peu réfléchi, oui, mais comme je l'ai dit plus haut je me suis fixé pour règle esthétique qu'il fallait que l'objectif à atteindre ne soit pas un optimum abstrait à déterminer au cas par cas, mais quelque chose d'assez simple pour être connu d'emblée, avant qu'on attaque le problème. "Le maximum de triangles non jointifs", à mon goût, ce n'est pas assez défini au départ. Avec ma règle, on sait d'emblée (en comptant un peu) s'il faut terminer sur un pentagone, un hexagone ou un heptagone. Donc, on sait où on va, et quand on arrive au bout, on sait si on a atteint l'objectif ou non; on n'a pas à se poser la question "même si ce que j'ai fait a l'air pas mal, est-ce que c'est vraiment l'optimum? est-ce que c'était vraiment difficile?"

Ensuite tu définis un autre système de remplissage de la grille, avec deux couleurs, ce qui donne une orientation toute différente au problème.

Ce n'était pas mon intention, et dans cette variante la couleur est tout à fait secondaire. Au lieu de colorer les cases en jaune quand on a un coup gagnant, j'aurais pu dessiner sur le côté un petit Mickey qui saute de joie chaque fois qu'on prend trois cases d'un coup, ou afficher un compteur qui incrémente le nombre de coups gagnants, avec des cases toutes de la même couleur, sans que ça change rien au défi intellectuel.

Ce qui semble intéressant, c'est d'obtenir davantage de triangles d'une couleur que d'une autre (le plus de triangles jaunes, parce que le plus de bleus, ce soit être trivial : on doit pouvoir tout colorer en bleu, non ?)

Bien sûr. C'est vraiment très facile, même en s'interdisant les retours en arrière (l'appui sur les "touches de magnétoscope"). Ou alors, il faudrait d'autres règles.

Y aurait-il d'autres possibilités ? Sans doute : obtenir le maximum de composantes connexes jaunes ou bleues par exemple, ou un pavage plus ou moins régulier de triangles jaunes et bleus, etc.

Ah, je n'y avais pas pensé. Mais à mon avis, si on cherchait quelque chose de régulier, il faudrait abandonner la disposition savamment bordélique de mes cases (à laquelle je tiens beaucoup   ) et se fixer ce genre de défis sur une grille hexagonale composée exclusivement de triangles équilatéraux: là, la recherche d'une diposition régulière aurait du sens.

Là tu énonces une conjecture sur le nombre minimal de triangles bleus restant, basée notamment sur un critère de divisibilité par 3, et une méthode de résolution, dont je n'ai pas compris si elle était générale.

Je pense qu'elle l'est -- même si on peut très occasionnellement rencontrer des exceptions, rarissimes avec des grilles aléatoires, mais qu'un matheux qui chercherait à le faire parviendrait sans doute à systématiser.

Bon, qu'est-ce que tu peux maintenant attendre d'un matheux ?

Oh, je n'avais pas d'autre vraie ambition que de l'amuser. Mon jeujeu est à mon sens un peu plus intello que le Sudoku, mais fondamentalement, il s'agit du même esprit: obliger les gens à se creuser la tête, et les remplir de joie quand ils sont parvenus à relever le défi.

C'est un jeu, quoi.   Mais tu as ma bénédiction si tu veux le modifier pour en faire un problème mathématique théorique.

Alors on pourrait considérer, après avoir résolu de façon complète ces cas limites, d'agrandir la grille ou d'introduire des imperfections (un quadrilatère, un pentagone, un heptagone... d'ailleurs jusqu'où peut-on aller dans les polygones à n côtés, – autant qu'on veut, non ?) et de voir comment cela modifie la méthode simple...

Je comprends que ça tente un matheux, mais ce n'est pas du tout ce que j'avais en tête. J'ai commencé à réfléchir à ces grilles sur la base de triangles "naturels", réunis en petit nombre autour d'un sommet. Par exemple, ceux qu'on obtiendrait dans une forêt de chênes si on s'amusait à tirer des ficelles du tronc d'un arbre vers les troncs des arbres qui l'entourent. Dans une forêt de chênes, à proximité immédiate d'un chêne, il n'y a pas "n" chênes: il y en a trois, quatre, cinq, six ou sept, très rarement d'autres valeurs (parce qu'alors ça ne serait plus une forêt de chênes, mais une clairière avec un arbre isolé en plein milieu). Les sommets de mes triangles sont saupoudrés sur la surface à des distances "raisonnables", celles (pour prendre un autre exemple) qu'adoptent spontanément les convives d'un cocktail quand ils se répandent dans une salle de réception: ils ne sont pas horriblement serrés ici et clairsemés là, ils se débrouillent spontanément pour se tenir à une distance moyenne qui varie dans d'assez faibles proportions. C'est exactement comme ça que je saupoudre les sommets des triangles dans mes grilles, et c'est la raison pour laquelle on n'y trouve jamais de polygones à 145 côtés, mais seulement des polygones raisonnables: des quadrilatères, des pentagones, des hexagones, des heptagones, très rarement des "trilatères" et des octogones, des ennéagones les jours de très grand vent mais jamais, jamais rien au-delà du décagone.

C'est pas des maths, ça, c'est la vraie vie!  

Voilà. Je n'apporte pas de réponse pour le moment. D'ailleurs je soupçonne qu'il faudrait que je me replonge dans un ouvrage de morphologie mathématique, et je n'en ai pas ouvert un depuis quinze ans ! Il faudra que je reparte des bases...

A toi de voir! C'est beau la science, mais y a pas que ça dans la vie non plus.

J'ai toujours un compteur qui s'incrémente et guère de feedback... D'où je me hasarderai à conclure que j'ai un paquet de lecteurs qui ont compris la beauté logique de mes grilles, mais qui n'osent pas avouer qu'ils se sentent un peu niais de ne pas arriver à atteindre l'optimum que je leur déclare toujours possible (toute la grille jaune, sauf deux cases isolées et un polygone convexe).

Il faut savoir que toutes les grilles ne présentent pas le même degré de difficulté. Moi, qui ai désormais beaucoup d'entraînement, j'arrive assez souvent à en résoudre une en moins d'une minute et pas plus de quarante clics (en comptant ceux sur les touches de magnétoscope); mais il y en a aussi qui continuent de me tenir tête au bout de vingt-cinq minutes et de 250 clics. Outre mes mois et même mes années de pratique de ce genre de problèmes (ça fait des années que je m'y essaye, mais seulement quelques mois que je commence à avoir le sentiment d'avoir acquis une certaine maîtrise), j'ai sur vous un gros avantage: mon solveur. Quand je me suis vraiment pris la tête trois quarts d'heure sur une grille et presque définitivement persuadé que j'étais un gros nul, je fais résoudre la grille par mon solveur, ce qui me convainc de deux choses: 1) je ne suis pas si nul que ça, vu que c'est quand même moi qui ai programmé le solveur, nananère; 2) la grille n'est pas insoluble, puisque le solveur a trouvé une solution (à vrai dire, si je le titille un peu, il n'est pas rare qu'il m'en trouve quatre ou cinq complètement différentes). Et ça me motive pour persévérer...

Par ailleurs, j'étudie la "stratégie" de mon solveur. Je mets stratégie entre guillemets, puisque le solveur n'utilise guère que la force brutale: des dizaines de milliers d'essais faits au hasard permettant d'en identifier un qui marche; la logique des Shadoks, quoi: comme il y a une chance sur mille que ça marche, hâtons-nous de foirer les 999 premiers essais. Mais il arrive que cette démarche un tantinet débile permette à mon solveur de trouver des solutions d'une originalité et d'une élégance qui me laissent pantois et me donnent presque envie de tomber en adoration en criant Allahou Akbar (la capacité des humains à adorer les idoles faites de main d'homme, fussent-elles des idoles faites d'octets et de silicone, doit être programmée dans nos gênes). Et puis, passé le temps de l'adoration, j'étudie la façon de faire du solveur, ou de la logique éternelle et incréée qui se révèle à travers lui (oui, je reste mystique: on ne se refait pas). Et parfois, je comprends, je retiens... et ça m'entraîne pour les problèmes futurs.

Il y aurait d'ailleurs là matière à d'intéressantes réflexions sur l'heuristique, la force brutale et même l'intelligence artificielle. Pendant longtemps, j'ai tenu l'intelligence artificielle pour une connerie authentique, un truc inventé par les débiles du marketing pour fourguer de la camelote. Or, dans certains cas précis, le terme est quand même pertinent: un processus mécanique, qui ne réfléchit pas ou vraiment si peu que rien, aide à mettre en lumière une démarche logique élégante dont l'intelligence humaine, la vraie, peut ensuite s'inspirer... pour se retrouver moins bête qu'avant. Mon casse-tête n'est pas qu'un passe-temps: c'est aussi une espèce de gymnastique intellectuelle qui me rassure sur les capacités de l'intelligence humaine à comprendre graduellement et de mieux en mieux le monde bordélique et absurde où nous nous débattons.

Je ne sais pas trop pourquoi je vous raconte tout ça, mais personne ne vous oblige à me lire.

http://fr.wikipedia.org/wiki/Space_Technology_5
Dix nouvelles technologies ont été testées par cette mission. L’une d’elle implique l’utilisation d’antennes conçues par un algorithme d'évolution artificielle.

Je pense qu'à un certain degré d'abstraction, l'intelligence naturelle, l'intelligence artificielle et l'intelligence tout court, c'est en fait la même chose. D'ailleurs, à un certain degré d'abstraction, ton trombone tordu ressemble furieusement à une abeille.

Non? Ca ne te paraît pas flagrant?

Mais non je ne plaisante pas. Allons donc. C'est pas du tout mon genre.

Je n'ai rien fait de particulier pour aboutir aux trente-quatre grilles que j'ai mises à votre disposition. Comme vous l'avez sans doute compris, ces grilles sont produites par un algorithme à partir du mot-graine qui leur donne leur nom, et donc je ne sais jamais a priori si ça va produire un problème simple, intéressant ou quasi-insoluble; cette incertitude fait partie du jeu.

A strictement parler, il n'existe pas de grille insoluble: il y a toujours un optimum de cases jaunes pour quelque grille que ce soit. Mais parfois, exceptionnellement, on ne peut pas atteindre cet optimum de façon "classique", en sacrifiant deux cases au début et un polygone convexe à la fin. C'est en particulier le cas quand une grille, au lieu d'être pleine de pentagones, hexagones et heptagones comme c'est très généralement le cas, se prive d'un de ces types de polygones convexes (généralement, en leur substituant des quadrilatères et des octogones).

Voici par exemple la grille "chirac":



Elle présente la particularité rare de ne comporter aucun pentagone, plus exactement aucun ensemble de cinq cases réunies autour d'un sommet commun. Et c'est bien ennuyeux, car j'ai énoncé plus haut le théorème (partiellement erroné, donc) selon lequel l'avant-dernier coup d'une partie à score optimal est toujours joué sur un pentagone, ayant deux cases en commun avec le polygone convexe sur lequel on doit jouer le dernier coup.

A quoi va donc pouvoir ressembler le score optimal?

Eh bien, la réponse à la question du post précédent est: c'est pas si compliqué que ça... En revanche, ça va être l'occasion de montrer de quelle créativité est capable un solveur, tout mécanique et stupide qu'il est.

La grille "chirac" comportant 36 cases, le score optimal théorique devrait être de 27 cases jaunes, soit neuf coups gagnants (2 cases sacrifiées au début, un heptagone sacrifié à la fin, ça nous fait 36 - 2 - 7 = 27 = 9 x 3). Mais l'absence de pentagone, facile à constater, indique que ce score ne pourra pas être atteint. Il va donc falloir réduire nos ambitions à huit coups gagnants, soit 3 x 8 = 24 cases, avec non plus 2 + 7 cases sacrifiées, mais bien 2 + 10: à la fin de la partie, c'est à priori dix cases qu'il faut sacrifier.

Y a-t-il un décagone sur la figure? Non (les décagones sont rarissimes). Il va donc falloir trouver autre chose.

Voici la solution que j'ai trouvée moi avec mon petit cerveau; comme souvent, c'est une des moins bien cachées: on peut dessiner le long du côté supérieur une enfilade (un couloir) de dix triangles, et la prendre en un seul coup final. Ce qui nous donne par exemple la séquence de coups: 6 32 25 26 30 28 15 23 9 18 11.

Cette solution trouvée par un humain est parfaitement valide, elle mène au score optimal et il n'y a rien à lui reprocher. Mais le solveur a d'autres idées.

On  peut remplacer ce couloir rectiligne et inélégant par un joli couloir biscornu: 6 22 35 28 8 2 31 4 11 15 25.

Au lieu de prendre dix cases en un coup final, on peut en prendre six, puis quatre, ou le contraire: 3 20 32 10 1 24 34 27 23 0 18 6.

Ou encore, et c'est à mon sens le plus ingénieux, on peut repérer deux hexagones mariés (ayant donc deux cases en commun) et les prendre en un seul coup final, ce qui a presque l'aspect d'une résolution "classique": 14 12 6 8 16 26 27 28 32 24 2.

Le solveur, lui, n'est pas soucieux d'élégance et peut aussi trouver des solutions bizarres, hétérodoxes et néanmoins valides: sacrifier deux cases à l'avant-dernier coup avant de prendre un couloir de huit cases en enfilade: 34 22 21 28 7 32 3 30 8 12 19 10.

Bref, ce solveur, tout crétin et mécanique qu'il est, peut se transformer en un très bon professeur, très ingénieux.

Essayez de reconstituer tous seuls une de ces solutions, si vous êtes cap'.

Je propose la séquence : 10, 12 (2 bleus), 16, 4, 2, 33, 34, 27, 21, 20 (8 × 3 jaunes). Cela produit un dessin assez érotique, ce qui n'est pas étonnant pour une grille Chirac.

J'aurais aussi quelques réflexions théoriques, mais quand ce sera au point.

Pieyre a écrit:Je propose la séquence : 10, 12 (2 bleus), 16, 4, 2, 33, 34, 27, 21, 20 (8 × 3 jaunes).

Bien joué.

Cela produit un dessin assez érotique.

C'est du cubisme, alors!

Je poserais bien une question aux matheux, tout particulièrement aux spécialistes des raisonnements par itération.

Combien y a-t-il de grilles Triancey concevables?

Je connais deux éléments de réponse: 1) énormément; 2) pas une infinité. Et j'aimerais bien savoir si "énormément", ça veut dire "des centaines de milliers" ou "des milliards de milliards". Ce dont je suis sûr, c'est que je n'ai encore jamais eu le sentiment de tomber deux fois sur la même grille... sauf évidemment quand j'avais utilisé deux fois le même mot-graine pour engendrer une fabrication (mon algorithme de fabrication est déterministe... vu que c'est un algorithme ).

Il y aurait assurément une infinité de grilles si le nombre de cases triangulaires sur une grille pouvait aller jusqu'à l'infini, mais ce n'est pas le cas avec mes algorithmes de fabrication. Je vous passe les détails, mais fondamentalement, la fabrication d'une grille consiste à saupoudrer un certain nombre de points sur la grille (points qui deviendront les sommets des triangles) et à les déplacer un peu (vers le barycentre des polygones) pour éviter la présence d'angles suraigus et de triangles très allongés. Ensuite on joint les points entre eux de façon que les segments ainsi formés ne se coupent pas, et quand on a fini, voilà, la grille est faite.

Mon algorithme impose une contrainte, qui limite le nombre de ces points: il est impossible d'ajouter un point à la grille si cela le placerait en-deçà d'une distance minimale avec un autre point déjà défini. Ajoutez à cela le déplacement des points vers le barycentre du polygone qu'on peut dessiner autour d'eux en réunissant toutes les cases ayant ce point pour sommet, et vous obtenez la physionomie de mes grilles, où les triangles sont "isogonoïdes" (c'est-à-dire: ressemblent vaguement à des triangles équilatéraux: leurs côtés ne sont pas disproportionnés, leurs angles sont généralement supérieurs à pi/4 -- 45 degrés -- et presque toujours supérieurs à pi/6 -- 30 degrés) et où les polygones engendrés sont très généralement des pentagones, des hexagones et des heptagones, possédant deux à deux un nombre de cases communes égal à deux. Il y a certes des exceptions (qui ne me dérangent pas: elles donnent du piment au jeu), mais ce sont bien des exceptions: elles se présentent très rarement et ne sont pas complètement différentes de la grille orthodoxe lambda (ce qui permet de les résoudre sans changer de logique).

Pour les grilles que je vous présente, la distance minimale entre deux sommets est de 0.165 (pour des grilles de côté 1.0), c'est-à-dire en gros un sixième de la largeur du carré-tore. Cette valeur n'a pas été choisie de façon totalement arbitraire: l'idée était de faire en sorte qu'il faille à peu près parcourir huit cases pour traverser la grille de part en part (de façon qu'un dernier coup joué sur un couloir prenne huit cases et ne soit donc pas optimal par rapport à un dernier coup joué sur un pentagone, un hexagone ou un heptagone).

Quand j'essaye la même logique avec une distance minimale de 0.5 ou 0.33, il est flagrant que je n'obtiens pas une infinité de grilles différentes, mais seulement quelques dizaines. Mais évidemment (enfin, c'est pas très difficile à comprendre), chaque fois qu'on arrive à caser un sommet de plus, le nombre de cases de la grille est majoré de deux. Donc, plus il y a de sommets, plus il y a de cases, plus il y a de grilles différentes envisageables, et ce de façon exponentielle.

Si la distance minimale entre deux points était de 1.0 (la largeur du carré), il n'y aurait que deux grilles envisageables (et même qu'une seule, car ces deux grilles seraient en fait deux fois la même avec des orientations différentes) et elle ne comporterait qu'un sommet sur le tore (répété aux quatre coins de la figure représentée à plat).

Chaque fois que j'ajoute un point-sommet, cela va se traduire ou par la division d'un segment (il y aura deux segments là où il n'y en avait qu'un), ou par la division d'une surface (il y aura trois triangles là où il n'y en avait qu'un); dans les deux cas, le nombre de cases de la grille est majoré de deux.

C'est à peu près tout ce que j'ai compris, et j'espère rencontrer l'esprit brillant qui saura s'appuyer sur tout ça pour évaluer le nombre de grilles possibles avec quatre cases, six, huit, dix, douze, etc., jusqu'à une petite soixantaine (en pratique, il est rarissime qu'on dépasse 48 cases).

Chers lecteurs matheux, à vos itérateurs.

Bon, ben en attendant que les bons mathématiciens se décident à me faire un bon raisonnement par itération, le mauvais mathématicien que je suis va se contenter de vous en présenter un mauvais... mais je pense que ce sera instructif quand même.



Sur le haut de cette figure, vous voyez la seule grille Triancey possible avec deux cases (on pourrait orienter la diagonale différemment, mais ça ne ferait pas une figure différente).

Sur le bas de cette même figure, vous voyez les trois grilles Triancey possibles avec quatre cases.

En augmentant le nombre de cases du minimum (deux cases de plus chaque fois qu'on ajoute un sommet), j'ai multiplié le nombre de grilles par trois.

Supposons (à mon avis c'est archi-faux, mais pas faux n'importe comment: c'est forcément très sous-estimé) que chaque fois que j'ajoute ainsi un sommet dans une grille existante, ça lui donne une descendance de trois grilles. Dans ce cas:

- avec deux cases, j'ai 3 puissance 0 grille.

- avec quatre cases, j'ai 3 puissance 1 grilles.

- avec six cases, j'ai au moins 3 puissance 2 grilles...

Donc quand j'arrive dans la zone de la quarantaine de cases où se trouvent la plupart des grilles produites par mon algorithme, je dois déjà avoir au moins dans les 3 puissance 20 grilles. Or 3 puissance 20, ça représente plus de 3 milliards (si ma table de logarithmes ne débloque pas).

Donc il n'y a pas seulement quelques milliers de grilles Triancey sur lesquelles on peut se triturer les méninges, mais au minimum plusieurs milliards. En fait, il y a même tellement de grilles concevables qu'il y a de quoi occuper jusqu'à leur mort tous les matheux de la planète. Donc, en rendant mon jeu libre de droits, j'inonde l'humanité de bienfaits et je mérite qu'on m'érige une statue.

Très bien. C'est tout ce que je voulais savoir.

Petitagore a écrit:


Sur le haut de cette figure, vous voyez la seule grille Triancey possible avec deux cases (on pourrait orienter la diagonale différemment, mais ça ne ferait pas une figure différente).
Sur le bas de cette même figure, vous voyez les trois grilles Triancey possibles avec quatre cases.

Tu vas surement me répondre que j'ai rien suivi, mais tant qu'à y être, pourquoi ne pas présenter les Carrés avec trois Triangles à l'intérieur aussi. Tu as fait deux. Tu as fait quatre. Pourquoi pas trois alors ?   Bon de ce que je comprends, c'est dû au fait qu'il faut impérativement que les deux cotés opposés du carré englobant soient strictement identiques. Bien bien.

Sinon t'avais pas dit que chaque Triangle avait toujours trois voisin ? Un voisin pour chacun de ses cotés ... J'ai pas bien pigé par quelle magie mystique tu arrives à nous convaincre que les deux triangles de la grille a deux triangles, ont chacun trois voisins distincts (Trois fois l'autre triangle donc). A moins que en fait, il suffit que le voisin soit distinct de soi même, auquel cas ça fonctionne.


Et surtout, et pour finir mes questions, si on numérote de 1 à 3 tes grilles à quatre cases de gauche à droite (et à supposer que mes réponses à mes propres questions au dessus ici posées soient justes), alors je ne vois strictement aucune différence entre la grille 1 (à gauche) et la grille 2 (au milieu). Ces deux grilles semblent identiques.  Du coup ça fait 2 puissance 20 = 1 048 576

(Je suis pas matheux hein, donc je ne fais que poser une question, à partir de ce que je vois)

Chaque fois que j'ajoute un point-sommet, cela va se traduire ou par la division d'un segment (il y aura deux segments là où il n'y en avait qu'un), ou par la division d'une surface (il y aura trois triangles là où il n'y en avait qu'un); dans les deux cas, le nombre de cases de la grille est majoré de deux.

Heu oui, pareil. On compte bien deux façons donc. Et non trois.

Stauk a écrit:Tu vas surement me répondre que j'ai rien suivi

Bien au contraire, je vais me réjouir qu'il y en ait encore un qui suive.  

mais tant qu'à y être, pourquoi ne pas présenter les Carrés avec trois Triangles à l'intérieur aussi. Tu as fait deux. Tu as fait quatre. Pourquoi pas trois alors ?   Bon de ce que je comprends, c'est dû au fait qu'il faut impérativement que les deux cotés opposés du carré englobant soient strictement identiques. Bien bien.

Oui, c'est ça. On en a parlé plus haut.

Sinon t'avais pas dit que chaque Triangle avait toujours trois voisin ? Un voisin pour chacun de ses cotés ... J'ai pas bien pigé par quelle magie mystique tu arrives à nous convaincre que les deux triangles de la grille a deux triangles, ont chacun trois voisins distincts (Trois fois l'autre triangle donc). A moins que en fait, il suffit que le voisin soit distinct de soi même, auquel cas ça fonctionne.

Non, tu as raison, le dessin du haut n'est pas une grille Triancey: pour être une grille Triancey, il faut avoir au moins quatre cases. J'étais bien conscient que c'était abusif, mais 1) c'était pour voir si vous suiviez;   2) pour le raisonnement par itération, c'était quand même bien pratique. Mais en effet, en toute rigueur, j'aurais dû démarrer ma démonstration avec quatre cases et pousser jusqu'à six. Mais 1) j'avais la flemme; 2) c'était pour motiver les contributeurs... à faire le boulot à ma place (l'esprit du web 2.0: quand c'est gratuit, c'est que c'est vous le produit! ).

Et surtout, et pour finir mes questions, si on numérote de 1 à 3 tes grilles à quatre cases de gauche à droite (et à supposer que mes réponses à mes propres questions au dessus ici posées soient justes), alors je ne vois strictement aucune différence entre la grille 1 (à gauche) et la grille 2 (au milieu).

Cornegidouille, tu as raison. Bon. Mais c'est visuellement différent, donc on dira que c'est valide pour compter les grilles visuellement différentes. Non? Tu n'es pas convaincu? T'es bien un matheux.  

Ouais, bon, j'avoue, mon raisonnement est foireux et pas mathématique. Mais il donne quand même une idée, un ordre de grandeur et même de gigantitude. Enfin, je crois.

Du coup ça fait 2 puissance 20 = 1 048 576.

Ah, ça va pas suffire pour qu'on m'érige ma statue. Va falloir que je le démontre mieux.

Petitagore a écrit:

Stauk a écrit:Du coup ça fait 2 puissance 20 = 1 048 576.

Ah, ça va pas suffire pour qu'on m'érige ma statue. Va falloir que je le démontre mieux.

Oui surtout que si ça se trouve c'est beaucoup moins. J'avoue que j'ai du mal à les compter tes bidules là. Ca me donne mal au crâne quand j'essaye ^ ^

Petitagore a écrit:Je poserais bien une question aux matheux, tout particulièrement aux spécialistes des raisonnements par itération.

Combien y a-t-il de grilles Triancey concevables?

Avant de chercher à les compter, il peut être judicieux de définir une règle d'égalité entre deux grilles, car selon comment on la définit, le résultat n'est pas le même !

Première option : « si on déplace légèrement un point sur une grille, alors la nouvelle grille et l'ancienne sont différentes » => Il y a trivialement une infinité de grilles

Deuxième option : Si on associe à une grille un graphe, dont chaque sommet est un des triangle de la grille et les arêtes relient ensemble des sommets dont les triangles associés sont voisins (chaque sommet a donc 3 arêtes). Et qu'on définit deux grilles comme égales si les deux graphes générés ont la même topologie, ce n'est pas forcément évident à voir, mais dans ce cas, tes 3 grilles à 4 triangles sont égales !

Avez-vous d'autres pistes ?

Levans a écrit:Avez-vous d'autres pistes ?

Je suggérerais bien de prendre en compte (entre autres) le nombre de cases autour d'un sommet commun. De ce point de vue-là, mon schéma représente bien, quand même, deux grilles à quatre cases différentes: la figure du milieu (celle de gauche aussi, d'ailleurs) a quatre cases autour de chaque sommet, et celle de droite seulement trois. Donc je pense qu'on ne peut les considérer comme identiques.

Mais c'est vrai que c'est monstrueusement prise de tête, ce bazar.

Levans a écrit: tes 3 grilles à 4 triangles sont égales !

Clairement, elle ne sont pas égales.  Suffit de considérer ce que j'appelle la "cardinalité" des sommets pour s'en convaincre. Ou cardinalité correspond au nombre de segments qui partent du sommet. Bon je trouve ça très mal commode de compter les sommets, alors j'ai pas du tout envie d'essayer ... surtout du fait que le bidule est un donut. Moi les donuts dépliés, j'ai du mal. Je les préfère dans mon estomac.

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.

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é.

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.

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).

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!

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...

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é ?

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...
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.

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.

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.  



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).

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 :

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...

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.

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.

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.

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.

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.

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.

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...

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?

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

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.

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

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!

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.

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.

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.