タンポポグラフのカエルゲーム
地元の池に多少の騒音があります。カエルのグループが誕生日パーティーを主催したいと思っています！
池には合計22のスイレンがあり、それぞれに1匹のカエルがいます。彼らは0から21までの数字でラベル付けされています。彼らの生活を楽にするために、各カエルは彼女の隣人のそれぞれに1つの橋を架けました。カエル0は最も人気のあるカエルであり、1から7までのカエルが隣人としていますが、8から21までのカエルは、前のカエルだけが隣人としています。
9番目のカエルは彼女の誕生日を祝いたいと思っています。他のすべてのカエルを彼女のユリパッドに案内できますか？
空でないスイレンパッドA上のn個のカエルすべてに、正確にn個の一意のブリッジで構成されるパスがAとBの間に存在する場合にのみ、他の空でないスイレンパッドBにジャンプするように指示できます。
これを下の画像に示します。
言い換えれば、カエルゲームのルールは正式に次のように与えられます：
カエルゲーム
ゲームは、頂点が「ユリパッド」（睡蓮）を表すグラフでプレイされます。
ゲームの開始時に、各ユリパッドに1匹のカエルを置きます。
ゲームの目的は、すべてのカエルを1つの指定されたユリパッドに移動することです。
両方のスイレンが空ではなく（少なくとも1つのカエルを含む）、正確にn個の一意のエッジで構成されるAからBへのパスが存在する場合にのみ、スイレンAに含まれるn個のカエルすべてを他のスイレンパッドBに正確に移動できます。 。
次に、画像のパズルは正式に次のように与えられます。
パズルの目標は、解決することであるカエルのゲームを上第九頂点与えられたグラフの（上の画像を参照します）。グラフは、0番目の頂点としてラベル付けされたルート頂点と、{1、2、3、4、5、6}としてラベル付けされた6つのリーフ頂点と、頂点が{7、8としてラベル付けされた15の頂点の1つのパスグラフで構成されます。 、9、...、21}。
グラフを印刷し、トークンを使用してカエルを表すことをお勧めします。そうでなければ、ペンと紙を使うことは問題ではないはずです（それが私が最終的にそれを解決した方法です）。
PSウォームアップするために、カエルのゲームがパスグラフの任意の頂点で解決できることがわかりますか？
それの訳は：
経路グラフPを置くN数直線上の頂点をn個と。中央の頂点から開始し、左右に交互にジャンプする場合（または、nのパリティによってはその逆）、葉の頂点（次数1の頂点）でパスを簡単に解決できることがわかります。
ここで、任意の頂点vのパスグラフP nを解くには、頂点vをリーフとして共有する（そして他の頂点を共有しない）2つのパスサブグラフに分割し、リーフ頂点戦略を使用して各サブグラフを解きます。
このパズルは、線からグラフまで、ナンバーフィルパズルの私の一般化に触発されました。このパズルで与えられたグラフは、「タンポポのグラフ」についての私の古い推測の1つに対する最小の反例であるため、特別です。
（与えられたグラフの）パズルの画像を作成するために、csacademyのグラフエディタを使用しました。
PS Mathpickleには、このようなパズルがたくさんあります。見る：
https://mathpickle.com/project/lazy-toad-puzzles-counting-symmetry/
https://mathpickle.com/project/lazy-toads-on-a-star/
回答
ユニークなソリューション？
グループA：
花びら1から5まで5匹のカエルを0に
移動します。0から12に6匹のカエルを移動します= 12に7匹のカエルを
移動します。12から19に7匹のカエルを移動します= 19に8匹のカエル
。
2匹のカエルを21から19に
移動= 19に10匹のカエル。10匹のカエルを19から9に移動= 9に11匹のカエル。
グループB：
1匹のカエルを13から14に
移動= 14に2匹のカエル15から16に1匹のカエルを
移動= 16に2匹のカエル16から14に2匹のカエルを移動= 14に
4匹のカエル14から10に4匹のカエルを移動= 5匹のカエル10.5
匹のカエルを10から6に
移動= 6匹のカエルを6に移動6匹のカエルを6から11に
移動= 11匹に7匹のカエル7匹のカエルを11から18に
移動= 1匹のカエルを18に移動17から18に1匹のカエル= 9 18のカエル
。9つのカエルを18から9に移動= 9の20のカエル。
そして最後に：
1匹のカエルを8から7に
移動= 2匹のカエルを7に移動します。2匹のカエルを7から9に移動します= PARTY ON 9 !!
他の解決策があるかもしれませんが：
ステップ1：
1→0、2→0、3→0、4→0、5→0、6→0を介して、すべての花びらを0に集めます。
ステップ2：
0の7匹のカエルでできる唯一のことをしてください：それらを13にジャンプさせてください。次に、そこにある8匹のカエルを21にジャンプします。これで、21に9匹のカエルがいます：0、1、2、3、4、5、6、13、21。
ステップ3：
これらの9匹のカエルが直接作ることができる唯一のジャンプは12になります、しかしそこであなたは立ち往生するでしょう。実際、私たちはそれらを直接9にしたいと思っています。したがって、さらに3匹のカエルが必要です。最善の方法は、隣接するユリパッド18、19、20から、19→20、（19）（20）→18、（18）（19）（20）→21を介してそれらを取得することです。21に12匹のカエルがいるので、すべて9匹にジャンプできます。
ステップ4：
OPは、エンドポイントの1つへのパスにすべてのカエルを配置する方法を示しているため、理論的には完了です。7-8から9および10-17から9が可能ですが、明示的には8→7、78です。 →9; および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、および（10）（11）（12）（13）（14）（15）（16）（17）→9。
元の不正解-ああ、私は馬鹿ですか。
これが1つの解決策ですが、他の解決策もあるかもしれません。
最初に気付くのは、0は1回しか使用できないため、最初にいくつかの花びら（1〜6）を中央に配置してから、すべてを0から移動するように注意する必要があります。最初に試みるのは明らかです。1〜6枚の花びらをすべて0に移動してから、7匹のカエルを13にジャンプします。しかし、これはすぐに消えてしまいます。8匹のカエルを21にジャンプし、次に9匹のカエルを12にジャンプすると、行き詰まります。 。
ただし、カエルを花びらにジャンプさせてから9に戻すことができるため、一度にすべての花びらを取得する必要はありません。1つを除くすべての花びらを0にジャンプして、シリーズ：1→0、2→0、3→0、4→0、5→0、012345→12、012345（12）→19。19に戻るには、2匹の追加のカエルが必要です。20→21と（20）（21）→19を介して取得でき、混乱全体012345（12）（19）（20）（21）は9に戻ります。 。
次のステップ：
この時点で、9匹のカエルの群れと、6、7、8、10、11、13〜18匹の単一のカエルがいます。まずは花びら側を片付けましょう。9に戻るには、6に3匹のカエルが必要です。8→7、78→6、678→9で取得できます。これで、10と11は10→11、（10）（11）→9で9になります。最後に、13から18の間に6つのカエルが並んでおり、与えられたパスグラフの結果によって15でまとめることができます（明示的に：14→13、（13）（14）→15、17→16、（16）（17） →18、（16）（17）（18）→15）、そして最後にこの質量は9にジャンプし、パズルを終了します。