Sommer der Rätsel / Zwergenmützchen

By Michael Bechmann Date 2016-08-27 13:03 Edited 2016-08-27 13:05

Das ist nicht konkret genug beschrieben.

Ich gehe davon aus, dass die Zwerge wieder in Einzelhaft gehalten werden. Ansonsten könnte man einen der anderen fragen, welche Mütze man aufhat. Ob er die Wahrheit sagt, ist eine anderes Problem.

Noch einfacher: Man sieht einfach mal selber nach. Sie hocken doch hoffentlich nicht im Dunkeln.

By Wolfram Bernhardt Date 2016-08-27 13:06

Sie können, sollen und dürfen nicht kommunizieren. Also nicht sprechen und auch keine wilden Gesten machen.

Sie kommunizieren einfach gar nicht miteinander.

Und sie sollen auch nicht selber nachschauen.

Warum, weiss ich nicht. Oder.. weiss ich doch: Weil das Rätsel sonst zu einfach wäre

By Ingo Althöfer Date 2016-08-27 13:38

Hallo,

Wolfram Bernhardt schrieb:

Sie können, sollen und dürfen nicht kommunizieren.
Also nicht sprechen und auch keine wilden Gesten machen.

Und ganz wichtig: Nachdem der einzelne Zwerg in die Arena gekommen ist,
stellt er sich passend hin und ändert danach seine Position nicht mehr.

Ingo A.

PS. Für nichtfarbenblinde Zwerge ist die Aufgabe einfach

By Frank Brenner Date 2016-08-27 13:31

Leider kenne ich das rätsel schon.

Bin aber immer auf der suche nach neuen, sehr schweren Rätseln.

Das mit den 97 Gefangenen habe ich per Zufall ein paar Stunden bevor ich es gepostet hab gefunden. Die Story natürlich umgeschrieben damit eine Google Suche nicht bereits adhoc einen Treffer liefert.

By Ingo Althöfer Date 2016-08-27 13:48 Upvotes 1

Hallo Herr Brenner,

Frank Brenner schrieb:

... Bin aber immer auf der suche nach neuen, sehr schweren Rätseln.

Dann sollten Sie mal Kontakt zur Rätselszene aufnehmen: Bernd Seckinger und Roland Voigt sind zwei
der zentralen Namen dort.

Mit Seckinger wollte ich mal ein Buch zusammen schreiben. Er hatte aber keine Zeit und verwies
mich an Roland Voigt. Das Ergebnis war "Spiele - Rätsel - Zahlen", erschienen 2014
im Springer-Spektrum-Verlag. Mir wurde durch das Buchprojekt erst klar, wie gross
in Deutschland die Szene für Logikrätsler ist.

Ingo Althöfer.

By Michael Bechmann Date 2016-08-28 00:50 Edited 2016-08-28 01:04

Da empfehle ich das Buch mit dem sonderbaren Namen "Die Hühnchen von Minsk".

Da werden 100 teilweise brutale Probleme dargestellt, die man nicht mit Grundrechnungen lösen kann und fast immer auch fundierte physikalische Kenntnisse haben muss.

"https://www.amazon.de/Die-H%C3%BChnchen-von-Minsk-Probleme/dp/3499603632/ref=sr_1_1?ie=UTF8&qid=1472338089&sr=8-1&keywords=Die+H%C3%BChnchen+von+Minsk"

By Frank Brenner Date 2016-08-28 01:15

Hast du das Buch denn ?

Wenn ja könntest du ja einmal hier eine Kostprobe geben.

By Michael Bechmann Date 2016-08-28 01:55

Ja. Eine mathematische Aufgabe 8ohne phyisikalische Apekte) - ich stelle sie in einem separaten Diskussion vor.

By Michael Bechmann Date 2016-09-04 01:52

Hallo,

Ich habe euch vielleicht mit dem Link zu dem anderen Buch abgelenkt?

Das wollte ich eigentlich nicht.

Wie ist denn das Problem mit den Zwergenmützen nun? Das ist inzwischen ganz in Vergessenheit geraten.

By Wolfram Bernhardt Date 2016-09-04 12:45

Das stimmt.
Die Lösung hatte ich auch noch gar nicht gepostet, weil es nur weniger Lösungsversuche gab.

Aber Ingo (Althöfer) hat mir eine vollständig richtige Lösung als persönliche Nachricht geschickt.

Viele Grüße,
Wolfram

By Peter Martan Date 2016-09-04 12:54 Edited 2016-09-04 13:02

Hallo Wolfram!
Danke für das Rätsel, ich hoffe, es macht dir nichts aus, dass ich einen Link zu einer anderen Quelle gesetzt habe in meinem Vorposting, hauptsächlich, weil ich die Formulierung der Aufgabe dort recht witzig fand teilweise.
Aber ich hab damit ja noch nichts direkt verraten, und du wirst die Lösung ja jetzt dann ohnehin bald selbst preisgeben, hatte ich gedacht.

By Peter Martan Date 2016-09-04 12:50

Michael Bechmann schrieb:

Das ist inzwischen ganz in Vergessenheit geraten.

Ja, so sind die Leute, immer verlieren sie gleich wieder das Interesse.

Ich nehme aber mal an, dass in diesem Fall das Rätsel mit Google so leicht im Netz zu finden war, dass dadurch selbst unter vielleicht vielen Interessierten, die es noch nicht kannten, sich ihre eigene Lösung bald bestätigen oder es sich auch gleich auflösen haben lassen, ich gehörte zu den Letzteren, weil ich mal wieder zu ungeduldig war.

Wenn jemand allein weiter grübeln will, muss er ja aber z.B. diesen Link hier

http://www.oliverschneider.net/ojemine/raetsel/logik/zwerge.htm

nicht anklicken und hat dann, selbst wenn er die Aufgabe dort noch einmal gelesen hat, immer noch die Wahl, auf "Lösung" zu klicken oder nicht.

Hingegen fand ich in dieser Formulierung der Aufgabenstellung die Sache mit dem ausdrücklichen Ausschließen von Rotmützen scheuchenden Stieren und der Voraussetzung der Unterlichtgeschwindigkeit ganz witzig, mit der sich die Zwerge bewegen, sodass sie sich auch nicht selbst beim Verlassen der Höhle beobachten können.

By Wolfram Bernhardt Date 2016-09-04 13:03

Hallo!

Kein Problem. Die dort angegebene Lösung ist die, die ich auch kenne und im Kopf hatte:

Die ersten beiden Zwerge stellen sich einfach nebeneinander.
Jeder weiter sieht, ob es eine Stelle gibt, an der eine grüne Mütze auf eine rote stößt. Wenn ja, stellt er sich zwischen die unterschiedlichen Mützenfarben. Dadurch entsteht eine neue "Umbruchstelle" auf einer Seite neben ihm und das ist der Platz für den nächsten Zwerg usw.

(Solange nur Zwerge mit der derselben Mützenfarbe in der Reihe stehen, stellt sich ein nächster Zwerg einfach an den linken ode rechten Rand).

Viele Grüße,
Wolfram

By Michael Bechmann Date 2016-09-04 16:48 Edited 2016-09-04 17:05

Lösung: "3. Dritter Zwerg geht raus und schaut:

a) stehen zwei gleichfarbige Zwerge da, stellt er sich links oder rechts daneben.
b) stehen zwei unterschiedlich farbige Zwerge da, stellt er sich dazwischen."

Prof. Althöfer hat geschrieben, dass die Zwerge ihre Positionen nicht mehr ändern dürfen. Sie müssten aber beiseite treten, wenn ein anderer "dazwischen" muss.

By Peter Martan Date 2016-09-04 18:21

Naja, das ist schon irgendwie eine kleine Schwachstelle, fand ich auch.
Dass die Nachbarzwerge irgendwann, wenn mehr und mehr Andere zwischen sie treten, ausweichen müssen, könnte man als "einander gegenseitig umsortieren" interpretieren, und das darf ja eigentlich nicht sein, im Link ist es ausdrücklich verboten und eine Form der "Kommunikation miteinander" ist es wohl auch irgendwie.
Aber soo genau darf man's bei Rätseln selten nehmen, schreibt man all das in die Aufgabenstellung hinein, was als Ausnahmen von Regeln auch gelten könnte, kann man's meistens auch gleich auflösen. Hier würde es sicher sofort die entscheidende Spur legen.

By Wolfram Bernhardt Date 2016-09-05 13:40

Wenn sie ganz schlau sind und viel Platz haben, stellen sie sich von Anfang an gaaaaanz weit weg voneinander auf

By Frank Brenner Date 2016-09-05 13:48 Edited 2016-09-05 13:53

Es reicht wenn die Zwerge ihre Bäuche einziehen können:
Dann stellen sie sich einfach auf rationale Positionen. Dort gibt es stets noch beliebig viele rationale Zwischenräume.

Der erste auf 0 , der zweite auf 1 und alle anderen dazwischen und es braucht nie jemand seine Position zu ändern.

By Peter Martan Date 2016-09-06 08:42 Edited 2016-09-06 08:44

Ist schon gut, eine Reihe, so wie man sie sich im Allgemeinen vorstellt, wird das halt nicht, es wird eine Zwergenansammlung in irgendeiner schiefen Mitte, die wahrscheinlich nicht einmal die Mitte ist, (nach dem ersten, der zwischen zwei andere hineintritt, kommen genau dort auch alle anderen restlichen Zwerge hinein) an diesem rationalen Ort häufen sich die Zwerge mit den eingezogenen Bäuchen, und an den "Enden" der Reihe verlieren einzelne einsame Zwerge die anderen aus den Augen.

Außerdem stellt sich der unbedarfte Rätselfreund natürlich vor, es werden zum Schluss zwei irgendwie getrennte Zwergengruppen, Reihen oder Haufen sein, in Wirklichkeit ist es eine geschlossene (je nach Rationalität der Orte) Reihe von Zwergen, die irgendwo von rot zu grün wechselt, und der letzte arme Zwerg weiß nach wie vor nicht, ob er jetzt eine rote oder grüne Haube auf hat, so lange es ihm keiner sagt oder deutet, oder er endlich sein blödes Mützchen abnimmt und nachschaut.
Als Ästhet befriedigt mich die Lösung irgendwie einfach nicht so richtig, aber ich bin selten mit Lösungen zufrieden, die ich nicht selbst finde.

By Frank Brenner Date 2016-09-07 16:45 Edited 2016-09-07 16:47

Hi Peter,

Der letzte Zwerg schubst einfach einen der beiden Zwerge an der Übergangstelle um und nimmt dessen Platz ein. Jenachdem wo sich der umgefallene Zwerg wieder einreiht kann der letzte Zwerg so auch seine Farbe ermitteln.

Es passiert oft bei Logikrätseln, daß anschließend nicht die vollständigen Informationen vorliegen, sondern gerade so eben diejenigen die so eben ausreichen um das Rätsel zu lösen.
So kannst du zb aus 13 Kugeln durch 3 mal wiegen mit einer Balkenwage herausfinden welche Kugel leichter oder schwerer ist, falls eine Kugel ein unterschiedliches Gewicht hat als die anderen. Aber du kannst nicht feststellen ob diese schwerer oder leichter ist. Hierzu würdest du mindestens in einem Fall einen vierten Versuch benötigen.
Bei 12 Kugeln kannst du bei 3 Versuchen auch herausfinden ob diese schwerer oder leichter ist.

Bei dem Götter-Lügen Rätsel von vor ein paar Jahren kannst du zwar ermitteln welcher Gott immer die Wahrheit erzählt, immer lügt, oder manchmal die Wahrheit sagt; du kannst aber mit 3 Fragen nicht noch zusätzlich ja und nein in die Göttersprache übersetzen.

Grüße
Frank

By Ingo Althöfer Date 2016-09-08 10:14

Liebe Leute,

jetzt habe ich mir auch ein paar Gedanken zur praktischen Realisierung
der Lösung (der neue Zwerg stellt sich an den Trennpunkt der beiden Farben)
gemacht. Es gibt da ein Problem, zumindest wenn sich die Zwerge nicht mehr
bewegen dürfen, nachdem sie sich hingestellt haben.

Wolfram Bernhardt schrieb:

... Es geht um eine Höhle voller Zwerge, von denen jeder
entweder ein grünes oder ein rotes Mützchen trägt. Keiner der Zwerge
weiss, welche Farbe seine eigene Mütze hat, aber die Farber der anderen
kann jeder sehen.
Einmal im Jahr haben sie ihr großes Ordnungsfest, bei dem sie sich vor
der Höhle in einer Reihe aufstellen, in der auf in einem Abschnitt alle
grünmützigen Zwerge zusammenstehen und in anderen alle rotmützigen.
Dazu kommen sie einzeln, einer nach dem anderen aus der Höhle und
stellen sich an beliebiger Position in die Reihe...

Angenommen, jeder Zwerg hat einen Durchmesser von 1 cm.
Dann braucht man bei n Zwergen als Gesamtlänge für die Reihe
2 + 2-hoch-(n-2) - 1 cm.

Beispiel mit 100 Zwergen: man braucht 2 + 2^98 - 1 = 2^98 + 1 cm.

Der Beweis funktioniert mit Induktion in n.
Induktionsanfang bei n=3: Die ersten beiden Zwerge müssen 1 cm zwischen sich freilassen.
Gesamtbedarf also 2 + 1 = 2 + (2^1 - 1)=3.
Induktionsschritt: Wenn nach dem aktuell auftretenden Zwerg noch k weitere kommen,
muss er sich in eine Lücke stellen, so dass danach noch rechts und links von ihm jeweils
2^k -1 cm Platz ist.

Also taugt die schöne/ideale Lösung nicht für den wirklichen Alltag.

Ingo Althöfer.

By Peter Martan Date 2016-09-08 12:08

Danke sehr, lieber Herr Professor!

By Wolfram Bernhardt Date 2016-09-08 14:34 Edited 2016-09-08 15:20

Hallo Ingo!

Ingo Althöfer schrieb:

Angenommen, jeder Zwerg hat einen Durchmesser von 1 cm.
Dann braucht man bei n Zwergen als Gesamtlänge für die Reihe
2 + 2-hoch-(n-2) - 1 cm.

Induktionsanfang bei n=3: Die ersten beiden Zwerge müssen 1 cm zwischen sich freilassen.
Gesamtbedarf also 2 + 1 = 2 + (2^1 - 1)=3.

Ach... das ist ja interessant. Ich bin aber nicht sicher, ob das für n= 3 stimmt. Die ersten beiden lassen eine Lücke, okay. Jetzt haben sie beide diesselbe Farbe auf, rot. Der Dritte kann sich nur links oder rechts daneben stellen, und braucht man 4cm Platz.
In die Mitte kann sich der Dritte ja nicht stellen, da er seine Farbe nicht kennt und mit grün die rote Reihe stören würde.

Noch etwas anderes zum ursprüngliche Rätsel, das mir gerade eben erst aufgefallen ist:
In dem Moment, da ein Zwerg sich zwischen andere Zerge stellt - nennen wir ihn "Drängelzwerg" - wissen plötzlich alle schon postierten Zwerge - bis auf den Drängelzwerg selber - sofort ihre eigene Farbe.
Jeder schaut einfach von sich zum Drängelzwerge und die Farbe, die jenseits des Drängelzwergs liegt, hat man nicht.

Viele Grüße,
Wolfram

By Ingo Althöfer Date 2016-09-08 15:22

Hallo Wolfram,

Wolfram Bernhardt schrieb:

Ach... das ist ja interessant. Ich bin
aber nicht sicher, ob das für n= 3 stimmt.
Die ersten beiden lassen eine Lücke, okay. Nun haben sie beide
diesselbe Farbe auf, rot. Der Dritte kann sich nun nur ...

Stimmt. Die 2 hoch n-2 sind nur eine untere Schranke für den Platzbedarf.

Zitat:

Noch etwas anderes zum ursprüngliche Rätsel, das mir gerade eben erst aufgefallen ist:
In dem Moment, da ein Zwerg sich zwischen andere Zerge stellt - nennen wir ihn "Drängelzwerg" -
wissen plötzlich alle schon postierten Zwerge - bis auf den Drängelzwerg selber - sofort
ihre eigene Farbe.

In der Tat. Die Nachbarn des Neudränglers wissen Bescheid, weil sie seine
Positions-Strategie kennen.

******************************************************************************
Spannend ist übrigens die 3-Farben-Variante des Problems in
der zweidimensionalen Ebene. Seien die Farben rot, grün und blau.
Am Ende sollen die Zwerge so stehen, dass in der konvexen Hülle
der roten Zwerge kein grüner oder blauer steht, usw.

Die Strategie ist ähnlich wie bei Bicolor: Der Drängelzwerg quetscht sich
an die "eindeutige" Stelle, wo die drei Farben aufeinander treffen.

Wieviel Platz müssen die Zwerge hier einkalkulieren, wenn nie einer
weggestupst werden soll?

Ingo.

By Ingo Althöfer Date 2016-09-09 14:34

Hallo Ingo,

Ingo Althöfer schrieb:

Stimmt. Die 2 hoch n-2 sind nur eine untere Schranke für den Platzbedarf...
***************************************************
Spannend ist übrigens die 3-Farben-Variante des Problems in
der zweidimensionalen Ebene. Seien die Farben rot, grün und blau.
Am Ende sollen die Zwerge so stehen, dass in der konvexen Hülle
der roten Zwerge kein grüner oder blauer steht, usw.

Die Strategie ist ähnlich wie bei Bicolor: Der Drängelzwerg quetscht sich
an die "eindeutige" Stelle, wo die drei Farben aufeinander treffen.
Wieviel Platz müssen die Zwerge hier einkalkulieren, wenn nie einer
weggestupst werden soll?

Man bekommt eine untere Schranke von 3 hoch (n-3), wenn man
den Idealfall annimmt, dass die ersten drei Zwerge alle verschiedene
Farben haben und ein gleichseitiges Dreieck bilden:

Der neue Zwerg besetzt den Schwerpunkt des Dreiecks. Dadurch entsteht
genau ein neues (kleineres) Dreieck, in dem die drei Ecken verschiedene
Farben haben. Die Fläche dieses Dreiecks ist 1/3 der Fläche des vorherigen
"bunten" Dreiecks. Im nächsten Schritt passiert das Gleiche.
Insgesamt verringert sich die Fläche des eindeutigen bunten Dreicks jedes
Mal um den Faktor 3.

*******************************************
Noch allgemeiner: Bei Zwergen in 4 Farben muss man in 3-D gehen.
Hier ergibt sich eine untere Schranke von 4 hoch (n-4). Dazu nimmt
man wieder den Idealfall an, dass die ersten vier Zwerge alle verschieden-
farbig sind und ein gleichseitiges Tetraeder bilden. Der nächste Zwerg
geht in den Schwerpunkt, und das neue "vollbunte" Tetraeder hat ein
Viertel der Fläche seines Vorgängers...

Es gibt übrigens einen Querbezug zum Beweis von Brouwers Fixpunktsatz
mit Hilfe des Lemmas von Sperner.

Ingo Althöfer.

PS. Hab ich gerade mit mir selbst kommuniziert?

By Wolfram Bernhardt Date 2016-09-09 16:04

Ingo Althöfer schrieb:

PS. Hab ich gerade mit mir selbst kommuniziert?

Scheint so - aber ich höre Euch gerne zu

Ich habe gerade Eindruck, dass man im 2d beliebig viele Farben voneinander trennen kann.
Das ist aber schwer zu erklären, ich mache dazu nachher mal ein Zeichnung. (Vielleicht merke ich dann, dass ich falsch liege)

(Streng genommen würde es die Sache erleichtern, wenn die Zwerge die Ausdehnung eines handelüblichen Punktes haben würden, aber das Prinzip müsste auch so zu erkennen sein.)

By Wolfram Bernhardt Date 2016-09-09 16:27 Edited 2016-09-09 16:35

Okay, hier mein Idee, mit 6 Farben:

Zu sehen ist ein fortgeschrittenes Stadium der Ordnerei von oben; jede der bunten Linien repräsentiert eine Reihe gleichfarbig bemützter Zwerge.
In der Mitte steht ein Oranger, der als letzter dazugekommen ist.
Unten rechts steht ein blauer Zwerg, der nun an der Reihe ist und seine Farbe nicht kennt. Aber er sieht die anderen.
Er schubst den orangenen Punkt nach links unten, dorthin, wo die orangene Reihe beginnt und stellt sich selber in die Mitte. Usw.

Daraus kann jetzt erkennen, dass sich die ursprüngliche Lösung auch so formulieren lässt:
- Jeder neue Zwerg schubst (ordnet) den direkt vorhergehenden in dessen farblich passende Farb-Reihe.
- Existiert noch keine Farb-Reihe für einen zu schubsenden Zwerg, wird er in eine Richtung geschubst, in der noch keine Reihe steht; damit wird eine neue Farb-Reihe eröffnet.

Das klappt für beliebig viele Farben, denke ich.

Aber: Wenn man es so betrachtet stellt das das ursprünglich Rätsel infrage, denn es hiess "keinerlei Kommunikation". Einen anderen Zwerg aber in eine bestimmte Richtung zu drücken, muss man eigentlich als Kommunikation ansehen.

Oh weh, jetzt ist das Rätsel kaputt.

Trotzdem wird es immer interessanter.

Viele Grüße,
Wolfram

PS: Und nein, ich weiss nicht, wie man das Bild kleiner darstellen kann.

By Michael Bechmann Date 2016-09-09 22:14 Edited 2016-09-09 22:28

So wie etwa auf dem Bild denke ich nach 2 Bier auch. Ich würde die Zeichnung zu eine moderne Ausstellung schicken und ein maßgeblicher Preis wäre damit gesichert.

aber nun etwas mathematischer: Mit mehr als 2 Farben wird die Lösung komplexer - aber wie wäre die Lösung, wenn die Zwerge keine bunten Mützen hätten sondern eine bestimmte Zahl von 1 bis 1000 (oder beliebig höhere Zahl>1000) und die Zwerge sollen die Zahl auf der eigenen Mütze ermitteln?

Wie gruppieren sich die Zwerge dann? Und wie viel Platz muss man auf der Zwergenwiese reservieren?
Ich habe gestern schon über die 2^98 cm für nur 100 Zwerge und nur 2 Farben gestaunt und versuchte mir, die mir vorzustellen. Das wären etwa 300 Milliarden Lj...

By Frank Brenner Date 2016-09-10 14:48 Edited 2016-09-10 14:52

Hallo Wolfram,

du bist ja der Threadersteller und hast das Rätsel initial gestellt.

Man könnte das Rätsel mit k Farben und n Zwergen noch weiter verwässern:

Alle Zwerge laufen beliebig nach draussen und der letzte Zwerg sortiert alle n-1 zwerge in der Form eines runden Kuchens mit k Kuchenstücken und stellt sich in die Mitte.

Diese Variante ist aber langweilig.

Wesentlich spannender ist aber die Variante wo überhaupt keinerlei Korrektur des Standortes eines Zwerges mehr angewendet werden darf. Dh der zwerg läuft nach draussen, sucht sich eine Position aus und bleibt dort für immer stehen.

Dann gibt es die einfache Lösung bei zwei Farben, dass sich die Zwerge auf positionen mit ganzrationalen Zahlenwerten aufstellen dürfen und sich selbst dabei beliebig klein machen können. Dann passen alle n Zwerge auf einen Meter.

Wenn die Zwerge aber ihre Bäuche nicht beliebig einziehen können, dann müssen die Zwerge von vorneherein einen genügend großen Abstand wählen damit in JEDEM FALL alle restlichen Zwerge dazwischen Platz haben ohne sich kleinfalten zu müssen.
Das Rätsel in dieser Variante ist am schwierigsten und vor allem am spannendsten.

Grüße
Frank

By Peter Martan Date 2016-09-09 18:57

Ingo Althöfer schrieb:

PS. Hab ich gerade mit mir selbst kommuniziert?

Für einen Beautiful Mind ganz normal.

By Frank Brenner Date 2016-09-10 14:33 Edited 2016-09-10 15:15

Hallo Herr Althöfer.

möglicherweise können wir die untere Schranke noch anheben:

Wenn ein Zwerg eine Standfläche von 1cm x 1cm (kurz 1) hat, dann ist nicht die Größe der Gesamtfläche des Dreiecks relevant, denn was nützt ein Dreieck mit der Fläche 12 , wenn die kleinste der drei Höhen nur 1/3 beträgt ?

Der Zwerg lässt sich nur ein bißchen drücken: Wenn die kleinste Höhe eines Dreiecks mindestens 1 ist, so soll er sich noch so gerade in der Mitte des Dreiecks aufhalten können.

Wenn wir einmal annehmen es kommt zuerst ein roter, grüner und ein blauer, so dass diese drei ein gleichseitiges 3-Farben Dreieck bilden.

Anschließend kommen alle anderen Zwerge. Dabei wird das Dreieck im wesentlichen jeweils gedrittelt. Aber wie verändert sich die Höhe des immer kleiner werdenden 3-Farben Dreiecks im Laufe der Zeit ?

Die Seitenhalbierende schneiden sich im Verhältnis 1:2 , d.h. im ersten Iterationsschritt wird die minimale Höhe des dreiecks gedrittelt.

In einer Simulation mit einem Programm habe ich herausgefunden, dass im Durchschnitt die minimale Höhe sich durch 2 teilt, bei einer Gleichverteilung , d.h. wenn die Zwerge in der Höhle gut durchgewürfellt wurden und es von jeder Farbe gleich viele gibt.
Im worst-Case, d.h. wenn ab dem vierten Zwerg nur noch rote kommen, dann drittelt sich im Durchschnitt die minimale Höhe mit jedem weiteren Zwerg.

Nehmen wir statt der Seitenhalbierenden die Winkelhalbierende nehmen so wird im Durchschnitt ebenfalls in etwa die Höhe in jedem Schritt durch 2 geteilt, jedoch ist der Worst-Case deutlich besser: Wenn nur noch rote kommen, dann halbiert sich auch hier im Durchschnitt die minimale Höhe in jedem Schritt

Wenn die minimale Höhe des ersten großen Dreiecks in der Größenordnung 2 hoch (n-3) liegt, dann beträgt die Fläche dieses gleichseitigen Dreiecks in der Größenordnung 1/wurzel(3) * 4 hoch ( n-3)

Grüße
Frank Brenner