21: Xmasium

  • Ich bin relativ schnell zu der Erkenntnis gekommen, dass es nicht gehen kann.

    Dann habe ich im Forum gelesen, dass einige einen Geistesblitz hatten und das Rätsel dann lösen konnten.

    Daraufhin war ich mir nicht mehr sicher und habe 2 Wochen immer wieder nachgedacht, wie es vielleicht gehen könnte, und war total gespannt auf die Lösung.

    Irgendwie bin ich jetzt froh, dass ich recht hatte und auch ein wenig enttäuscht, dass es keinen genialen Trick gibt ;)

    Oh-weh, ich hoffe das war nicht ich - täte mir unendlich leid.


    Ich hatte recht schnell raus, das es eigentlich nicht gehen kann, da man durch die Würfe zwar für alle beliebigen Konstellationen die Atome immer sortiert bekommt, aber eben niemals so, dass es bei egal welcher Konstellation eine Stelle in der Reihe gibt, an der immer zwei gleiche Atome liegen.

    Damit war die Aufgabe gelöst und ich hatte das geschrieben.


    Solange die Anfangskonstellation (also die Anzahl des jeweiligen Isotops) nicht bekannt ist, kann das Problem für alle erdenklichen Atommengen nicht gelöst werden.

  • Ich glaube der Ansatz lässt sich zu einem Beweis erweitern.

    Angenommen, man könnte dafür sorgen, dass oBdA X1=X2 gilt und ich nenne die beiden einfach A und B. Dann lässt sich die Liste nach dem Prinzip Bubble Sort sortieren. In der einfachsten Variante geht man 6 Mal durch die Liste und vertauscht X1 und X2, wenn nötig, dann X2 und X3 usw. Das Vertauschen wenn nötig lässt sich durch genau einen Wurf durchführen.


    Immer wenn A mit einem anderen Atom vertauscht wird, muss B auch mit diesem vertauscht werden, da A und B gleich sind, und es kann sich kein Atom dazwischen schieben. Also sind sie nach dem Sortieren immer noch in aufeinanderfolgenden Positionen, aber wie mr.x ja schon gesagt hat, ist das unmöglich und somit die Annahme am Anfang falsch.


    Edit: Ich glaube der Beweis ist falsch. Dass es unmöglich ist, die Aufgabe zu lösen und die Liste gleichzeitig zu sortieren liegt nicht (notwendigerweise) daran, dass die Aufgabe an sich unmöglich ist. Es ist schon aus dem Grund nicht möglich, dass man nach dem Sortieren nicht mehr weiß, an welcher Stelle die beiden gleichen Atome sind, das verfehlt ja den Sinn der Aufgabe.

  • Danke. Ich verstehe, dass man bei einem Bubble-Sort kein Element zwischen A und B bekommt. Aber ich verstehe leider immer noch nicht, warum dies zwingend beweist, dass auch ein Ansatz ohne Sortierung nicht erfolgreich sein kann, oder wenn man sortiert, warum dann mit Bubble-Sort ... . Ich werde mir nochmals in Ruhe alles bisher Geschriebene zu diesem Thema ansehen. Und mit etwas Zeit und Muße am Wochenende wird sich vielleicht die große Einsicht einstellen.

  • Der Ausschluss des Sortierens alleine reicht als Beweis nicht aus. Ein anderer Denkbarer Ansatz wäre eine Art divide-et-impera, also eine Aufteilung der sechs Atome in Untergruppen. Das hatte ich mir auch noch überlegt, war dabei aber zu dem Schluss gekommen, dass innerhalb jeder Untergruppe das gleiche Problem wie bei den sechs Atomen vorliegt, und dass ich auch keinen Nutzen daraus ziehen kann, z.B. aus zwei Untergruppen jeweils das erste Atom zu nehmen, weil ich keine Aussagen über diese Atome machen kann, ohne Informationen über die Arten der Atome in den Untergruppen zu haben. Das ist immer noch kein Beweis, aber schon mal ein Schritt weiter, der mir dann ausgereicht hat, mich für die Antwort 10 zu entscheiden.

  • Doch, der Ausschluss der sortierten Variante reicht als (Gegen-)Beweis aus, weil es ja auch im urprünglichen Zustand sortiert vorliegen könnte. Man kann also zeigen, dass es für die 5 möglichen Ausgangssituationen

    00001

    00011

    00111

    01111

    nicht möglich ist, zwei gleiche zu erhalten. Da jede mögliche Operation nur die Spalten vertauschen würde und man damit keine zwei gleichen Spalten erhalten kann. Ob es dann für andere Anfangskonstellationen möglich wäre ist egal.

  • Man sollte fairerweise noch 000000 und 111111 hinzunehmen.

  • Exakt. Durch das Sortieren kann man jedes Verhältnis von "schweren" und "leichten" X-Masium Atomen (jede Konstellation) immer und O.B.d.A. in eine solche Reihenfolge bringen. Den Beweis hierzu überlasse ich dem Leser. Da die Anzahl der 0 oder 1 X-Masium Atome aber nicht bekannt ist, gibt es kein weiteres Kriterium nach dem bestimmbar wäre, welche benachbarten Spalten in dieser Darstellung zwei gleiche X-Masium Isotope haben.

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

    Ich würde mal davon ausgehen, dass das Sortieren durch eine Folge von Würfen eine eindeutige Abbildung des Anfangszustands auf den sortierten Zustand ist. Damit muss jeder Weg zwei gleiche X-Masium Atome zu ermitteln sich auch auf dem sortierten Zustand durchführen lassen. Wenn es aber auf dem sortierten Zustand unmöglich ist, ist es auch auf jedem anderen Weg unmöglich.

  • Wieso sollte man das? Und wieso wäre das irgendwie fair?

    Die Konstellationen mit nur 0 und nur 1 X-Masium (um in der hier verwendeten Notation zu bleiben) wurden in der Aufgabe nicht ausgeschlossen.


    Irgendwie finde ich es fair (warum kann ich auch nicht genau sagen - ist vielleicht auch der englischen Redewendung entlehnt), bei einer Lösungsdiskussion, die ja für alle Teilnehmer und auch zum Vergleich mit ihren jeweiligen Ansätzen gedacht ist, das vollständige Problem zu beleuchten.

  • Die Konstellationen mit nur 0 und nur 1 X-Masium (um in der hier verwendeten Notation zu bleiben) wurden in der Aufgabe nicht ausgeschlossen.


    Irgendwie finde ich es fair (warum kann ich auch nicht genau sagen - ist vielleicht auch der englischen Redewendung entlehnt), bei einer Lösungsdiskussion, die ja für alle Teilnehmer und auch zum Vergleich mit ihren jeweiligen Ansätzen gedacht ist, das vollständige Problem zu beleuchten.

    Verstehe ich nicht. Es reicht völlig, die genannten 5 Konstellationen zu betrachten. 101010 wird ja auch nicht betrachtet, ist das auch unfair?

  • Problematisch sind eigentlich nur die Fälle 0 0 0 0 0 1 und 0 1 1 1 1 1. In jedem andern Fall findet man zwei gleichartige Atome, indem man nach dem Sortieren die ersten beiden bzw. die letzten beiden Atome wählt.

    Dem will ich mich nicht anschließen. Ich behaupte jetzt:

    Problematisch ist nur der Fall 0 0 0 1 1 1 nach dem Sortieren. In jedem anderen Fall kann ich die beiden mittleren Atome wählen. :P

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

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

    Das würde ich so nicht sagen: n ist nur die minimale Länge einer Strategie, die für jeden Anfangszustand gerantiert, dass A_n und B_n gleich sind.

    Wenn man nur n-1 Würfe macht, muss es zwar einen Anfangszustand geben, sodass A_n-1 und B_n-1 unterschiedlich sind, aber es kann natürlich auch sein, dass A und B gleich sind (z.B. für die Anfangszustände 000000 oder 111111).

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