コインを円で弾く
N枚のコインがすべて円形に配置されています。それらはすべて、表向きに「しっぽ」を持っています。コインはすべて別個のものであり、数字（1,2,3 ... N）が書かれています。
それぞれの動きで、3枚の連続したコインを裏返します。つまり、次のことを考慮してください。
HHHTT
コイン3、4、5を裏返すことにした場合、次のようになります：HHTHH
これで、N個の異なるコインの2 ^ N個の異なる表-裏順列が存在する可能性があります。
1.最初のすべての尾の順列から、これらのNコインの（2 ^ N）の頭と尾の順列のいずれかに到達できる有限の動きのセットがあることを証明/反証します。
2.また、任意の順列に到達することが実際に可能である場合、最初のすべてのテール順列から任意の順列に到達するために必要な移動の最大数はいくつですか。
さらに明確にするために、たとえばNが3の場合、これら3つのコインの2 ^ 3の異なる順列は次のようになります。
TTT
TTH
THT
THH
HHH
HHT
HTH
HTT
回答
仮定しましょう $N \geq 3$そうでなければ、問題は明確に定義されていません。
パート1：
コインの終了位置は、コインが裏返された回数にのみ依存します（裏返しの回数が偶数の場合はT、奇数はHになります）。
したがって、移動（3回のフリップで構成される）は可換です。また、動きは明らかに自己逆であるため、同じ動きを2回行っても意味がありません。したがって、（順序付けられていない）移動位置のセット（その中には$2^N$）。
すべての位置に到達できるわけではない場合、2つの異なる移動セットで同じ結果が得られる必要があります。しかし、これは、これらの移動セット間の対称差（XOR）が、すべてTの構成を与える必要があることを意味します。したがって、代わりに、すべてTを与える空でない移動セットがあるかどうかを尋ねることができます。
どの移動セットでも、各コインが裏返されます。 0から3回の間。また、隣接するコインのフリップの数は、0または1だけ異なる必要があります（フリップする動きは1つだけです）$x$ ではなく $x + 1$したがって、すべてのTを取得するには、フリップの数がすべて0またはすべて2である必要があります。すべて0は、空の移動セットでのみ可能です。2つすべてはどうですか？
各移動で3枚のコインが反転するため、反転の総数は3の倍数である必要があります。したがって、2つすべてを取得することは不可能です。$N$ 3の倍数です。 $N$3の倍数です簡単です。すべてのコインは、3つおきの位置に移動することで裏返すことができます。次に、同じことをもう一度実行できますが、1シフトして元に戻します。
したがって、すべての終了位置は、次の場合にのみ到達可能です。$N$は3で割り切れません。
パート2：
すべての位置に到達できる場合、すべての移動セットは異なる位置に到達します。特に、すべての移動位置のセットは、で特定の終了位置に到達します$N$移動し、他の位置ではそれ以上の移動は必要ありません。この特定の位置は、各コインを3回反転するため、実際にはすべてHです。
特定の終了位置の移動セットをすばやく計算するには、最初にコイン1を反転するだけの移動セットを計算することをお勧めします。次に、この移動セットをシフトして単一のコインを反転する方法を知っています。そして、単一のコイン移動セット（対称差/ XORを使用）を組み合わせることにより、任意の結果を計算できます。
あまり「数学的」でないアプローチ：
任意の構成に到達するための問題は、正確に1枚のコインを裏返す一連の動きと同等であることは明らかです。
今それを見つける方法：
シーケンス1、2、4、5、7、...を使用して、必要なフリップシーケンスを簡単に作成できます（番号は開始コインに対応し、1はコインをフリップすることを意味します1、2、3）。これにより、コイン2（N = 3k + 1）またはN（N = 3k + 2）のいずれかが反転します。構造は明らかです。最初の動きで頭として設定しているコイン1から始めて、残りのすべてを反転し続けて、円の「終わり」に向かって伝播する頭が1〜2個になるようにします。それらの頭が（ほぼ）最初の頭に出会ったら、最後のフリップを実行します。N = 3k + 1の場合、最後に1つのヘッドを取得し、コイン2だけをフリップします。N= 3k + 2の場合、最後の前に1つのヘッド1を取得し、コインNだけをフリップします。N= 3kの場合、2つのコインを取得します。終わりとすべての尾に到達します。これらのコインを「絞り出して」単一の「ヘッド」を残すことはできないため、すべての構成に到達することはできません。
今最悪の場合：
すべての頭を取得するには、すべてのコインを1〜3回裏返す必要があります。明らかに、N = 3k + 1または2ですべてのコインを1回裏返すことはできません。コインXが3回裏返された場合、コインX + 1はすでに2回裏返されているため、もう一度裏返す必要があります。最初のすべての尾からすべての頭を取得するには、すべてのコインを3回裏返す必要があります。