20: Noch eine knackige Mützenaufgabe / Another Tricky Hat Challenge

  • Man kann die Vier-Vierergruppen-Strategie so erweitern, dass der zeitlich erste jeder Vierergruppe die freie Farbwahl hat und dadurch 1 Bit an Information mitteilen kann. Die beiden Nachfolger jeder Gruppe nehmen die Farbe des Vorgängers, der letzte die andere Farbe.

    Am Ende ist wie bisher entweder in vier Gruppen der jeweils letzte zu erkennen, oder in genau einer Gruppe ist dies nicht der Fall.

    Unwahrscheinlich, aber dennoch möglich, dass der Weihnachtsmann als erste 4 Wichtel gerade die jeweiligen "Informationswichtel" auffordert, eine Mütze aufzusetzen. Zu diesem Zeitpunkt gibt es allerdings nicht wirklich viel zu berichten. D.h. im ungünstigen Fall kann kein Mehrwert erzeugt werden und somit kann diese Strategie auch keinen zusätzlichen Kuchen garantieren..

  • Unwahrscheinlich, aber dennoch möglich, dass der Weihnachtsmann als erste 4 Wichtel gerade die jeweiligen "Informationswichtel" auffordert, eine Mütze aufzusetzen. Zu diesem Zeitpunkt gibt es allerdings nicht wirklich viel zu berichten. D.h. im ungünstigen Fall kann kein Mehrwert erzeugt werden und somit kann diese Strategie auch keinen zusätzlichen Kuchen garantieren..

    Richtig. Ein Mehrwert kann nicht garantiert werden. Aber die Wahrscheinlichkeit, dass Quibo den letzten Wichtel X ganz links hinstellt, kann in dem Fall, dass alle vier Gruppenletzten zu erkennen sind, erhöht werden. Und zwar wie folgt:

    Die drei Gruppenersten wählen blau, der letzte Gruppenerste wählt rot.


    Ich habe das mal für den Fall von drei Dreiergruppen bei zehn Intelligenzwichteln berechnet:

    Die Wahrscheinlichkeit, dass der letzte Wichtel aus der

    1. Gruppe ist = 0,25,

    2. Gruppe ist = 0,30,

    3. Gruppe ist = 0,45.

    Wenn der Weihnachtsmann die Mützenfarbe zufällig wählt, sinkt der Erwartungswert (Wichtel, die hungrig nach Hause geschickt werden) bei drei Dreiergruppen von 1 auf 0,9125.

  • Eigentlich müsste ich diesen Beitrag löschen! Nach Lektüre der folgenden Ausführungen (#26 und #27) von Georg J. aus D. ist eine Korrektur oder zumindest Kommentierung unumgänglich.

    [...]

    Wenn der Weihnachtsmann die Mützenfarbe zufällig wählt, sinkt der Erwartungswert (Wichtel, die hungrig nach Hause geschickt werden) bei drei Dreiergruppen von 1 auf 0,9125.

    (1.) Leider kann ich der Reduzierung auf 10 Intelligenzwichtel nicht folgen. Nach meinem Verständnis läge der Erwartungswert hungrig nach Hause zu schickender Wichtel bei 3 Dreiergruppen nicht bei 1, sondern bei 2 Wichteln. [Verständnisfehler von mir]


    (2.) Für die folgende Betrachtung möchte ich wegen (1.) wieder auf die uns bekannten 17 Intelligenzwichtel schauen. Einer, Quibo, muss zunächst raus, so dass 16 Wichtel im Raum bleiben, von denen nun 15 strategisch ihre Mützenfarbe wählen dürfen, während einer, Wichtel X, vom Weihnachtsmann die Mütze aufgesetzt bekommt.

    Im positiven Extremfall würden die ersten 3 vom Weihnachtsmann gewählten Wichtel zu einer Gruppe gehören. Der 4. zu dieser Gruppe gehörende Wichtel ist nun einer der 13 nicht gewählten Wichtel und wäre der Kandidat für die 5. Gruppe, die sich aus den Gruppenletzten bildet. Für jeden dieser 13 Wichtel ist die Chance als nächster gewählt zu werden 1/13, bzw. 12/13 nicht gewählt zu werden. Im nächsten Wahlgang beträgt die Chance 1/12, bzw. 11/12, usw.

    Deshalb beträgt die Wahrscheinlichkeit für jeden dieser 13 Wichtel bis zum Ende nicht gewählt zu werden, also der vom Weihnachtsmann bemützte Wichtel zu sein, 12/13 x 11/12 x ... x 1/2 = 1/13. Das bedeutet, dass es keinen Unterschied macht, ob die eigene 4er-Gruppe bereits gefüllt war oder nicht. (Wenn man diese Wahrscheinlichkeit zu einem späteren Zeitpunkt berechnete, zu dem z.B. bereits k Wichtel ihrer Gruppe durch Wahl zugeordnet sind, wären noch 16-k Wichtel übrig und jeder hätte die Chance 1/(16-k) als letzter Wichtel übrig zu bleiben oder eine beliebige andere frühere Position im Wahlgang zu erhalten.) [Die Angabe von Georg J. aus D. für n=3, dass die Wahrscheinlichkeiten des letzten Wichtels aus Gruppe 1 bis 3 zu stammen, 0,25; 0,3 und 0,45 , hätte ich nie geglaubt, konnte sie aber zwischenzeitlich bestätigen und muss daher meine Betrachtung als falsch ansehen!]


    (3.) Das Konzept der vier 4er-Gruppen für 15 Wichtel funktioniert, weil die Gruppenletzten eine andere Mützenfarbe als ihre jeweils 3 Gruppenkollegen wählen und somit als fünfte 3er-Gruppe erkennbar werden. Wichtel X wird nun eine dieser fünf 3er-Gruppen durch seine Mützenfarbe zu einer 4er-Gruppe ergänzen. Aus dieser 4er-Gruppe bekommt nur Wichtel X garantiert Kuchen, von den anderen 3 Wichteln nur jene, die zufällig rechts von ihm aufgestellt werden. Innerhalb dieser durch Wichtel X komplettierten 4er-Gruppe bleibt wegen (2.) jeder Wichtel gleichermaßen verdächtig, Wichtel X zu sein. [Nachdem (2.) nicht mehr haltbar ist, ist auch die Schlussfolgerung falsch.]


    M.E. hat die zusätzliche Information "4er-Gruppe i wurde als letzte begonnen" mit i € {1; 2; 3; 4} keinen Wert bzgl. der Kuchenverteilung.

    [s.o.: Offensichtlich nicht haltbar!]

    Dieser Beitrag wurde bereits 1 Mal editiert, zuletzt von MATH+ () aus folgendem Grund: Annahmen und "Beweis" waren falsch.

  • Gegeben waren in der Aufgabe n2 + 1 Wichtel mit n = 4. Quibo sieht sich n2 Wichteln gegenüber, die vom Weihnachtsmann in einer von n2! möglichen Reihenfolgen ausgewählt wurden. Die Strategie mit n Gruppen zu je n Wichteln garantiert M = n2 - 2 Wichteln Kaffee und Kuchen, d. h. höchstens n - 1 Wichtel werden hungrig nach Hause geschickt. Die Intelligenzwichtel wollen, nachdem sie M maximiert haben, zusätzlich auch den Erwartungswert E (Anzahl der Wichtel, die hungrig nach Hause geschickt werden) minimieren. (Das ist eine Erweiterung der Aufgabenstellung.)

    Wenn der letzte Wichtel X zufällig in einer Reihe von n Wichteln steht, dann werden gleichwahrscheinlich 0, 1, ..., n-1 Wichtel nach Hause geschickt.

    ==> Die bisherigen besten Strategien haben E = (n-1)/2.


    In #24 habe ich den Fall für n = 3 betrachtet, da ich alle 9! mögliche Reihenfolgen schneller als alle 16! mögliche Reihenfolgen bei n = 4 untersuchen kann. Die Minimierung des Erwartungswertes setzt n >= 3 voraus und dass der Weihnachtsmann die Mützenfarbe zufällig wählt.


    Wie kann der Erwartungswert überhaupt kleiner werden?

    In der einen Hälfte aller Fälle kann Quibo die (feste) Gruppe, zu der Wichtel X gehört, identifizieren (Fall A).

    In der anderen Hälfte aller Fälle kann Quibo den jeweils letzten Wichtel aller n Gruppen identifizieren (Fall B). Alle n Wichtel stammen aus verschiedenen (festen) Gruppen.

    Und genau in diesem Fall B kann er den letzten Wichtel derjenigen Gruppe, deren erster Wichtel als letzter erster Wichtel ausgewählt wurde, identifizieren und ganz nach links stellen.


    Es gilt hier n = 3:

    Fall B: Von allen 9! möglichen Reihenfolgen ist in 45 % aller Fälle der letzte Wichtel X aus der (zeitlich) 3. Gruppe. Quibo wählt X an die 1. Position links: E(3.) = 0

    In 30 % aller Fälle ist X aus der 2. Gruppe, und in 25 % aller Fälle ist X aus der 1. Gruppe. Quibo kann diese beiden Fälle nicht unterscheiden und wählt zufällig X an die 2. oder 3. Position von links: E(2.) = E(1.) = 1,5

    E(B) = 0,45 * 0 + 0,55 * 1,5 = 0,825


    E = (E(A) + E(B))/2 = (1 + 0,825)/2 = 0,9125


    Man kann E sogar noch etwas kleiner bekommen, indem man entweder diese Regel

    Zitat

    Die n-1 Gruppenersten wählen blau, der letzte Gruppenerste wählt rot.

    oder jene Regel

    Zitat

    Die n-1 Gruppenersten wählen rot, der letzte Gruppenerste wählt blau.

    verwendet - ja nach der Parität der (festen) Gruppe des allerersten Wichtels.


    In Fall B stellt Quibo den letzten Wichtel der letzten Gruppe immer nach ganz links. Die Parität dieser (festen) Gruppe sei p.


    Für n = 4 kann Quibo den Wichtel Y identifizieren, der zur anderen (festen) Gruppe mit der Parität p gehört.


    Falls die (zeitlich) erste Gruppe auch die Parität p hat, dann stellt Quibo Y an die vierte Stelle von links und die restlichen beiden Wichtel dazwischen.


    Falls die (zeitlich) erste Gruppe die andere Parität hat, dann stellt Quibo Y an die zweite Stelle von links und die restlichen beiden Wichtel rechts daneben.

  • Es gilt hier n = 4:


    Fall B: Von allen 16! möglichen Reihenfolgen ist in 128/385 = 0,332... aller Fälle der letzte Wichtel X aus der (zeitlich) 4. Gruppe. Quibo wählt X an die 1. Position links: E(4.) = 0


    In 96/385 = 0,249... aller Fälle ist X aus der 3. Gruppe, in 12/55 = 0,218... aller Fälle ist X aus der 2. Gruppe, und in 20 % aller Fälle ist X aus der 1. Gruppe. Quibo kann diese drei Fälle nicht unterscheiden und wählt zufällig X an die 2. bis 4. Position von links: E(3.) = E(2.) = E(1.) = 2


    E(B) = 128/385 * 0 + 257/385 * 2 = 514/385 = 1,335...


    E(A) = 1,5


    E = 2183/1540 = 1,4175... (ohne Nutzung der Parität)

  • Meine Lösung ist ein Mix aus der Lösung von Dandelo und der "Musterlösung" mit 4 Untergruppen à 4 Wichteln. Wenn man das Rätsel für 4 Wichtel gelöst hat, sieht man, dass es eine Strategie gibt ein Paar zu codieren, das sicher nicht den letzten Wichtel enthält. Genau diese Strategie kann man nun für die 4 Untergruppen auch anwenden: Egal was Santa am Ende macht, wird Quibo 2 Untergruppen erkennen, die den letzten Wichtel X enthalten muss und auch in jedem der 2 Untergruppen jeweils das Wichtelpaar, das in Frage kommen kann. Er kann also auch 4 Wichtel identifizieren, die für X in Frage kommen.


    Das lässt sich übrigens auch auf 4 x 4 x 4 Wichtel (allgemein auf 4^n) ausweiten. Quibo wird dann 2 Cluster identifizieren mit 2 Untergruppen mit 2 Paaren, also von den 64 Kandidaten kann man 8 herausfiltern.


    Danke für diese tolle Aufgabe, an der ich eine ganze Woche gerätselt habe, denn anfangs war ich überzeugt, es müsste eine Strategie geben, die 14 Wichtel "rettet". Und wenn man etwas sucht, das es nicht gibt, kann man schon einmal verzweifeln :-)

  • Einen Beweis dafür, dass es zu jeder Strategie der Wichtel mindestens eine Wahl des Weihnachtsmannes gibt, also eine 15 stellige Folge von (verschiedenen) Wichteln und eine Farbe für den 16. Wichtel (Mr.X), so dass Quibo nicht weniger als 4 Wichtel als Kandidaten für Mr.X bestimmen kann, ist nicht bekannt, oder habe ich was überlesen?

    Ich suche seit Tagen danach, bin aber wohl zu blöd, es sei denn, der Beweis ist tatsächlich schwierig bzw. die ganze Vermutung ist falsch.


    Naheliegende Verallgemeinerung: statt 16 bzw. 17 Wichtel seien es n2 bzw. n2 + 1 Wichtel und die beste Strategie liefert n Wichtel als Kandidaten für Mr.X.

  • Einen Beweis dafür, dass es zu jeder Strategie der Wichtel mindestens eine Wahl des Weihnachtsmannes gibt, also eine 15 stellige Folge von (verschiedenen) Wichteln und eine Farbe für den 16. Wichtel (Mr.X), so dass Quibo nicht weniger als 4 Wichtel als Kandidaten für Mr.X bestimmen kann, ist nicht bekannt, oder habe ich was überlesen?

    Ich suche seit Tagen danach, bin aber wohl zu blöd, es sei denn, der Beweis ist tatsächlich schwierig bzw. die ganze Vermutung ist falsch.


    Naheliegende Verallgemeinerung: statt 16 bzw. 17 Wichtel seien es n2 bzw. n2 + 1 Wichtel und die beste Strategie liefert n Wichtel als Kandidaten für Mr.X.

    Ja das wäre interessant einen Beweis zu sehen. Oder wenn es keine Quadratzahl ist. Ich habe lange nach einer Strategie für 8 Wichtel gesucht, konnte aber immer nur 4 davon "retten". Schon bei 8 Wichtel gibt es extrem viele Möglichkeiten für eine Strategie und ich habe keine Ahnung, wie man das allgemein angehen kann.

  • Ja das wäre interessant einen Beweis zu sehen. Oder wenn es keine Quadratzahl ist. Ich habe lange nach einer Strategie für 8 Wichtel gesucht, konnte aber immer nur 4 davon "retten". Schon bei 8 Wichtel gibt es extrem viele Möglichkeiten für eine Strategie und ich habe keine Ahnung, wie man das allgemein angehen kann.

    Für den Fall n =8 statt 16: da müsste es doch mit einer 3,3,2 - Gruppierung (statt einer 4,4,4,4 - Gruppierung wie in der hier veröffentlichten "Musterlösung") möglich sein, immer mindestens 5 zu "retten", oder?


    Was die Anzahl der Strategien angeht: für den Fall der 16 Wichtel gibt es 235.951.249.665.216 Strategien, für den Fall von 8 Wichteln immerhin

    noch 269280, zu viel zum Durchlauf in einer Schleife. Selbst bei 4 Wichteln gibt es bereits 240 Strategien. Die Anzahl der Strategien lässt sich sicher durch "intelligente" Reduktionen verkleinern (z.B. wird man Strategien, die durch Permutation der Wichtel auseinander hervorgehen, als äquivalent ansehen können). Aber ihre Anzahl wird "groß" bleiben, um es vorsichtig auszudrücken.

  • Danke für die weiteren Ausführungen in Posts #26 und #27.

    Ich habe meine falsche Einschätzung in Post #25 entsprechend kommentiert.


    Wäre eine weitere Verbesserung wohl möglich, wenn nur die beiden ersten Gruppenersten eine rote Mütze wählen und beide letzte Gruppenerste eine blaue?

    Mir ist es leider nur gelungen, deine Angaben für n=3 in einer Tabellenkalkulation nachzustellen. n=4 gelingt mir so nicht.

  • Für den Fall n =8 statt 16: da müsste es doch mit einer 3,3,2 - Gruppierung (statt einer 4,4,4,4 - Gruppierung wie in der hier veröffentlichten "Musterlösung") möglich sein, immer mindestens 5 zu "retten", oder?


    Was die Anzahl der Strategien angeht: für den Fall der 16 Wichtel gibt es 235.951.249.665.216 Strategien, für den Fall von 8 Wichteln immerhin

    noch 269280, zu viel zum Durchlauf in einer Schleife. Selbst bei 4 Wichteln gibt es bereits 240 Strategien. Die Anzahl der Strategien lässt sich sicher durch "intelligente" Reduktionen verkleinern (z.B. wird man Strategien, die durch Permutation der Wichtel auseinander hervorgehen, als äquivalent ansehen können). Aber ihre Anzahl wird "groß" bleiben, um es vorsichtig auszudrücken.

    Ja mit einer 3,3,2 - Gruppierung kann man 5 "retten", möglicherweise hatte ich auch so eine Strategie gefunden mit meinem Pythonprogramm, aber ich hatte sie verworfen, weil ich zu dem Zeitpunkt noch überzeugt war, es müsse eine Lösung geben, die 6 Wichtel rettet.


    Wie kommt man auf 240 Strategien? Ich ging bisher von 2n! Strategien aus. Da gibt es ja anscheinend noch viel mehr, die ich gar nicht in Betracht gezogen hatte.

  • Überlegungen zur Anzahl der Strategien


    Phase 1: Mützenfarben für n Wichtel:

    Weihnachtsmann bestimmt Reihenfolge von n Wichteln: n!

    n-1 Wichtel wählen Farbe für sich, Weihnachtsmann wählt für Wichtel X: 2n

    Insgesamt n! * 2n Strategien der Farbwahl.


    Phase 2: Quibo sieht n Wichtel mit 2n möglichen Farbvariationen. Er kann jeweils n! Farbwahlen nicht unterscheiden. Es gibt für jede der 2n Farbvariationen n! mögliche Reihungen.


    Insgesamt: n! * 2n * n!

    n = 4 --> 9216 mögliche Strategien


    In Phase 1 habe ich zu viele Strategien gezählt. Korrektur in #40.

    Die Lösung ist vom Lösungsweg unabhängig.

    Dieser Beitrag wurde bereits 1 Mal editiert, zuletzt von Georg J. aus D. () aus folgendem Grund: Hinweis auf #40

  • mmm, ich komme da auf andere Ergebnisse. Nehmen wir mal nur 3 Wichtel. Da komme ich auf 29 Strategien, die jeweils durch eine 3 x 3 Matrix A, die nur aus Nullen und Einsen besteht, dargestellt werden kann. Die Elemente aij = 1 bedeutet Wichtel i nimmt eine 1 wenn er nach Wichtel j drankommt (oder eben eine 0 wenn aij = 0). aii = 1 bedeutet Wichtel i nimmt eine 1 wenn er beginnt. Mehr Strategien sehe ich nicht zum Auswählen der Farben.


    Die Stragien der Phase 2 braucht man nicht analysieren, nach meiner Meinung, da ich ja nur wissen will ob es eine Strategie gibt um k Wichtel zu retten. In dem Fall mit den 16 Wichtel und alle nehmen blau bis auf die Gruppenletzten, gäbe es ja auch unzählige Strategien für Quibo (z.B. ich wähle immer Wichtel 1 oder ich wähle Wichtel m, wenn es m blaue Hüte gibt, etc ...), aber das sind ja Strategien, die völlig irrelevant zum Lösen der gestellten Frage sind.


    Habe ich da einen Fehler in meiner Argumentation?

    (Ich hatte die verschiedenen Strategien für n=4 mit einem Pythonprogramm analysiert, aber bei n=8 war ich dann gescheitert)


  • Das sehe ich anders. Eine Strategie der Wichtel muss für jede Situation, die sich aufgrund der nicht vorherzusehenden Wahl des Weihnachtsmannes ergeben könnte, eine Reaktion vorsehen.

    Also: im folgenden mögen die Zahlen 1 bis 16 für die 16 Wichtel stehen.


    Das Spiel läuft in der ersten Phase dann so: der W.-Mann wählt eine Zahl zwischen 1 und 16, der entsprechende Wichtel muss dann bereits eine Wahl treffen, er kann nicht warten, bis die gesamte Wahl des W.-Manns feststeht. Eine Strategie zu haben bedeutet dann also, dass festgelegt sein muss, welche Wahl welcher Wichtel treffen soll, wenn er als erster gewählt wird. Dann geht's weiter mit der nächsten Auswahl des W.-Manns und der entsprechende Wichtel, der jetzt weiß, was vor ihm gewählt wurde, muss eine Wahl treffen. Das heißt, die gewählte Strategie muss für alle Paare von Wichteln für den zweiten Wichtel in diesem Paar eine Farbe vorsehen. In dieser Weise geht es weiter. Insgesamt: eine Strategie wählt für jede max. 15-stellige Folge von paarweise verschiedenen Zahlen zwischen 1 und 16 eine Farbe. Die Anzahl solcher Folgen ist, wie leicht zu sehen: 16 + 16*15 + 16*15*14 + ... + 16*15*14*...*2.


    Für den Fall der 4 Wichtel haben wir: Anzahl der Folgen ist 4 + 4*3 + *4*3*2 = 40.


    So ergeben sich die oben genannten Werte.


    Da die Anzahl der Farben 2 ist, könnte man auch sagen: eine Strategie besteht darin, eine Teilmenge der Menge aller oben erklärten Folgen festzulegen, nämlich die Menge aller Folgen, bei der der letzte in der Folge ROT wählt.


    Für den Fall von 3 Wichteln, der oben von RüdiJ erwähnt wurde, ergibt meine Rechnung auch 29 Strategien, da die Anzahl der Folgen ja 3 + 3*2 = 9 ist.


  • Das erscheint mir sehr plausibel. Dann stimmen auch meine 29 = 23 + 3*2 Strategien für n=3. Prima.

  • Die 240 Strategien für 4 Wichtel erschienen mir zu hoch. Deshalb meine Abschätzung in #36.

    Ich gebe zu, dass ich zu viele Fälle gesehen habe. Der erste Wichtel kann seine Farbwahl nicht von der Reihenfolge der späteren Wichtel abhängig machen. Das hatte ich nicht berücksichtigt. Daher jetzt neu und zuerst Phase 1:


    n Wichtel plus Quibo


    Der Weihnachtsmann wählt den ersten Wichtel aus n Wichteln, jeder davon hat 2 Farben zur Auswahl:

    2n


    Der Weihnachtsmann wählt den 2. aus n-1 Wichteln, jeder davon hat 2 Farben zur Auswahl:

    2(n-1)


    usw.


    Der Weihnachtsmann wählt für den letzten Wichtel X eine von 2 Farben:

    2


    2n * 2(n-1) * 2(n-2) * ... * 2 = (2n)!!


    Für n = 3: 6!! = 48

    Für n = 4: 8!! = 384


    Phase 2: Quibo sieht n Wichtel mit 2n möglichen Farbvariationen. Er kann jeweils n! Farbwahlen nicht unterscheiden, da er die Reihenfolge nicht kennt. Es gibt für jede der 2n Farbvariationen n! mögliche Reihungen:


    2n * n! = (2n)!!


    Dies ist gleiche Zahl wie in Phase 1.

    Die Lösung ist vom Lösungsweg unabhängig.

    Dieser Beitrag wurde bereits 3 Mal editiert, zuletzt von Georg J. aus D. () aus folgendem Grund: Phase 2 ergänzt.

  • Phase 2 lass ich mal außen vor, denn die Anzahl der Strategien ist unabhängig von Phase 2. Quibo kennt natürlich die gewählte Strategie und muss nun entscheiden, welche Permutationen in Frage kommen, damit die Farbverteilung, die er sieht, so ist wie sie ist. Und das jeweils letzte Element solcher Permutationen ist dann ein Kandidat für Wichtel X.


    Zur Anzahl der Strategien (ohne jede Reduktion aufgrund von Symmetrien):


    Nehmen wir n = 4. Schon für die erste Wahl des W.-Manns gibt es 24 Möglichkeiten, zu reagieren und nicht nur 2*4. Für die zweite Wahl des W.-Manns sind 12 = 4*3 Paare zu berücksichtigen. Denn: die Farbe, die die Strategie für die Folge 2,1 für 1 vorsieht, kann ja anders sein, als die Farbe, die die Strategie für 1 beim Paar 3,1 vorsieht, und auch verschieden von der Farbe für die 1, wenn sie (also der entspr. Wichtel) als erste genannt wird oder als dritte in z.B. 2,4,1.


    Kurz und gut: eine Strategie ist eine Abbildung aller max. 15-stelligen Folgen aus dem Bereich 1 bis 16, paarweise verschieden, in die 2- elementige Menge {rot, blau}. (Bzw. für n = 4 eine Abbildung aller max. 3 stelligen Folgen aus dem Bereich 1,2,3,4 in die Menge {rot, blau}.)


    Nicht einleuchtend?