Münzen im Kreis werfen

Question

Wir haben einen Satz von N Münzen, die alle in einem Kreis platziert sind. Sie alle haben "Schwänze" als Gesicht nach oben. Die Münzen sind alle verschieden und mit Zahlen (1,2,3 ... N) versehen.

In jedem Zug werfen wir 3 aufeinanderfolgende Münzen. Das heißt, bedenken Sie:

HHHTT

Wenn ich mich entscheide, die Münzen 3,4 und 5 zu werfen, bekomme ich: HHTHH

Nun kann es 2 ^ N verschiedene Kopf-Schwanz-Permutationen von N verschiedenen Münzen geben.

1. Beweisen / widerlegen Sie, dass es eine endliche Menge von Zügen gibt, mit denen wir eine der (2 ^ N) Kopf-Schwanz-Permutationen dieser N Münzen erreichen können, beginnend mit der anfänglichen Permutation aller Schwänze.

2. Auch wenn das Erreichen einer Permutation tatsächlich möglich ist, wie viele Züge sind maximal erforderlich, um von der anfänglichen Permutation aller Schwänze zu einer Permutation zu gelangen?

Zur weiteren Verdeutlichung wären, wenn N beispielsweise 3 wäre, die 2 ^ 3 unterschiedlichen Permutationen dieser 3 Münzen:

TTT

TTH

THT

THH

HHH

HHT

HTH

HTT

Answer 1

Lasst uns annehmen $N \geq 3$oder das Problem ist nicht gut definiert.

Teil 1:

Die Endposition einer Münze hängt nur davon ab, wie oft sie geworfen wurde (gerade Anzahl der Würfe, es ist T; ungerade Zahl, H).

Bewegungen (bestehend aus drei Flips) sind also kommutativ. Außerdem sind Bewegungen eindeutig selbstinvers, sodass es keinen Sinn macht, dieselbe Bewegung zweimal auszuführen. Wir müssen uns also nur mit (ungeordneten) Sätzen von Bewegungspositionen befassen (von denen es auch gibt)$2^N$).

Wenn nicht alle Positionen erreichbar sind, müssen zwei verschiedene Bewegungssätze das gleiche Ergebnis liefern. Dies bedeutet jedoch, dass die symmetrische Differenz (XOR) zwischen diesen Zugsätzen die Konfiguration mit allen T ergeben muss. Wir können stattdessen fragen, ob es einen nicht leeren Zugsatz gibt, der alle T ergibt.

Für jeden Zugsatz wird jede Münze geworfen zwischen 0 und 3 mal. Außerdem darf sich die Anzahl der Würfe für benachbarte Münzen nur um 0 oder 1 unterscheiden. (Es gibt nur einen Zug, der geworfen wird$x$ und nicht $x + 1$und umgekehrt.) Um also alle T zu erhalten, muss die Anzahl der Flips entweder alle 0 oder alle 2 sein. Alle 0 sind nur mit dem leeren Zugsatz möglich. Was ist mit allen 2?

Die Gesamtzahl der Flips muss ein Vielfaches von 3 sein, da jeder Zug drei Münzen wirft. Es ist also unmöglich, alle 2 zu bekommen, es sei denn$N$ ist ein Vielfaches von 3. Wenn $N$ist ein Vielfaches von 3 ist es einfach. Jede Münze kann durch Bewegen in jede dritte Position geworfen werden. Dann können wir das Gleiche noch einmal tun, aber um 1 verschoben, um sie zurückzudrehen.

Jede Endposition ist also genau dann erreichbar, wenn$N$ist nicht teilbar durch 3.

Teil 2:

Wenn jede Position erreichbar ist, erreicht jeder Bewegungssatz eine andere Position. Insbesondere erreicht der Satz aller Bewegungspositionen eine bestimmte Endposition in$N$Bewegungen, und keine andere Position erfordert mehr als so viele Bewegungen. Diese bestimmte Position ist eigentlich alles H, da jede Münze dreimal geworfen wird.

Um den Zugsatz für eine bestimmte Endposition schnell zu berechnen, würde ich vorschlagen, zuerst den Zugsatz zu berechnen, der nur Münze 1 wirft. Dann wissen wir, wie man eine einzelne Münze wirft, indem man diesen Zugsatz verschiebt. Und dann können wir jedes Ergebnis berechnen, indem wir einzelne Münzbewegungssätze (mit symmetrischer Differenz / XOR) kombinieren.

Answer 2

Weniger "mathematischer" Ansatz:

Es ist offensichtlich, dass das Problem, eine beliebige Konfiguration zu erreichen, einer Reihe von Zügen entspricht, die genau eine Münze werfen.

Nun, wie man es findet:

Sie können die erforderliche Flip-Sequenz einfach mit der Sequenz 1,2,4,5,7, ... erstellen (die Zahlen entsprechen der Startmünze, 1 bedeutet das Umdrehen der Münzen 1,2,3). Dies wirft entweder Münze 2 (N = 3k + 1) oder N (N = 3k + 2). Die Konstruktion ist offensichtlich. Beginnen Sie mit Münze 1, die Sie beim ersten Zug als Köpfe festlegen, und drehen Sie den Rest um, sodass sich nur 1-2 Köpfe zum "Ende" des Kreises ausbreiten. Sobald diese Köpfe (fast) Ihren ersten treffen, führen Sie den letzten Flip durch. Mit N = 3k + 1 erhalten Sie einen Kopf am Ende und werfen am Ende nur Münze 2, mit N = 3k + 2 erhalten Sie einen Kopf 1 vor dem Ende und werfen nur Münze N. Mit N = 3k erhalten Sie 2 Münzen das Ende und erreichen alle Schwänze. Da Sie diese Münzen nicht "herausdrücken" können, um sie mit einem einzigen "Kopf" zu belassen, ist es nicht möglich, alle Konfigurationen zu erreichen.

Jetzt schlimmster Fall:

Um alle Köpfe zu erhalten, müssen alle Münzen 1 oder 3 Mal geworfen werden. Sie können natürlich nicht alle Münzen 1 Mal mit N = 3k + 1 oder 2 werfen lassen. Wenn eine Münze X 3 Mal geworfen wird, wurde die Münze X + 1 bereits 2 Mal geworfen und muss noch einmal geworfen werden usw. Sie müssen alle Münzen dreimal werfen, um alle Köpfe von den anfänglichen Schwänzen zu erhalten.