Kürzeste bitstring deren unendliche Wiederholung unterscheidet sich nach der Umkehrung

Question

Marvin Minsky mir die folgenden Fragen während meiner mündlichen Prüfung gefragt:

  

Wie eine Ameise geht es druckt eine binäre Zahl (zum Beispiel 101) jedes Mal, dauert es einen Schritt zurück. Was ist die minimale Länge, in Ziffern kann die binäre Zahl sein, damit es möglich sein, in welcher Richtung zu sagen, die Ameise, ohne am Anfang oder Ende des Strings suchen reisen? Die Ameise sagt Ihnen, die binäre Zahl.

Beispiel: Die binäre Zahl der Ameise ist 101, und daher lässt die Ameise eine Spur, die wie folgt aussieht: 101101101101101101101. Beachten Sie, dass es keine Möglichkeit, die Art und Weise zu sagen, ist die Ameise fährt. Daher ist diese besondere Nummer funktioniert nicht (aber es kann eine dreistellige binäre Zahl sein, die der Fall ist).

Beispiel: Die binäre Zahl der Ameise ist 011 und damit die Ameise eine Spur hinterlässt, die wie folgt aussieht: 011011011011011011. Auch hier gibt es keine Möglichkeit, zu sagen, welche Art und Weise die Ameise ohne fährt an den Enden des Strings zu suchen.

Was ist die Antwort auf diese Frage? Beachten Sie, dass die Antwort nicht nur ein Beispiel für eine binäre Zahl sein kann, die funktionieren. Die Antwort muss einen Nachweis enthält, dass keine binäre Zahl mit einer Länge von weniger als n-1 eingegeben werden, wobei n die Länge der Beispiel binären Zahl ist, die funktioniert. Ein Beweis durch erschöpfende Aufzählung ist in Ordnung, aber unangenehm. :)

Answer 1

Ein weiterer Ansatz wäre von Binärzahlen abzuweichen. Formulieren Sie die Frage „Was ist die kürzestmögliche Muster ist, das gerichtet ist, wenn man erlaubt ist, eine beliebige Anzahl von einzigartigen Symbole zu benutzen?“

Die Antwort ist 3 (zum Beispiel A, B, C oder #; &; @) seit 2 nicht funktioniert. Also, wenn Sie ein Muster wie ABC wird, in welcher Richtung klar ist, die Ameise geht.

Entweder ... CABCABCABCABCAB ... (von links nach rechts) Oder ... CBACBACBACBACBA ... (von rechts nach links)

Nun, wie viele Binärziffern brauchen wir ein Muster von 3 Symbolen in Ternary (Basis-3) schreiben?

Zwei Binärziffern können Sie einzelne Quartär (Basis-4) Ziffer schreiben, die die erste Base höher als oder gleich 3 ist

So:. (2 Ziffern-per-Symbol), multipliziert mit (3 Symbolen) = 6 Binärziffern

Answer 2

ChssPly76 hat die richtige Antwort (IMHO) in den Kommentaren oben.

6 Ziffern, zB 100.110.