Accueil / Jeux /Puzzles / Hexagrilles
Hexagrilles
Description
La grille de jeu
Vous pouvez remarquer qu'il s'agit d'une grille et que des petits cercles sont placés aux intersections des lignes de la grille. (Ces petits cercles seront aussi appelés des sommets, ils correspondent aux sommets d'un graphe G).
Les traits ont trois orientations différentes ( - ou / ou \), c'est-à-dire E-W (Est-Ouest ou droite-gauche), NE-SW (Nord-Est, sud Ouest) et NW-SE. (Les traits qui relient deux sommets sont les arêtes du graphe G).
La forme externe de la grille est un hexagone régulier.
Lorsque chaque côté de l'hexagone contient n sommets (n petits cercles),
le nombre de lignes de chaque direction est 2n-1.
Quel est le nombre total de sommets ? La suite 1, 7, 19, 37, 61, 91, 127 est la suite [OEIS A003215].
Règles
Plusieurs types de jeux sont possibles sur ces grilles hexagonales.
MAXIMUM (Puzzle I)
Cochez un maximum de points en cliquant à l'intérieur des cercles.
Attention, on ne peut cocher qu'un sommet au plus de chaque ligne des trois directions E-W, NE-SW et NW-SE.
Pour effacer, il suffit de cliquer une seconde fois.
(Indication : il est toujours possible de trouver 2n-1 cases à cocher, une sur chaque ligne, dans toutes les directions).
MINIMUM (Puzzle II)
Bloquez le jeu en cochant un minimum de sommets judicieusement choisis.
Toute autre sommet du jeu est alors sous la menace d'au moins un sommet coché.
(Indication : il est toujours possible de bloquer le jeu en cochant n cases lorsque n est impair et n-1 cases lorsque n est pair).
Puzzles 1&2
Compléments
Cliquez ici pour afficher ou masquer les compléments
Grille
La forme externe de la grille est un hexagone régulier.
Chaque côté de l'hexagone contient n petits cercles ( n points du quadrillage hexagonal ou n sommets d'un graphe),
le nombre de lignes de ce réseau, dans chacune des trois directions, est 2n-1.
Le nombre total P(n) = 6n-5 de points (ou de sommets) nous donne la suite 1, 7, 19, 37, 61, 91, 127 [OEIS A003215] des nombres hexagonaux.
Il existe des suites de nombres triangulaires [ A000217], carrés [ A000290], pentagonaux [ A005891], hexagonaux [ A000217], heptagonaux [ A005891], hexagonaux [ A069099]...
Le nombre S(n) de solutions au puzzle 1 en fonction de n donne la suite 1, 2, 6, 28, 244, 2544, 35600, 659632, 15106128, 425802176 [OEIS A002047].
Ensembles stables maximum (Puzzle I)
Le graphe G a pour ensemble X de sommets, l'ensemble des petits cercles de la figure. Deux sommets distincts quelconques sont reliés dans le graphe par une arête lorsqu'ils sont sur une même ligne (de l'une des trois directions principales).
(Il n'est pas nécessaire que les deux sommets soient à proximité l'un de l'autre pour être reliés dans le graphe, ils ont juste besoin d'être sur une même droite)
Un ensemble Y de sommets est stable si deux sommets quelconques de Y ne sont pas reliés.
Un ensemble stable est maximum s'il n'existe pas d'ensemble stable ayant plus de sommets. Le nombre de sommets d'un ensemble stable maximum est le "nombre de stabilité" du graphe.
Comme on ne peut mettre plus d'un sommet sur chaque droite et que les 2n-1 droites parallèles d'une même direction contiennent l'ensemble des sommets, un stable maximum a au plus 2n-1 sommets. Qelques lignes de calcul suffisent pour généraliser la disposition de la figure ci-dessus à toute autre dimension et donc de trouver un ensemble stable maximum de 2n-1 sommets, (il existe d'autres types de figures que l'on pourrait tout aussi bien généraliser).
On en déduit que ce graphe a pour nombre de stabilité 2n-1.
Si vous n'arrivez pas à trouver d'autre solution au puzzle I : Cliquez ici pour obtenir un stable maximum au hasard.
(Les réponses sont trouvées ou construites par un procédé aléatoire mais leurs apparitions ne sont pas équiprobables).
Noyaux minimum (Puzzle II)
Une sous-ensemble Y de l'ensemble des sommets est absorbant si tout sommet du graphe n'appartenant pas à Y, est relié par une arête du graphe à un sommet au moins de Y.
Un ensemble absorbant contenant un nombre minimum de sommets est un ensemble absorbant minimum.
Le puzzle de cette page exige plus que cela : les sommets cochés ne doivent pas être reliés (ne doivent pas être placés sur une même ligne), l'ensemble de ces sommets doit donc être aussi un ensemble stable.
Un ensemble de sommets qui est à la fois stable et absorbant est appelé un noyau.
Résoudre le puzzle 2 revient donc à déterminer une partie stable et absorbante (donc un noyau du graphe), et si possible un noyau minimum.
Si vous n'arrivez pas à trouver de solution satisfaisante au puzzle II : Cliquez ici pour obtenir un noyau de taille n (lorsque n est impair) ou de taille n-1 (lorsque n est pair).
Attention, pour n supérieur ou égal à 8 le temps de calcul peut être vraiment long, soyez patient. La solution est choisie au hasard, en cliquant à nouveau vous en aurez peut-être une autre.
Autre remarque d'importance : Un stable maximum de l'hexagone de côté n est un noyau d'hexagones de côtés 2n-1 et 2n.
|
