Variation von 100 Häftlingsnamen in Kisten

Question

100 Gefangenennamen in Kisten

Das folgende Puzzle ist eine Variation des obigen Puzzles.

Namen in Kisten

• Die Namen von 4 Gefangenen werden in 4 Holzkisten gelegt, ein Name in eine Kiste, und die Kisten stehen auf einem Tisch in einem Raum. Die Boxen sind mit 1,2,3 und 4 nummeriert.

• Die Namen werden zufällig platziert. Daher enthält Kasten 1 wahrscheinlich auch den Namen eines der vier Gefangenen. Gleiches gilt für die anderen Boxen.

• Nacheinander werden die Gefangenen in den Raum geführt; Jeder darf höchstens 2 Kisten einsehen, muss aber den Raum genau so verlassen, wie er ihn gefunden hat, und darf nicht weiter mit den anderen kommunizieren.

• Jeder Gefangene muss vor dem Betreten des Raumes herausfinden, welche 2 Kisten er öffnen wird. Sie können dann nur diese 2 Kisten öffnen.

• Die Gefangenen haben die Möglichkeit, ihre Strategie im Voraus zu planen, und sie werden sie brauchen, denn wenn nicht jeder einzelne Gefangene seinen eigenen Namen findet, werden alle anschließend hingerichtet.

• Mit welcher Strategie können sie ihr Überleben maximieren?

Answer 1

Ich denke die Antwort ist

Die ersten beiden Gefangenen wählen die ersten beiden Kisten, und die letzten beiden Gefangenen wählen die letzten beiden Kisten. Die Überlebenschance ist$1/6 \approx 16.7\%$.

Argumentation:

Stellen wir uns ein Diagramm mit vier Knoten und vier Kanten vor, wobei jeder Knoten eine Box darstellt und jede Kante die beiden von einem Gefangenen ausgewählten Boxen verbindet. Dann gibt es vier Knoten und vier Kanten, und eine Kante kann keine Selbstschleife sein.

Beachten Sie bei einem solchen Diagramm, dass ein Zyklus beliebiger Größe im Diagramm zwei Möglichkeiten bietet. Wenn beispielsweise drei Gefangene A, B, C die Felder 1-2, 2-3, 3-1 auswählen, gibt es zwei Fälle, in denen alle drei ihre eigenen Namen finden: ABC und CAB.

Wenn ein solcher Zyklus irgendwelche Zweige hat, erhöhen sie nicht die Gesamtüberlebensfälle: Zusätzlich zum letzten Beispiel, wenn D 1-4 wählt, gibt D im Wesentlichen die Chance auf, ihren Namen in Feld 1 zu sehen (seitdem einer von ABC wird seinen Namen sonst nie finden).

Wenn eine verbundene Komponente mehr Kanten als Knoten hat (z. B. D wählt stattdessen 1-2), sinkt die Überlebenschance auf Null, da sie nicht genügend eindeutige Kästchen haben, um alle ihre Namen zu finden.

Um die Überlebenschance zu maximieren, müssen die Gefangenen daher die Anzahl der disjunkten Zyklen in der Grafik maximieren, die zwei Zyklen mit jeweils zwei Knoten ergibt. Dann werden sie in vier Fällen aus überleben$4!=24$ Gesamtfälle geben $1/6$ Überlebenschance.