10

マービンミンスキーは私の口頭試験中に次の質問をしました：

アリが歩くと、一歩踏み出すたびに2進数（101など）が出力されます。文字列の最初または最後を見なくても、アリがどちらの方向に進んでいるかを判断できるようにするための2進数の最小の長さは、数字で何ですか？アリは2進数を教えてくれます。

例：アリの2進数は101であるため、アリは次のような軌跡を残します：101101101101101101101。アリがどちらの方向に移動しているかを知る方法がないことに注意してください。したがって、この特定の番号は機能しません（ただし、機能する3桁の2進数が存在する場合があります）。

例：アリの2進数は011であるため、アリは次のような軌跡を残します：011011011011011011。繰り返しますが、文字列の端を見ずにアリがどちらの方向に進んでいるかを知る方法はありません。

この質問に対する答えは何ですか？答えは、機能する2進数の単なる例ではないことに注意してください。答えには、n-1未満の長さの2進数が機能しないという証明を含める必要があります。ここで、nは機能する2進数の例の長さです。徹底的な列挙による証明は問題ありませんが、不快です。:)

4

2 に答える 2

6

もう 1 つのアプローチは、2 進数から離れることです。質問を次のように言い換えます。

2 は機能しないため、ここでの答えは 3 (たとえば、A;B;C または #;&;@) です。つまり、ABC のようなパターンがあると、アリがどちらの方向に歩いているかが明確になります。

...CABCABCABCABCAB... (左から右へ) または ...CBACBACBACBACBA... (右から左へ)

では、3 進数 (基数 3) で 3 つの記号のパターンを記述するには、2 進数で何桁が必要ですか?

2 進数を 2 桁使用すると、1 つの 4 進数 (基数 4) の数字を書き込むことができます。これは、3 以上の最初の基数です。

したがって、(シンボルあたり 2 桁) に (3 シンボル) を掛けた = 2 進数の 6 桁。

于 2009-07-22T14:56:59.730 に答える
2

ChssPly76は、上記のコメントに正解（IMHO）があります。

6桁、例100110。

于 2009-07-21T18:58:29.753 に答える