Jeu de grenouille sur un graphique de pissenlit
Il y a du bruit dans l'étang local. Un groupe de grenouilles veut organiser une fête d'anniversaire!
Il y a un total de 22 nénuphars dans l'étang, chacun abritant une seule grenouille. Ils sont étiquetés comme des nombres de 0 à 21. Pour leur faciliter la vie, chaque grenouille a construit un pont vers chacun de ses voisins. La grenouille 0 est la grenouille la plus populaire et a des grenouilles de 1 à 7 comme voisines, alors que les grenouilles de 8 à 21 n'ont que la grenouille précédente comme voisine.
La 9e grenouille veut fêter son anniversaire. Pouvez-vous guider toutes les autres grenouilles vers son nénuphar?
Vous pouvez demander à toutes les n grenouilles d'un nénuphar non vide A de sauter vers un autre nénuphar non vide B si et seulement s'il existe un chemin entre A et B composé d'exactement n ponts uniques.
Ceci est illustré dans l'image ci-dessous.
En d'autres termes, les règles du jeu de grenouille sont formellement données comme suit:
Le jeu de grenouille
Le jeu se joue sur un graphe dont les sommets représentent des "nénuphars" (nénuphars).
Au début du jeu, placez une grenouille sur chaque nénuphar.
Le but du jeu est de déplacer toutes les grenouilles vers un seul nénuphar donné.
Vous pouvez déplacer exactement toutes les n grenouilles contenues sur le nénuphar A vers un autre nénuphar B si et seulement si les deux nénuphars ne sont pas vides (contiennent au moins une grenouille) et qu'il existe un chemin de A à B composé d'exactement n bords uniques .
Ensuite, le puzzle dans l'image est formellement donné comme:
Le but du puzzle est de résoudre le jeu de grenouille sur le 9ème sommet du graphe donné (voir l'image ci-dessus). Le graphe se compose d'un sommet racine étiqueté 0e sommet, auquel nous connectons 6 sommets feuille étiquetés {1, 2, 3, 4, 5, 6} et un graphe de chemin de 15 sommets dont les sommets sont étiquetés {7, 8 , 9, ..., 21}.
Vous voudrez peut-être imprimer le graphique et utiliser des jetons pour représenter les grenouilles. Sinon, cela ne devrait pas être un problème d'utiliser un stylo et un papier (c'est ainsi que je l'ai finalement résolu).
PS Pour vous échauffer, voyez-vous que le jeu de grenouille peut être résolu sur n'importe quel sommet d'un graphe de chemin ?
Ceci est dû au fait:
Placez un graphe de chemin P n avec n sommets sur une droite numérique. Si vous commencez au sommet du centre et alternez les sauts gauche et droit (ou vice versa, selon la parité de n), vous pouvez voir qu'un chemin est facilement résoluble dans les sommets feuille (sommets de degré 1).
Maintenant, pour résoudre un graphe de chemin P n dans un sommet arbitraire v, divisez-le simplement en deux sous-graphes de chemin qui partagent le sommet v en tant que feuille (et ne partagent aucun autre sommet), et résolvez chaque sous-graphe en utilisant la stratégie de sommet de feuille.
Ce puzzle a été inspiré par ma généralisation d' un puzzle Numberphile , d'une ligne à des graphiques. Le graphique donné dans ce puzzle est spécial car c'est le plus petit contre-exemple à l'une de mes anciennes conjectures sur les "graphiques de pissenlit" .
Pour créer l'image du puzzle (du graphe donné), j'ai utilisé l' éditeur de graphes de csacademy .
PS Mathpickle a plus d'énigmes comme celle-ci! Voir:
https://mathpickle.com/project/lazy-toad-puzzles-counting-symmetry/
https://mathpickle.com/project/lazy-toads-on-a-star/
Réponses
Solution unique?
Groupe A:
Déplacez 5 grenouilles à 0 des pétales 1 à 5.
Déplacez 6 grenouilles de 0 à 12 = 7 grenouilles sur 12.
Déplacez 7 grenouilles de 12 à 19 = 8 grenouilles sur 19.
Déplacez 1 grenouille de 20 à 21 = 2 grenouilles sur 21.
Déplacez 2 grenouilles de 21 à 19 = 10 grenouilles sur 19.
Déplacez 10 grenouilles de 19 à 9 = 11 grenouilles sur 9.
Groupe B:
Déplacez 1 grenouille de 13 à 14 = 2 grenouilles sur 14.
Déplacez 1 grenouille de 15 à 16 = 2 grenouilles sur 16.
Déplacez 2 grenouilles de 16 à 14 = 4 grenouilles sur 14.
Déplacez 4 grenouilles de 14 à 10 = 5 grenouilles sur 10.
Déplacez 5 grenouilles de 10 à 6 = 6 grenouilles sur 6.
Déplacez 6 grenouilles de 6 à 11 = 7 grenouilles sur 11.
Déplacez 7 grenouilles de 11 à 18 = 8 grenouilles sur 18.
Déplacez 1 grenouille de 17 à 18 = 9 grenouilles sur 18.
Déplacez 9 grenouilles de 18 à 9 = 20 grenouilles sur 9.
Et enfin:
Déplacez 1 grenouille de 8 à 7 = 2 grenouilles sur 7.
Déplacez 2 grenouilles de 7 à 9 = PARTY ON 9 !!
Il peut y avoir d'autres solutions, mais:
Étape 1:
Rassemblez tous les pétales sur 0, via 1 → 0, 2 → 0, 3 → 0, 4 → 0, 5 → 0, 6 → 0
Étape 2:
Faites la seule chose que vous pouvez avec les 7 grenouilles sur 0: passez-les à 13; puis sautez les 8 grenouilles là-bas à 21. Vous avez maintenant 9 grenouilles sur 21: 0, 1, 2, 3, 4, 5, 6, 13, 21.
Étape 3:
Le seul saut que ces 9 grenouilles peuvent faire directement est à 12, mais là, vous serez coincé. En fait, nous voulons les amener directement à 9. Nous avons donc besoin de 3 grenouilles supplémentaires! La meilleure chose à faire est de les obtenir des nénuphars adjacents, 18, 19 et 20, via 19 → 20, (19) (20) → 18, (18) (19) (20) → 21. Nous avons maintenant 12 grenouilles sur 21, et pouvons toutes les faire passer à 9.
Étape 4:
Théoriquement, nous avons terminé, puisque l'OP montre comment obtenir toutes les grenouilles dans un chemin vers l'un de ses points d'extrémité, nous pouvons donc 7-8 à 9 et 10-17 à 9, mais pour être explicite: 8 → 7, 78 → 9; et 13 → 14, (13) (14) → 12, (12) (13) (14) → 15, (12) (13) (14) (15) → 11, (11) (12) (13) (14) (15) → 16, (11) (12) (13) (14) (15) (16) → 10, (10) (11) (12) (13) (14) (15) (16 ) → 17, et (10) (11) (12) (13) (14) (15) (16) (17) → 9.
Réponse incorrecte originale - Oh garçon, je suis stupide.
Voici une solution, il peut y en avoir d'autres:
La première chose à noter est que vous ne pouvez utiliser 0 qu'une seule fois, vous devez donc faire attention de centraliser d'abord certains des pétales (1-6), puis de les déplacer tous de 0. Mais combien à centraliser? La première chose évidente à essayer est tout: déplacez tous les 1-6 pétales à 0, puis sautez de 7 grenouilles à 13. Mais cela s'arrête rapidement: vous sautez de 8 grenouilles à 21, puis de 9 grenouilles à 12, et vous êtes coincé .
Mais vous n'êtes pas obligé de prendre tous les pétales à la fois, car vous pouvez sauter des grenouilles à un pétale, puis les renvoyer au 9. Alors essayons de prendre tous les pétales sauf un au 0, en donnant le série: 1 → 0, 2 → 0, 3 → 0, 4 → 0, 5 → 0, 012345 → 12, 012345 (12) → 19. Nous avons besoin de deux grenouilles supplémentaires pour revenir à 19, que nous pouvons saisir via 20 → 21 et (20) (21) → 19, et tout le désordre 012345 (12) (19) (20) (21) revient à 9 .
Prochaines étapes:
À ce stade, vous avez une masse de grenouilles sur 9 et des grenouilles simples sur 6, 7, 8, 10, 11 et 13-18. Nettoyons d'abord le côté pétale. Nous avons besoin de trois grenouilles sur 6 pour revenir à 9, ce que nous pouvons obtenir avec 8 → 7, 78 → 6 et 678 → 9. Maintenant 10 et 11 passent à 9 avec 10 → 11, (10) (11) → 9. Enfin, nous avons six grenouilles d'affilée entre 13 et 18 qui peuvent être massées en 15 par le résultat du graphe de chemin donné (explicitement: 14 → 13, (13) (14) → 15, 17 → 16, (16) (17) → 18, (16) (17) (18) → 15), puis finalement cette masse passe à 9, terminant le puzzle.