| Manfred Börgens Mathematische Probleme # 86 |
Liste aller Probleme mit Lösungen voriges Problem nächstes Problem |
zur Leitseite |
Behütete Gefangene Teil 2 → Teil 1
Hier kommt das zweite "Hüte-Problem". In Teil 1 ging es um zwei Gefangene, jetzt soll das analoge Problem für n Gefangene behandelt werden. Da es schwer ist, für beliebiges n ebensoviele Farben zu finden, nummerieren wir statt dessen die Hüte mit natürlichen Zahlen von 0 bis n-1 . Die konkrete Problemstellung lautet also:
n Gefangenen werden Hüte aufgesetzt; jeder Hut trägt eine der Zahlen 0 bis n-1 . Jeder kann nur die Hutnummern der anderen sehen, soll aber seine eigene erraten, ohne dass die Gefangenen Signale austauschen dürfen. Alle werden freigelassen, falls mindestens einer seine Hutnummer richtig angibt. Vor dem Aufsetzen der Hüte dürfen sich die Gefangenen über ihre Strategie beraten.
Was ist die optimale Strategie, mit der die Gefangenen ihre Freilassung erreichen?
Es lohnt sich, die Lösung von Teil 1 anzuschauen, denn sie lässt sich fast mühelos auf n Gefangene übertragen.
Wir betrachten die Situation zuerst aus der Sicht von drei Gefangenen. Diese sprechen eine Strategie ab, die sich an derjenigen von zwei Gefangenen orientieren soll. Hier ist die Analogie: Zwei Gefangene nehmen die Zweierreste der Summen der Hutnummern zu Hilfe, also liegt es nahe, dass drei Gefangene sich der Dreierreste bedienen. Das bedeutet, dass der Gefangene A von einem Dreierrest 0 , B von einem Dreierrest 1 und C von einem Dreierrest 2 ausgeht. Da die Summe der Hutnummern genau einen dieser Dreierreste aufweist, hat genau einer der Gefangenen recht.
Die drei Gefangenen können aus der Hutsumme der jeweils beiden anderen und dem von ihnen angenommenen Dreierrest ihre (vermutete) Hutnummer leicht berechnen. Sieht B beispielsweise zwei Hüte mit der Nummer 1 , so nennt er für seine eigene Hutnummer die 2 , da 1 + 1 + 2 modulo 3 = 1 ergibt.
Diese Strategie lässt sich tabellarisch darstellen:
| vorh. A |
vorh. B |
vorh. C |
Entsch. A |
Entsch. B |
Entsch. C |
richtige |
||
| 0 | 0 | 0 | 0 | 1 | 2 | 1 | ||
| 0 | 0 | 1 | 2 | 0 | 2 | 1 | ||
| 0 | 0 | 2 | 1 | 2 | 2 | 1 | ||
| 0 | 1 | 0 | 2 | 1 | 1 | 1 | ||
| 0 | 1 | 1 | 1 | 0 | 1 | 1 | ||
| 0 | 1 | 2 | 0 | 2 | 1 | 1 | ||
| 0 | 2 | 0 | 1 | 1 | 0 | 1 | ||
| 0 | 2 | 1 | 0 | 0 | 0 | 1 | ||
| 0 | 2 | 2 | 2 | 2 | 0 | 1 | ||
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | ||
| 1 | 0 | 1 | 2 | 2 | 1 | 1 | ||
| 1 | 0 | 2 | 1 | 1 | 1 | 1 | ||
| 1 | 1 | 0 | 2 | 0 | 0 | 1 | ||
| 1 | 1 | 1 | 1 | 2 | 0 | 1 | ||
| 1 | 1 | 2 | 0 | 1 | 0 | 1 | ||
| 1 | 2 | 0 | 1 | 0 | 2 | 1 | ||
| 1 | 2 | 1 | 0 | 2 | 2 | 1 | ||
| 1 | 2 | 2 | 2 | 1 | 2 | 1 | ||
| 2 | 0 | 0 | 0 | 2 | 0 | 1 | ||
| 2 | 0 | 1 | 2 | 1 | 0 | 1 | ||
| 2 | 0 | 2 | 1 | 0 | 0 | 1 | ||
| 2 | 1 | 0 | 2 | 2 | 2 | 1 | ||
| 2 | 1 | 1 | 1 | 1 | 2 | 1 | ||
| 2 | 1 | 2 | 0 | 0 | 2 | 1 | ||
| 2 | 2 | 0 | 1 | 2 | 1 | 1 | ||
| 2 | 2 | 1 | 0 | 1 | 1 | 1 | ||
| 2 | 2 | 2 | 2 | 0 | 1 | 1 |
Wir wollen diese Strategie formelmäßig darstellen, damit sie sich leicht auf n Gefangene verallgemeinern lässt:
Drei Gefangene tragen Hutnummern nA , nB , nC ∈ {0,1,2}.
A tippt auf (nA + nB + nC) mod 3 = 0 ⇔ A tippt auf nA + nB + nC = j·3 ⇔ A nennt als eigene Hutnummer mA = (-nB - nC) mod 3
B tippt auf (nA + nB + nC) mod 3 = 1 ⇔ B tippt auf nA + nB + nC = 1 + j·3 ⇔ B nennt als eigene Hutnummer mB = (1 - nA - nC) mod 3
C tippt auf (nA + nB + nC) mod 3 = 2 ⇔ C tippt auf nA + nB + nC = 2 + j·3 ⇔ C nennt als eigene Hutnummer mC = (2 - nA - nB) mod 3
genau einer hat recht ↑ genau einmal gilt m.. = n.. ↑
| Lösung
n Gefangene mit den Namen #k (k = 0 ... n-1) tragen Hutnummern nk ∈ {0 ... n-1} . #k tippt auf Σi=0..n-1 ni mod n = k ⇔ #k tippt auf Σi=0..n-1 ni = k + j·n ⇔ #k nennt als eigene Hutnummer mk = k - Σi=0..n-1,i≠k ni mod n , d.h. er subtrahiert von seiner Namens-Nummer die Summe der Hutnummern seiner Mitgefangenen → das Ergebnis E ist um mk größer als die nächstliegende durch n teilbare Zahl j·n ≤ E → er nennt mk als seine Hutnummer Genau einer hat recht, d.h. nk = mk für genau ein k . Alle Gefangenen werden freigelassen. |
Quelle: Winkler, P.: Numbers on Foreheads, in: Mathematical Mind-Benders, A. K. Peters 2007
Publiziert 2014-04-08 Stand 2013-01-05
voriges Problem | Liste aller Probleme mit Lösungen | nächstes Problem