Kleine Denkaufgabe

Fragen zu mathematischen Problemen
Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Kleine Denkaufgabe

Beitrag von Xin » Mo Feb 15, 2010 7:53 pm

Mal eine kleine Aufgabe, um einen Algorithmus zu formulieren. ^^

In einer Höhle stehen 100 Zwerge. Sie haben grüne oder rote Mützen auf.
Jeder Zwerg kann sehen, welche Farbe die Mützen der anderen Zwerge hat, aber sie können nicht miteinander kommunizieren und die Zwerge wissen nicht, welche Farbe ihre eigene Mütze hat.

Nun teilen sie sich in zwei Gruppen auf. Dafür verlässt ein Zwerg nach dem anderen die Höhle und nachdem der letzte Zwerg die Höhle verlassen hat, stehen alle Zwerge mit den grünen Mützen zusammen und alle Zwerge mit den roten Mützen.
Wie haben die Zwerge das gemacht?

Viel Spaß ;-)
Wer die Lösung hat, kann sie mir ja mailen. Falls sie stimmt, setze nenne ich die Person hier. Falls nicht, nenne ich den Ansatz und warum es nicht funktioniert ^^
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Kleine Denkaufgabe

Beitrag von Xin » Mo Feb 15, 2010 9:05 pm

AnGaiNoR war erster mit der korrekten Lösung.
Und es gibt eine Lösungsansatz, der wohl dazu führt, dass am Schluss 99 Zwerge vor dem letzten Zwerg gewissermaßen panikartig flüchten.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Kleine Denkaufgabe

Beitrag von Xin » Di Feb 16, 2010 10:35 am

Dirty Oerti ist dabei. ^^
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Kleine Denkaufgabe

Beitrag von Xin » Di Feb 16, 2010 10:48 am

> Habe da jetzt keinen Algorithmus ;)

Schade ^^

> Ich wüsste nicht wie das klappen sollte. Die ersten beiden Zwerge bilden 2
> Gruppen. Jeder Zwerg der jetzt raus kommt weiß nicht welche Farbe seine
> Mütze hat, weiß also auch nicht wohin er gehen soll. Von den draußen
> stehenden Zwergen kann er ja auch keine Hilfe erwarten. Die wissen es ja
> auch nicht besser. Sie wissen noch nicht einmal ob sie unterschiedliche
> Farben haben oder ob da gerade 2 Zwerge mit grünen Mützen stehen. Das weiß
> nur der 3. Zwerg...

So sieht die Sache aus.

> ohne Kommunikation geht bei den Zwergen leider nichts..

Doch, es gibt einen Handlungsablauf (=Algorithmus), den jeder Zwerg durchführen muss, so dass am Schluss zwei Gruppen von Zwergen entstehen.

> warum Panik erst bei
> dem 100. Zwerg ausbricht verstehe ich gerade nicht^^

Die Überlegung war, dass wenn ein Zwerg die Höhle verlässt, er sich zu einer beliebigen Gruppe stellt. Die Gruppe
kann die Mütze sehen und jeder Zwerg kann die Mütze der Leute in der eigenen Gruppe sehen. Also kann die Gruppe
entscheiden, ob sie da bleibt, oder vom Zwerg weggeht.
In der Lösung ging die Gruppe auf die andere Gruppe zu, woraufhin die andere Gruppe zum Zwerg ging.

Wenn die ersten Zwerge allerdings die Höhle verlassen, können sie nicht entscheiden, wann ein zweiter Zwerg
in die Gruppe kommt - oder eben nicht.
In der Lösung wird der Part mit 'am Anfang Chaos, aber das stabilisiert sich je mehr Zwerge da sind' übergangen.
Da sich nie stabile Gruppen bilden können, gehe ich davon aus, dass die Zwerge herumlaufen, da ein Zwerg
falsch steht, sobald er in einer invaliden Gruppe steht, er also mit zwei Zwergen zusammensteht, von denen einer
eine rote und eine grüne Mütze hat.

> Postest du die richtige Lösung noch oder schickst sie mir?

Mal schauen, es gibt jedenfalls eine Lösung.
Und einen Algorithmus sollte man als Entwickler schon entwerfen können ;-)

--
Mit freundlichen Grüßen
Sascha 'Xin' Atrops

It's a kind of fun to do the impossible.
(Walt Disney)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Kleine Denkaufgabe

Beitrag von Xin » Fr Mär 12, 2010 11:56 pm

Folgende Frage kam:

> eventuell bin ich in der Lage eine (sprachliche) Lösung zu entwickeln. Mir
> sagt der Begriff Algorithmus zwar etwas, jedoch die Lösung in Form eines
> solchen darzustellen - dazu fehlen mir wohl die speziellen Kenntnisse.

Übersetze Algorithmus als Kochrezept. Fülle Wasser in Topf, packe Topf auf Herd, mache Herd an, solange Wasser zu kalt warte, sonst fülle Nudeln rein.

> > .. sie können nicht miteinander kommunizieren ...
> Dürfen sich die Zwerge an der Hand nehmen und auch wieder loslassen?
> Ich würde das als Kommunikation auffassen - die Lösung der Aufgabe wäre so
> ziemlich simpel!

Kommunikation bedeutet, dass sie sich keine Informationen geben dürfen, bzw. Informationen übertragen können.
Kein Zwerg erzählt dem anderen, was er zu tun hat, bzw. regt einen anderen Zwerg an, eine selbstständige Handlung durchzuführen.
Zwerge handeln immer selbständig, ohne aktiv Einfluss auf andere Zwerge zu nehmen.

> das Einstellen dieser Anfrage ins Thema >Kleine Denkaufgabe< wäre wohl unpassend gewesen???

Nein, vielleicht hat jemand anderer die gleiche Frage?
Die Lösung ist hier unpassend. ^
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Kleine Denkaufgabe

Beitrag von Xin » Sa Mär 13, 2010 3:07 pm

cloidnerux wirft die korrekte Lösung per PM rein :-)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

melebele
Beiträge: 8
Registriert: Fr Feb 12, 2010 11:40 am
Wohnort: Zelt, z.Z Andalucía/España

Re: Kleine Denkaufgabe

Beitrag von melebele » Fr Mär 19, 2010 4:47 pm

Argumentation pro Sprache!
Die Aufgabe als solches, vielmehr aber die Formulierung derselben und der weitere Umgang veranlassten mich zum nachzudenken.
Wie wir sehen werden offenbart die Kleine Denkaufgabe noch eine andere Problematik. Es ist dies der dürftige sprachliche Ausdruck, insbesondere die unpräzisen Formulierungen (abgesehen von den Rechtschreibfehlern). Einige Beispiele und Kommentare zeigen auf, warum dies so unwichtig nicht ist.

100 motiviert handelnde Zwerge ohne Kommunikation und ein Handlungsort.
Easy - könnte man meinen! Eben nicht - zur Orientierung stelle ich hier eine (meiner Meinung nach) korrekt formulierte Version der Aufgabe vor.

+ In einer Höhle stehen 100 Zwerge – jedwede Art von Kommunikation ist ihnen unmöglich. Alle tragen entweder eine grüne oder eine rote Mütze - die Farbe der eigenen kennen sie nicht. Aber sie wollen (bezüglich der Mützenfarbe homogene) Gruppen bilden – deshalb verlässt ein Zwerg nach dem anderen die Höhle. Draußen sehen sie und formieren sich. Letztendlich stehen 2 Gruppen da. Wie haben die Zwerge das gemacht? +

Nun zum Original!
(aus Aufgabe) Xin hat geschrieben:Jeder Zwerg kann sehen, ...
Hier noch nicht! Falls sie denn Nachtsichtgeräte hätten auch nicht, denn dass man ihnen eine Kerze anmacht, davon ist keine Rede!
(aus Aufgabe) Xin hat geschrieben:Nun teilen sie sich in zwei Gruppen. Dafür ...
Falsch! Eine Gruppe definiert sich durch Übereinstimmung in mindestens einem Merkmal. In der Höhle haben wir es mit nichtsehenden Zwergen zu tun, also bestehen zu diesem Zeitpunkt noch keine Gruppen, sondern eine Gruppe (ID-Merkmal „Mützen“) mit dem Wunsch, Gruppen (ID-Merkmal „gleiche Mützenfarbe“) zu bilden!
(aus Aufgabe) Xin hat geschrieben:... und nachdem der letzte Zwerg die Höhle verlassen hat, stehen alle Zwerge mit den grünen Mützen zusammen und alle Zwerge mit den roten Mützen.
Hoppla! Quasi zeitgleich geht's ja nicht, zuerst muss noch die Zuordnung stattfinden. *
(aus Erfolgsmeldung AnGaiNoR) Xin hat geschrieben:Und es gibt eine Lösungsansatz, der wohl dazu führt, dass am Schluss 99 Zwerge vor dem letzten Zwerg gewissermaßen panikartig flüchten.
Kurios! * - denn Grenzfall Verteilung 99/1 ist durch die Formulierung der Aufgabe ausgeschlossen worden!
(aus Aufgabe) Xin hat geschrieben:Sie haben grüne oder rote Mützen auf... sowie ... nachdem der letzte Zwerg die Höhle verlassen hat, stehen alle Zwerge mit den grünen Mützen zusammen und alle Zwerge mit den roten Mützen.
(aus Reflexion) [i]Person inkognito[/i] und Xin hat geschrieben: >Ich wüsste nicht wie das klappen sollte. Die ersten beiden Zwerge bilden 2 Gruppen. ...

So sieht die Sache aus.
So sieht die Sache nicht aus! 2 Individuen können keine 2 Gruppen bilden - selbst Zwerge nicht. Noch nicht einmal eine Gruppe, höchstens ein Paar - wenn's denn passt. :?:
(aus Reflexion) Xin hat geschrieben:In der Lösung ging die Gruppe auf die andere Gruppe zu, woraufhin die andere Gruppe zum Zwerg ging.
Naja, das werden wir uns noch anschauen wollen! Für den Moment: eine Aufgabe ist zeitlos - also Verbform Präsenz.
(aus Reflexion) Xin hat geschrieben:In der Lösung wird der Part mit 'am Anfang Chaos, aber das stabilisiert sich je mehr Zwerge da sind' übergangen.
Meine Lösung kennt kein Chaos! Aber bekanntlich gibt's verschiedene Wege nach Rom.
(aus Reflexion) Xin hat geschrieben:Da sich nie stabile Gruppen bilden können...
Wie das?! Das Resultat ist doch die Bildung zweier stabiler (nämlich homogener) Gruppen - und diese gibt es auch schon während der Formierung - bzw. es kann sie geben!
(aus Reflexion) Xin hat geschrieben:Wenn die ersten Zwerge allerdings die Höhle verlassen, können sie nicht entscheiden, wann ein zweiter Zwerg in die Gruppe kommt - oder eben nicht.
Tinnef! Ein zweiter Zwerg bildet erstens keine Gruppe, dies bleibt einem dritten vorbehalten - so denn schon ein Paar besteht. Zweitens entscheidet nicht die Gruppe wann ein (weiterer) Zwerg kommt, das tut dieser.

Fazit! Die Erklärungsbemühungen und Missverständnisse hätten sich teilweise erübrigt so die Aufgabe klar formuliert worden wäre.
Die Beteiligung lässt zu wünschen übrig – ich enthalte mich der Spekulation über die Gründe!

Definition Gruppe ≥ 3 Individuen (mit ID-Merkmal)
Nur bei Königs hält man es mit Paaren oder Gruppen nicht so genau! :idea:

Grenzfallbetrachtung Grenzfälle sind für die Lösung irrelevant.
Eine differenzierte Grenzfallbetrachtung ist unnötig – Grenzfälle bestehen für die Zwerge als Handelnde (in Unkenntnis von solchen) ohnehin nicht.
Für den die Lösung der Aufgabe Suchenden bestehen (hypothetisch) 2 Grenzfälle - Verteilung 50/50 sowie 97/3 bzw. 3/97 - alle in Idealkonstellation nach den Regeln der Wahrscheinlichkeit unmöglich - also hier uninteressant.

Kleine Nebensache Zwerge tragen Kappen oder Hüte, Mützen passen vielleicht besser zu Dumpfnasen oder Tölpeln - ich kenne mich da nicht so aus. :shock:
Zuletzt geändert von melebele am Fr Mär 19, 2010 5:31 pm, insgesamt 4-mal geändert.
[color=#FFBF00]Corrigendum welcome[/color]
[color=#BFBFBF][i]... und immer schön locker bleiben![/color][/i] [size=125]©[/size]

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Kleine Denkaufgabe

Beitrag von Xin » Fr Mär 19, 2010 4:59 pm

melebele hat geschrieben:2 Individuen können keine 2 Gruppen bilden - selbst Zwerge nicht. Noch nicht einmal eine Gruppe, höchstens ein Paar - wenn's denn passt. :?:
Das scheint mir leicht zu widerlegen:
melebele hat geschrieben:Fazit! Die Erklärungsbemühungen und Missverständnisse hätten sich teilweise erübrigt so die Aufgabe klar formuliert worden wäre.
Die Beteiligung lässt zu wünschen übrig – ich enthalte mich der Spekulation über die Gründe!

Definition Gruppe gleich ≥ 3 Individuen
Ich vermute die Gruppe derer, die sich für diese ausführliche Erörterung interessierten beläuft sich auf unter 3 Personen. :->
Das wäre zum einen ich, der hierauf geantwortet hat, und zum anderen Wayne.

Ich glaube, wir haben unseren Foren-Clown gefunden. :lol:
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

melebele
Beiträge: 8
Registriert: Fr Feb 12, 2010 11:40 am
Wohnort: Zelt, z.Z Andalucía/España

Re: Kleine Denkaufgabe

Beitrag von melebele » Fr Mär 19, 2010 6:21 pm

> Das scheint mir leicht zu widerlegen:

Und die Widerlegung kommt noch?

> Ich vermute die Gruppe derer, die sich für diese ausführliche Erörterung interessierten beläuft sich auf unter 3 Personen. :->
> Das wäre zum einen ich, der hierauf geantwortet hat, und zum anderen Wayne.

a) Ich schaue in die Zukunft, Du in die Vergangenheit?
b) Also ein Paar (ID-Merkmal Interesse)? Du und Wayne.
c) Onkel Wayne hast Du wohl auf die Schnelle aus Deinem Fundus gekramt?

> Ich glaube, wir haben unseren Foren-Clown gefunden. :lol:

In einer individuellen Position habe ich mich schon immer sehr wohl gefühlt, einzig - meine Schullehrer und andere akzeptierten das kaum! Heute ist es mir aber ohnehin schnuppe!

Noch einen sachlichen Punkt: Zur Verfahrensweise - solange ein Beitrag noch zu "Ändern" ist könnte mit einer Einlassung gewartet werden, um Wirrwarr zu vermeiden - wie bereits geschehen!
[color=#FFBF00]Corrigendum welcome[/color]
[color=#BFBFBF][i]... und immer schön locker bleiben![/color][/i] [size=125]©[/size]

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Kleine Denkaufgabe

Beitrag von Dirty Oerti » Fr Mär 19, 2010 6:31 pm

Definition Gruppe ≥ 3 Individuen (mit ID-Merkmal)
Woher das? Bzw mit welcher Begründung?

Ansonsten sind das ja sehr genau, sprachliche Analysen..
--> Sprachwissenschaflter? :)
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Antworten