Beiträge von RüdiJ

    Alles richtig. Nur die letzte Zeile "dass ausgehend von der Anfangskombination 000000 beim (n+1)-Wurf kein Wechsel B<->C stattfindet." ist nicht meine Argumentation.


    Ich sage stattdessen: Im Fall 1, muss Cn+1 zu 1 werden und im Fall 2 muss Bn+1 zu 1 werden. Und das ist doch unmöglich.

    Ich hatte vor kurzem einen Beweis auf YouTube gesehen, der zeigt, dass X4 + Y4 = Z4 keine ganzzahligen Lösungen besitzt (). Die Idee dabei ist, wenn es eine Lösung gäbe und die kleinste wäre, X, Y, Z, dann könnte man daraus eine kleinere Lösung X', Y', Z' ableiten, was der Annahme widerspricht, dass X, Y, Z die kleinste sei.


    Genauso ist mein Gedankengang. Wenn n+1 die kleinste Anzahl von Würfen ist, um (für alle Kombinationen) zwei identische Teile zu finden, was muss dann im letzten Wurf passiert sein? Wenn man sich diesen Wurf genau anschaut, sieht man eben, dass er nicht für alle möglichen Kombinationen den gewünschten Effekt erzielen kann (und da genügt es schon, wenn der Wurf bei einer Kombination scheitert, denn die kann Ruprecht ja nicht ausschließen). Ich komme dann zu dem Ergebnis, dass Ruprecht die identischen Teile auch schon vor dem letzten Wurf kennen müsste, da der letzte Wurf ihm keine Klarheit verschaffen kann.


    Kann man so nicht argumentieren? Ist der Beweis nicht zu retten?

    Ja, ich meine B63.

    Bn ist jetzt der Zustand von B nach n Würfen. Bn beschreibt ja immer noch gleichzeitig den Zustand von B in allen 64 möglichen Zeilen.

    Du schreibst vom notwendigen Vorzeichenwechsel. Für den Widerspruchsbeweis muss sich Bn+1 von Bn in mindestens einer der 64 Zeilen unterscheiden, d. h. es muss eine Änderung entweder von 0 auf 1 oder von 1 auf 0 erfolgt sein. Aber das muss nicht und kann nicht gleichzeitig in allen 64 Zeilen passieren, da in Zeile 0 und in Zeile 63 sich die Werte nie ändern.

    Deine Argumentation (so wie ich sie verstanden habe): In einer Zeile ändert sich B nicht, also Widerspruch.

    Ich entgegne: Für einen Widerspruch ist es notwendig zu zeigen, dass sich B in allen Zeilen nicht ändert. Nur dann wäre Bn+1 = Bn.


    Also meine Argumentation ist nicht, dass sich die Variable B im letzten Wurf in einer Zeile ändert, sondern der Zustand B für eine völlig beliebige Ausgangsverteilung, die wir nicht kennen. Und daraus leite ich dann den Widerspruch ab. Bn ist also nicht die 6x64 Matrix sondern ein einziger Zustand.

    Ich habe das inzwischen noch etwas präzisiert:


    Also gibt es nur 2 Fälle für den letzten Wurf: Bn auf Cn oder Cn auf Bn


    Nehmen wir an, dabei ändert sich das Vorzeichen von B. [wie gesagt nicht die Matrix, sondern dieser eine Zustand]


    Fall 1: Bn auf Cn

    Daraus folgt dass Bn = 0 und Cn = 1 (die einzige Möglichkeit, wo der Geworfene sein Vorzeichen wechselt).


    Fall 2: Cn auf Bn. Daraus folgt dass Bn = 1 und Cn = 0.


    Wenn aber die Anfangskombination (0 0 0 0 0 0) ist, kann sowohl Bn = 1 als auch Cn = 1 nicht vorkommen und

    somit ist sowohl Fall 1 als auch Fall 2 nicht möglich. Der Algorithmus von Ruprecht muss ja für alle Anfangskombination funktionieren.


    Also darf sich das Vorzeichen von B beim letzten Wurf nicht ändern. Da Ruprecht das aber auch schlussfolgern kann, wüßte er ja bereits nach n

    Würfen, dass A und B identisch sind und damit haben wir den gesuchten Widerspruch.

    Ich verstehe nicht ganz, wieso gerade ein Induktionsbeweis brauchbar seien soll, wenn es doch gerade nicht darum geht nachzuweisen, das nach einer Anzahl von Würfen die "0" X-Masium nicht von den "1" X-Masium getrennt werden können, sondern darum, das diese Trennung nicht für alle 64 Konstellationen möglich ist?


    Insgesamt gibt es doch für alle 64 Konstellationen nur eine endliche Anzahl von Würfen (12) nach der sich nichts mehr ändert, weil die X-Masium für alle Konstellationen sortiert sind. Bei manchen Konstellationen sind hierfür auch weniger oder gar keine Würfe notwendig (aber da man die Konstellation ja gerade nicht messen kann, weiß Ruprecht es nicht). Die Unmöglichkeit einer Trennung von "0" X-Masiium und "1" X-Masiium für eine Konstellation, die nach wenigen Würfen bereits sortiert ist, ergibt sich doch nicht aus der Unmöglichkeit der Trennung für eine Konstellation, die mit noch weniger Würfen sortiert ist, sondern aus der Unmöglichkeit die real vorliegende Konstellation zu messen und aus der Unmöglichkeit einen Zustand herzustellen, der für alle Konstellationen garantiert, das zwei gleiche X-Masium benachbart sind.

    Es reicht somit völlig zu zeigen, dass durch eine Abfolge von 12 Würfen alle 64 Konstellationen eindeutig auf die 7 sortierten Zustande abgebildet werden können, und das diese 7 sortierten Zustände linear unabhängig sind.

    Naja, ist doch Geschmacksache welcher Beweis "schöner" ist. In dem hier zitierten Beweis, muss man erst einmal nachvollziehen, dass sich nach einer endlichen Anzahl von Würfen (12) nichts mehr ändert und dass danach alles sortiert ist. Das nachzuvollziehen erfordert schon etwas Gehirnschmalz. Und dass die 7 sortierten Zustände linear unabhängig sind. Aber muss man denn überhaupt sortieren? Es könnte ja auch Strategien geben, die nicht sortieren. Also ich finde da meinen Beweis etwas einfacher zu verstehen, aber wie gesagt das ist Geschmacksache.


    Was mich unruhig macht, sind die Kommentare zu meinem Beweis, die die Gültigkeit anzweifeln. Auch wenn du meinen Kommentar nicht "brauchbar" findest, möchte ich doch gerne wissen, ob er mathematisch hieb- und stichfest ist.

    Die Argumentation hat Lücken:

    64 mögliche Anfangszustände dargestellt als 64 Zeilen einer 6-spaltigen Matrix. Jede Spalte steht für ein Atom, z. B.: A, B, C.

    Nach n+1 Würfen sollen die Spalten A und B identisch sein, aber nach n Würfen noch nicht.

    Wenn sich oBdA B ändert, dann muss sich B an mindestens einer Stelle, z. B. Bn (Spalte B und Zeile n der Matrix) ändern. An anderen Stellen B0 und B31 bleiben die Werte gleich.

    Georg, kannst du das bitte näher erläutern, denn von deiner Erklärung kann ich die Argumentationslücke nicht erkennen. Ich sage doch dass Bn nicht immer 1 sein kann. (Vorsicht Bn ist in meiner Schreibweise der Zustand von B nach n Würfen und nicht die n-te Zeile!)


    Außerdem vermute ich dass du B63 und nicht B31 meinst, oder? (Diesmal in deiner Notierung, wo der Index die Zeile deiner Matrix angibt)

    Ich glaube für n = 3 lässt sich das noch am einfachsten aufdröseln. Die 48 Möglichkeiten sind keine Strategien. Es gibt 48 Möglichkeiten, wie sich die 3 Wichtel der Reihe nach in verscheidenen Hutvariationen aufstellen können. Aber beim 3. Wichtel haben sie gar keine Wahl mehr, das wird vom Weihnachtsmann bestimmt und dafür können sie keine Strategie wählen.


    Und der zweite Wichtel, der vom Weihnachtsmann ausgewählt wird, hat nicht nur 2 sondern 4 mögliche Strategien (nicht Wahlmöglichkeiten!). Er kann seine Farbwahl von seinem Vorgänger (A1 oder B1) und der Wahl seines Vorgängers abhängig machen, also für f(A1=0) muss er eine Strategie haben, genau so für f(A1=1), f(B1=0) und f(B1=1). Es gibt also 2 x 2 x 2 x 4 x 4 x 4 verschiedene Strategien.


    Ergänzung: sorry, ihr schreibt viel schneller als ich. Ich bin immer noch bei n=3, wollte aber euren Gedankenfluss mit n=4 nicht durcheinander bringen.

    A oder B ist in den letzten Wurf involviert. Dabei muss aber nicht im jedem Fall ein Vorzeichenwechsel stattfinden (weil A und B auch nach n Würfen identisch sein können, bei geeigneter Anfangsverteilung).

    Es ist bloß so, dass nicht bei allen Anfangsverteilungen nach n Würfen A und B identisch sind. Damit kann Ruprecht nach n Würfen nicht sicher sein.

    Das stimmt allerdings, dass ich genaugenommen auch den Fall betrachten muss, in dem im letzten Wurf kein Vorzeichenwechsel stattfindet. Es gibt also 2 Fälle zu betrachten:


    A) im letzten Wurf findet ein Vorzeichenwechsel statt, aber das kann nicht sein, wie schon gezeigt

    B) im letzten Wurf findet kein Vorzeichenwechsel statt, aber wenn Ruprecht das weiß (und das weiß er ja, da der andere Fall zu einem Widerspruch führt), dann braucht er ja den letzten Wurf gar nicht machen und hat schon nach n Würfen eine Lösung.


    Also auch in dem Fall gibt es einen Widerspruch.

    RüdiJ Ich finde es etwas verwirrend, dass Du mit Santa argumentierst. In der Aufgabe ist Ruprecht der Werfer, und der Weihnachtsmann (Santa) soll das Geschenk mit den zwei gleichen Atomen erhalten. Die Argumentation über Santa ist deshalb verwirrend, weil bei der ursprünglichen Aufgabe schon die Bemerkung aufkam, dass Ruprecht doch einfach zwei Atome einpacken könnte, wenn man die Typen nicht unterscheiden kann. Daraufhin wurde argumentiert, dass es ja sein könne, dass Ruprecht die zwar nicht unterscheiden kann, der Weihnachtsmann aber evtl. schon - mit dem Argument im Hinterkopf muss man sich bei Deinem Beweis immer klarmachen, dass Du eigentlich Ruprecht meinst (davon gehe ich zumindest aus).

    sorry, das Rätsel ist schon ein paar Tage her und ich hatte die Aufgabenstellung nicht mehr im Kopf. Ich werde das sofort korrigieren.

    Sorry, diesen Teil verstehe ich immer noch nicht... Auch wenn es eine hypothetische Strategie (von minimaler Länge) gäbe, muss nicht für alle Anfangskombinationen gelten, dass A oder B beim letzten Mal den Zustand wechselt. (Mit anderen Worten: Vor dem letzten Wurf kann man sich nicht sicher sein, dass A und B gleich sind; aber es ist trotzdem möglich (wegen z.B. Anfangszustand 000000). Im letzteren Fall findet sich beim letzten Wurf kein Vorzeichenwechsel statt)

    Ruprecht sagt nach n+1 Würfen, dass A identisch zu B ist. Wenn weder A noch B in den letzten Wurf involviert sind, dann wüsste er doch schon nach n Würfen, dass A und B identisch sind!

    So ich habe versucht, den Induktionsbeweis noch einmal sauber aufzuschreiben:


    Annahme: Ruprecht kann nach n Würfen keine 2 identischen Teile identifizieren.


    Test für n = 0. Ruprecht kennt zu Beginn keine 2 identischen Teile. Damit ist die Induktionsverankerung gegegben.


    Widerspruchsannahme: Ruprecht kann nach n+1 Würfen 2 identischen Teile identifizieren. Nennen wir die beiden Teile A und B.

    Der n+erste Wurf kann nicht A auf B oder umgekehrt sein. Da würde sich die relative Parität von A und B nicht verändern.


    Also gibt es nur 2 Fälle für den n+ersten Wurf: Bn auf Cn oder Cn auf Bn

    (o.B.d.A. nehmen wir an, dass B sein Zustand ändern wird und nicht A)


    Fall 1: Bn auf Cn mit Vorzeichenwechsel von B.

    Daraus folgt dass Bn = 0 und Cn = 1 (die einzige Möglichkeit, wo der Geworfene sein Vorzeichen wechselt).


    Fall 2: Cn auf Bn mit Vorzeichenwechsel von B. Daraus folgt dass Bn = 1 und Cn = 0.


    Es muss aber für alle möglichen Anfangskombination gelten. Wenn aber die Anfangskombination (0 0 0 0 0 0) ist,

    kann sowohl Bn = 1 als auch Cn = 1 nicht vorkommen und somit ist sowohl Fall 1 als auch Fall 2 nicht möglich

    und damit haben wir den gesuchten Widerspruch.


    Daraus folgt, dass Ruprecht auch nach n+1 Würfen keine 2 identischen Teile identifizieren kann. Damit ist der Induktionsbeweis geführt.


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

    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)

    Vielleicht sollte man noch dazuschreiben (obwohl das ja schon vielfach an anderen Stellen steht) dass Kriemhilde und Fridolin die gleichen Wahrscheinlichkeiten haben für die Ankunftszeiten 1 ; 3 ; 5 ; 7 ; 9. Denn wenn Fridolin eine höhere relative Wahrscheinlichkeit für die Ankunftszeit 1 hätte als Kriemhilde, dann würde deine Urnensimulation nicht stimmen.

    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.

    Ich denke auch, dass der Beweis so noch nicht ganz funktioniert, da er Aussagen zu allen Verteilungen mit Aussagen zu konkreten Verteilungen zu mischen scheint. Auch der Satz "Es ist gar nicht möglich, dass B_n-1 und C_n-1 bestimmte Werte einnehmen für alle möglichen Ausgangsverteilungen." ist ja eher eine umformulierte Behauptung dessen, was zu beweisen ist.

    Trotzdem könnte der gewählte Ansatz, dass es einen kürzeste Strategie gibt und man daraus einen Widerspruch ableitet, zielführend sein.

    Vielleicht sollte ich diesen Satz noch etwas mehr erklären: "Es ist gar nicht möglich, dass B_n-1 und C_n-1 bestimmte Werte einnehmen für alle möglichen Ausgangsverteilungen."


    Nennen wir fn(B) den Zustand von B nach n definierten Würfen. Egal welche Würfe Santa auch macht, fn(B) hängt immer von der unbekannten Ausgangsverteilung ab. Insbesondere ist fn(B) = 0 wenn man nur Atome ohne Higgs Bosonen hat und fn(B) = 1 wenn man nur Atome mit Higgs Bosonen hat. Aber genauso ist fn(C) = 0 wenn man nur Atome ohne Higgs Bosonen hat und fn(C) = 1 wenn man nur Atome mit Higgs Bosonen hat. Also sind sowohl bei (0 0 0 0 0 0) als auch bei (1 1 1 1 1 1) die Belegung von B und C gleich. Und das steht im Widerspruch zu den Schlussfolgerungen, die für die beiden Fallunterscheidungen gemacht wurden.

    Ist das überzeugender?


    Es ist so etwas wie ein Induktionsbeweis: Wenn Santa es nach n Würfen nicht weiß, wird er es auch nach n+1 Würfen nicht wissen können.

    Dass es mit Sortieren nicht geht, heißt nicht, dass es nicht (anders) gehen könnte ... Es ist kein Beweis, einen Weg auszuschließen. Für einen Beweis muss man alle denkbaren Wege ausschließen.

    Ist das ein akzeptabler Beweis:


    Nach n throws behauptet Santa Teil A wäre gleich dem Teil B. Da n die minimale Anzahl ist,

    muss A und B nach n-1 throws noch unterschiedlich gewesen sein.

    Es gibt also nur 2 Fälle für den letzten throw: B_n-1 auf C_n-1 oder C_n-1 auf B_n-1

    (o.B.d.A. nehmen wir an, dass B sein Zustand geändert hat und nicht A;

    Der Wurf A auf B oder umgekehrt, würde die relative Parität von A und B nicht verändern,

    den Fall kann man auch ausschließen).


    Also Fall 1: B_n-1 auf C_n-1 mit Vorzeichenwechsel von B.

    Daraus folgt dass B_n-1 = 0 und C_n-1 = 1 (die einzige Möglichkeit, wo der Geworfene sein Vorzeichen wechselt).


    Fall 2: C_n-1 auf B_n-1 mit Vorzeichenwechsel von B. Daraus folgt dass B_n-1 = 1 und C_n-1 = 0.


    Und jetzt kommt der Knackpunkt:

    Es ist gar nicht möglich, dass B_n-1 und C_n-1 bestimmte Werte einnehmen für alle möglichen Ausgangsverteilungen.

    Zum Beispiel wenn man nur Einsen oder nur Nullen hat, kann nicht das eine Teil 0 und das andere 1 werden.

    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.