RauteMusik Forum

Wir haben heut von unserem Prof n Rätsel gestellt bekommen:

Also eine Diktatur, ein Herrscher, lauter Zwerge.
Die Zwerge können nicht untereinander kommunizieren (Wichtig!)
Einige der Zwerge haben einen roten Punkt auf der Stirn, es gibt keine Spiegel oder so.
Keiner weiß ob er einen roten Punkt auf der Stirn hat oder nicht.

Nun die Aufgabe des Herrschers:

Wenn die Zwerge es irgendwann schaffen, dass beim morgendlichen Apell alle Zwerge mit rotem Punkt einen Schritt nach vorne gehen, und alle ohne stehenbleiben, werden sie freigelassen.

Nach einigen Tagen treten alle Zwerge mit Punkt einen Schritt nach vorne, alle ohne bleiben stehen. Sie haben es also geschafft.

WIE konnten sie das machen, ohne zu wissen ob sie einen Punkt haben, ohne kommunizieren zu können?

Hab eine Lösung die noch nen kleinen Haken hat, aber vlt ist das nicht die gesuchte deswegen warte ich noch bevor ich auflöse, sofern es kein anderer macht (wovon ich ausgehe)

Antworten gibts per PM wenn ihr meinen Vorschlag wissen wollt :)

gruß

Meine Lösung ist auch net wirklich befriedigend:
Wenn wir die Zustände 1 und 0 für vorne und hinten festlegen, und die Zwerge zu Beginn in einer Reihe stehen, könnte man praktisch binär hochzählen bis zur max. Zahl. Irgendwann muss dann zufällig ne Richtige Kombi vorliegen.
Am ersten Tag stehen alle hinten, am zweiten Tag der erste vorne, dann der zweite, dann die beiden ersten usw... Iwann wäre man dann am Ziel, da alle Zustände iwann erfüllt werden müssen.

D.H. die Zwerge müssten mitrechnen, wissen welcher Tag grade ist und jeden Tag an einer bestimmten, bekannten Position stehen.

Das ganze dauert allerdings bis zu 2hochZWERGE Tage
Bei 5 Zwergen dauert das also schon bis zu 32 Tage, bei 6 64 usw..

Also is im durchschnittsfall nix mit "Nach einigen Tagen...", sondern...

vllt fällt mir ja noch was besseres ein...

jeder zwerk amcht sich einen roten punkt auf die stirn(edding hilft) un dann machen einfach alle einen schritt anch vorne

mh. auch interessat, Lukaro.
Weiß nicht ob das so gemeint ist, könnte natürlich sein.
Meine Lösung erscheint mir im moment aber noch einfacher :D

Hmmm also sag mal was heisst keine kommunikation für dich die einfachste möglichkeit für die zwerge sich zu retten , wenn man bei kommunikation allein von einer sprachlichen kommunikation ausgeht , ist das sie sich alle betrachten somit wissen schonmal alles wer einen roten punkt hat demnach ist es dann nicht mehr schwer für die zwerge sich bei der nächsten versammlung so hinzustellen das sie alle gleichzeitig vortreten können .. denke ich jetzt zu einfach ^^ wenn ja sags miir ruhig dann versuche ich mal was komplexeres auszutüfteln bloss ist es meistens so das bei solchen fragestellungen die einfachste lösung gesucht wird

an sich geht der gedankeen schon in die richtige richtung.
man muss wohl annehmen dass alle zwerge nen recht hohen IQ haben und die gleiche Idee, sonst funktioniert es auch nach meiner idee nicht :)

angenommen du selber hast einen roten punkt auf der stirn... woher weißt du das wenn du nicht nachschauen kannst und es dir keiner sagen/zeigen kann ?
trittst du nach vorne ? oder nicht ?

Deswegen ja meine frage was betrachtest du als kommunikation ist kommunikation im allgemeinen damit definiert oder gehts nur um die sprachliche kommuniktion

ich denke mal die zwerge sind taub, blind usw.
sie wissen aber natürlich alle um die gestellte aufgabe.

was für nen punkt haben die denn auf der stirn einen den man fühlen kann oder nicht??

wenn die zwerge nicht untereinander kommunizieren können, dann heißt das auch das sie sich nichts zeigen können ... sonst wäre es ja auch ein bischen zu leicht oder nicht?
Ich denke auch das es so geht wie Lucaro vorgeschlag. Also ist der maximale Aufwand 2^n ... wobei n die Anzahl der Zwerge ist.

das meine ich neet die können ja gegenseitig an der stirn fühlen bzw sich slber dann merken sies ja

Die Frage hat aber von einen Prof. gestellt worden. Und wenn das mit den fühlen die richtige Antwort sein soll, dann hätte er das auch in der Grundschule stellen können.
Außerdem, wenn ich dir ein Punkt auf die Strin male kannst du das fühlen ja?

Vllt gibts auch noch eine andere Möglichkeit. Aber ich glaube schon das die Aufgabenstellung so gemeint war, dass die Zwerge in keinster weise feststellen können ob sie eine Punkt haben oder nicht - nicht untereinander und auch nicht bei sich selbst.

Die Frage hat aber von einen Prof. gestellt worden. Und wenn das mit den fühlen die richtige Antwort sein soll, dann hätte er das auch in der Grundschule stellen können.

Hat es denn gleich viele Zwerge mit rotem punkt wie ohne?

Hat es denn gleich viele Zwerge mit rotem punkt wie ohne?

dei anzahl der zwerge mit bzw ohne Punkt ist nach meine Lösung nicht von Bedeutung :)

morgen bekommen wir die auflösung. dann kann ich sagen ob ich richtig lag oder nicht, und dann lös ich auch hier auf :)
meinen lösungsvorschlag hab ich schon einmal heute als PM verschickt, da könnt ihr dann nachfragen ob es meine Idee war oder nicht :D wenn ihr mir nicht glaubt ^^

Also wir hatten damals im ersten Semester in theoretischer Informatik eine ähnliche Aufgabe.
Zwerge mit roten und grünen Hüten sollten sich geordnet aufstellen. Also stellt sich der erste Zwerg hin (egal welche Farbe sein Hut hat). Dann kommt der zweite. Im dümmsten Fall haben beide unterschiedliche Hutfarben. Dann kommt der dritte. Der stellt sich genau zwischen die beiden. Und jeder der dazukommt stellt sich immer zwischen roten und grünen was zu einer Ordnung führt. Also wenn erst RRG und es kommt ein Grüner (G) dann stellt er sich zwischen R und G und es wird zu RRGG.
Wenn ich das auf dein Beispiel beziehe, ordnen die sich nach genanntem Muster. Der letzte weiß ja nicht zu welchen er gehört. Sollte er versehentlich stehen bleiben oder hervortreten macht er am nächsten Tag einfach das Gegenteil. Damit ist die effektive Laufzeit bis zur Terminierung höchstens 2 mal Morgenappell.
Stimmt so?

@aeMKei: also so isses auch möglich, seh zumindest keinen haken.

Meine Lösung wäre gewesen, dass sich alle (ungeordnet) nebeneinander aufstellen.
Von einer Seite (in meinem fall von rechts) läuft nun der äusserste zwerg so weit nach innen, bis er den letzten Zwerg MIT hut "überholt" hat und ordnet sich neben diesem ein. Dann kommt der nächste Zwerg ganz rechts aussen und macht das gleiche.
Auch so entsteht irgendwann eine Ordnung, und der erste Zwerg OHNE Punkt wird irgendwann nicht mehr überholt. Spätestens zu dem Zeitpunkt an dem der zuallererst gelaufene Zwerg das zweite mal von aussen nach innen geht, und den ohne Punkt wieder nicht überholt, ist eine klare Grenze zu erkennen.

Die Lösung von unserem Prof:

Vorraussetzung ist, dass mindestens ein zwerg einen Punkt hat.
Für den Fall dass es wirklich nur einen Zwerg mit Punkt gibt, sieht dieser , dass keine anderer nen Punkt hat. Weiß aber selber nicht was er hat und tritt auch nicht hervor. Weil aber auch kein anderer Hervortritt macht er genau das am nächsten Tag.
FÜr den Fall das es zwei Zwerge mit Punkt gibt, lläuft es am ersten Tag genauso wie vorher, ein Zwerg tritt hervor, weil er nen anderen Punkt sieht und selber keine schritt nach vorne macht. Weil sie aber nich freigelassen werden und er nur einen Punkt sieht schließt er daraus dass er selber einen haben muss und tritt am nächsten tag selber hervor.
Das lässt sich mit beliebig vielen Zwergen mit Punkt weitertreiben... irgendwann ist es halt so weit....

aber die Lösung von aeMKei gefällt mir am besten

Jupp aeMKei's Lösung ist die beste mit den geringsten Aufwand. Setzt aber auch vorraus, dass die Zwerge wissen, dass sie sich immer zwischen zwei verschiedenen stellen müssen ;)

Von der Lösung vom Prof. hätt ich aber mehr erwartet. Da müsstest du anubis ihn mal die Aufgabe geben, dass er dieses Rätsel lösen muss, mit höchstens 2 Morgeneppelle. ^^

ja, vorraussetzung ist halt dass jeder zweg die gleiche idee hat :)

werde den prof mal drauf ansprechen, jo