21: Xmasium

  • 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.

  • 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.

    Ok, das könnte funktionieren. Bei deinem konkreten Argument bin ich aber noch nicht überzeugt:

    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.

    Die beiden Fallunterscheidungen basieren doch auf der Tatsache, dass A und B nach n-1 Würfen unterschiedlich sind. Aber auch das ist nicht für alle, sondern nur für manche Anfangsverteilungen wahr. Insbesondere für (0 0 0 0 0 0) und (1 1 1 1 1 1) nicht. Deshalb führen diese Anfangsverteilungen meiner Ansicht nach auch nicht zu einem Widerspruch ...

  • Die beiden Fallunterscheidungen basieren doch auf der Tatsache, dass A und B nach n-1 Würfen unterschiedlich sind. Aber auch das ist nicht für alle, sondern nur für manche Anfangsverteilungen wahr. Insbesondere für (0 0 0 0 0 0) und (1 1 1 1 1 1) nicht. Deshalb führen diese Anfangsverteilungen meiner Ansicht nach auch nicht zu einem Widerspruch ...

    Ja, aber Ruprecht braucht ja eine Methode, die für jede Anfangsverteilung funktioniert. Daher reicht es schon, zu beweisen, dass es für mindestens eine Anfangsverteilung keine Lösung gibt, bzw. dass jeder Lösungsweg für mindestens eine Anfangsverteilung nicht funktioniert.

  • Ja, aber Ruprecht braucht ja eine Methode, die für jede Anfangsverteilung funktioniert. Daher reicht es schon, zu beweisen, dass es für mindestens eine Anfangsverteilung keine Lösung gibt, bzw. dass jeder Lösungsweg für mindestens eine Anfangsverteilung nicht funktioniert.

    Ja, klar. Was ich meine, ist dass die Anfangsverteilungen (0 0 0 0 0 0) und (1 1 1 1 1 1) nie zu einem Widerspruch führen.

    Der Aussage

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

    stimme ich zu. Jedoch hilft das nicht beim Beweis, denn dafür müssten wir zeigen:

    Zitat

    "Es ist gar nicht möglich, dass B_n-1 und C_n-1 bestimmte Werte einnehmen für alle möglichen Ausgangsverteilungen, bei denen A_n-1 und B_n-1 unterschiedlich 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.

    Dieser Beitrag wurde bereits 1 Mal editiert, zuletzt von RüdiJ () aus folgendem Grund: Santa wurde durch Ruprecht ersetzt

  • 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)

  • 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!

    Dieser Beitrag wurde bereits 1 Mal editiert, zuletzt von RüdiJ () aus folgendem Grund: Sorry, ich meinte Ruprecht und nicht Santa

  • 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).

  • Santa 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!

    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.

  • 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.

  • 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.

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

    Da wäre ich mir nicht so sicher, ob das schon gezeigt ist.

    Dafür müsste man die Situation, dass beim letzten Wurf ein Vorzeichenwechsel stattfindet, zum Widerspruch führen. Wie oben können wir zwar folgern dass es ein weiteres Atom C geben muss sodass B und C wechseln.

    Doch da wir die Situation "beim letzten Wurf findet ein Vorzeichenwechsel statt" betrachten, sind die Anfangsverteilungen 000000 und 111111 ohnehin ausgeschlossen, und führen daher nicht zu einem Wiederspruch...

  • 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.

  • 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 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!)

    B_n "darf" ja auch 0 sein, ohne einen Widerspruch zu erzeugen. Diesen bekommt man erst, wenn gleichzeitig beim (n+1)-ten Wurf ein Vorzeichenwechsel erfolgen soll (aber das ist ja bei der angeführten 000000-Startkonfiguration nicht der Fall).


  • 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.

  • 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.

  • 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)

    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.

  • 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.

  • Bn ist also nicht die 6x64 Matrix sondern ein einziger Zustand. [...] Also gibt es nur 2 Fälle für den letzten Wurf: Bn auf Cn oder Cn auf Bn

    Dieser eine Zustand muss dann aber eben einer sein, bei dem sich beim letzten Wurf sich etwas ändert.

    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.

    Die Anfangskombination (0 0 0 0 0 0) führt aber zu einem Zustand bei dem sich beim letzten Wurf nichts ändert.




    Wenn ich es richtig verstehe geht die Argumentation wie folgt:


    Zitat

    Es muss einen Zustand (= mögliche Anfangskombination K) geben, sodass beim letzten Wurf A oder B den Zustand wechseln. [sonst wäre die Länge nicht minimal]

    OBdA wechselt B den Zustand.

    => Es gibt eine Anfangskombination K, sodass beim letzten Wurf B und ein weiteres Atom C den Zustand tauschen. (*)


    Wenn die Anfangskombination (0 0 0 0 0 0) ist, ist es nicht möglich, dass beim letzten Wurf B und C den Zustand tauschen. (**)

    Nur widersprechen sich die Aussagen (*) und (**) eben nicht. [Die Anfangskombination K kann sowieso nicht (0 0 0 0 0 0) sein...]