Farbe des Hutes erraten

Neue Frage »

Sherlock Holmes Auf diesen Beitrag antworten »
Farbe des Hutes erraten
Edit (mY+): Bitte auf bessere Titelwahl achten! Nichtssagener Titel wurde modifiziert!

Hier ist meiner Meinung nach ein schweres Rätsel:

Auf einer mysteriösen Insel werden 100 Studenten so in einer Reihe im Sand eingegraben, dass jeder alle Studenten weiter vorne, jedoch keinen der hinteren Studenten sieht. Nun bekommt jeder entweder einen schwarzen oder einen weissen Hut aufgesetzt, wobei niemand seinen eigenen Hut sieht. Beginnend beim hintersten Studenten, darf jeder der Reihe nach entweder "schwarz" oder "weiss" sagen, sodass dies alle anderen hören. Am Ende bekommt jeder, der die Farbe seines eigenen Huts genannt hat, eine Tafel Schokolade. Wie viele Tafeln können die Studenten insgesamt in jedem Fall erhalten, wenn sie sich vorher absprechen dürfen?
b) Wie sieht eine optimale Strategie für n Studenten aus, wenn es Hüte mit k verschiedenen Farben gibt?

Hinweis 1: Von jedem Studenten wird jeweils nur die Information, welche Farbe dieser genannt hat, an alle anderen übermittelt. Es ist beispielsweise nicht erlaubt, die Farbe schnell zu sagen, wenn der Nachfolger einen schwarzen Hut hat und sonst langsam.
Hinweis 2: Gesucht ist die Lösung, die für den "Worst Case" optimal ist. Die Lösung darf also nicht beginnen mit "Wenn man davon ausgeht, dass etwa die Hälfte der Hüte weiss ist..." Es könnten auch alle schwarz sein!

Schönen Gruß
10001000Nick1 Auf diesen Beitrag antworten »

Habe ich das richtig verstanden? Der hinterste Student sieht alle anderen außer sich selbst, und damit auch alle anderen Hüte. Wenn die Studenten sich absprechen dürfen, kann doch der hinterste Student allen anderen ihre Hutfarbe sagen.
Dann fängt der hinterste Student an mit der Farbe. Er hat eine 50:50-Chance. Alle anderen wissen jedoch schon ihre Farbe und können damit die richtige Farbe nennen. Also kriegen von 100 Studenten mindestens 99 eine Tafel Schokolade.

b) geht genauso, da kriegen (n-1) Studenten eine Tafel Schokolade.
weisbrot Auf diesen Beitrag antworten »

@nick:
Zitat:
Beginnend beim hintersten Studenten, darf jeder der Reihe nach [genau] entweder "schwarz" oder "weiss" sagen
lg
10001000Nick1 Auf diesen Beitrag antworten »

Hä? Das Wörtchen "Genau" bringt mich jetzt aber auch nicht weiter.
Ich glaub, du musst mir das mal genauer erklären. smile
Che Netzer Auf diesen Beitrag antworten »

Ich würde mal einwerfen, dass sich die Studenten vermutlich absprechen dürfen, bevor sie lebendig begraben werden.
10001000Nick1 Auf diesen Beitrag antworten »

Na gut, dann fällt mir jetzt spontan folgendes ein: Die Studenten einigen sich darauf: Jeder Student, der von hinten gesehen, an einer ungeraden Stelle liegt (also der 1., 3., 5., ... von hinten), sagt die Farbe von dem, der vor ihm liegt. Dann weiß, jeder, der an einer geraden Stelle von hinten liegt (also 2., 4., 6., ... von hinten), seine Farbe, da er ja alles hören kann. Damit können sie mindestens 50 Tafeln kriegen. Aber wahrscheinlich gibt es noch eine bessere Strategie.
 
 
HAL 9000 Auf diesen Beitrag antworten »

50 ist ein bisschen wenig, 99 sollten schon drin sein. Big Laugh

Zitat:
Original von Sherlock Holmes
b) Wie sieht eine optimale Strategie für n Studenten aus, wenn es Hüte mit k verschiedenen Farben gibt?

Das ist schon eine härtere Nuss. Die Frage ist, ob die aus a) adaptierte Strategie zumindest im Fall wirklich optimal ist. verwirrt
tmo Auf diesen Beitrag antworten »

Ich gebe mal eine Strategie zu a), wie man auf 99 Tafeln kommt. Die genauen Details, warum und wie das dann funktioniert, kann ja jemand anderes beisteuern.


Der hinterste Student kann ja durch seine Antwort 1 Bit Informationen an die anderen geben. Hört sich wenig an, ist jedoch als Paritätsbit genutzt Gold (bzw. Schokolade) Wert Augenzwinkern



Erweitert man diese Strategie für b), so erhält man ( vorrausgesetzt) mit Sicherheit Tafeln. Dass das für (also der Fall a) optimal ist, ist ja trivial.

Für größere ist das gar nicht klar. Z.b. ist ja für die banale Strategie, dass jeder zweite die Farbe seines Vordermannes nennt, schon besser.
HAL 9000 Auf diesen Beitrag antworten »

Hmmm, ich hatte bei der adaptierten Strategie auch daran gedacht, dass sich die ersten Leute "opfern", die nötigen Bit Information zu übertragen.

Da jeder dieser Leute durch die Nennung von einer aus Farben aber im Fall mehr als 1 Bit Information übermitteln kann, muss eigentlich nur erfüllt sein, d.h. , das macht dann

k m
2 1
3 2
4 2
5 2
6 2
7 3
8 3

Insgesamt springen daher mindestens Tafeln heraus. Aber auch da weiß ich nicht, ob das (für große ) optimal ist. verwirrt
Donquixote Auf diesen Beitrag antworten »

Könnte jemand vielleicht noch näher tmo's Strategie erläutern? Ich habe zwar nachgeschaut, was es ein Paritätsbit ist, aber sonderlich viel nicht herausgefunden und auch nicht wie der Zusammenhang zu dieser Aufgabe ist. Eine rein kombinatorische Lösung ohne Informatiksprache würde ich auch begrüßen.
Ich kann mir einfach nicht erklären, wie man auf min. 99 kommt. Ob 99 oder 100 liegt dann daran, ob der erste richtig rät, aber ab dann müssen ja schon alle anderen die richtigen Informationen besitzen.
Guppi12 Auf diesen Beitrag antworten »

Der letzte Student zählt die schwarzen Hüte vor sich und sagt je nachdem, ob die Anzahl vor ihm gerade oder ungerade ist, schwarz oder weiß. Was sieht jetzt der Student, der als nächstes dran ist vor sich (wieviele Schwarze Hüte), was kann er daraus für seinen eigenen Hut ableiten?
Donquixote Auf diesen Beitrag antworten »

Ah, okay, ich verstehe. Das ist natürlich clever
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »