21: Xmasium

  • Nach ein paar vergeblichen Anläufen zwei Atome desselben Typs zu extrahieren, stieß ich auf ein grundsätzliches Problem:

    Invarianz-Prinzip: Zeichnet man sich alle 7 verschiedenen möglichen Verteilungen (0-6 Atome mit Higgs-Boson) untereinander auf (siehe Tabelle in der Lösung), erkennt man schnell das Problem: Ein Wurf permutiert nur die Spalten, pro zwei Spalten bleibt immer mindestens ein ungleiches „Pärchen“. Diese Eigenschaft ist sozusagen „invariant unter Wurf“. Zur Identifizierung zweier Atome müsste man jedoch durch „Würfe“ zwei Spalten exakt gleich hinbekommen! Dadd jeht nicht!


    Nebenbei: Die allererste Kalenderaufgabe die mir begegnet (bin seit 2009 am Start), bei der man beweisen/ einsehen musste, dass etwas nicht geht. Ungewohnt J


    Hier etwas ausführlicher dargestellt:

    https://www.dropbox.com/s/8os6…nvarianz-Prinzip.JPG?dl=0

  • Nebenbei: Die allererste Kalenderaufgabe die mir begegnet (bin seit 2009 am Start), bei der man beweisen/ einsehen musste, dass etwas nicht geht. Ungewohnt J

    Ich fand das auch überraschend und originell. Derartige Aufgaben sollten im MATH+ Adventskalender öfter kommen!

  • Bei mir war die Überlegung so:


    Ich bekomme alle Xmasium-Atome mit Higgs-Boson ("Typ 1") und ohne Higgs-Boson ("Typ 2") sortiert, indem ich die Atome im Kreis anordne und dann die Atome im Uhrzeigersinn bewerfe. Nach einer Runde ist am am Ende eines mit Typ 1, falls ein solches existiert. Und so weiter...


    Also nach n Schritten sind alle sortiert.


    Diese reihe ich nun auf. Das erste Typ 1 (falls existent) links und so weiter.


    Kann diese Reihe irgendwo splitten (Schnitt setzen) und links davon oder rechts davon sind nur Typ1 oder Typ2 Atome?


    Nein - das geht nicht. Egal wo ich den Schnitt setze könnte partout die Atom-Ausgangskonstellation (Anzahl Typ1/Typ2-Atome) einen Strich durch die Rechnung machen.

  • Es reicht, fünf mögliche Startkonstellationen anzuschauen (mit 1 bis 5 Bosonen, jeweils "ganz vorne" zum Beispiel). Hier gibt es keine 2 Atome, bei denen man sicher ist, dass sie gleichen Typ haben.

    Jeder Wurf ist nur eine Permutation bzw. Umnummerierung der Atome davon, d.h. man findet immer noch keine 2 Atome, die gleichen Typ haben müssen - schon unter den 5 betrachteten Startkonstellationen.

  • Hier mein Python-Code, der eventuell schwer verständlich ist.

    Den Zustand der 6 Xmasium-Atom codiere ich durch eine Binärzahl zwischen 0 und 63. Als "Zustaende" bezeichne ich nun die Menge aller möglichen Zustände nach Ausführung gegebener Würfe. Jeder Wurf überrführt "Zustaende" in neue mögliche "Zustaende". Dies kann durch einen gerichteten Graphen modelliert werden. Die Knoten sind die "Zustaende" und die Kanten die Würfe. Durch Ausnutzen von Symmetrien muss ich nicht alle 557803 Knoten des Graphen einzeln betrachten. Dadurch liefert das Programm die Antwort in gut einer Minute.


  • Hier noch meine Betrachtung, warum das nicht geht:

    (X1,X2,X3,X4,X5,X6) seien die Zustände der Atome mit 1: mit Boson, 0 = ohne Boson.


    Dann könnten auch folgende 7 Verteilungen auftreten:

    (0,0,0,0,0,0)

    (1,0,0,0,0,0)

    (1,1,0,0,0,0)

    (1,1,1,0,0,0)

    (1,1,1,1,0,0)

    (1,1,1,1,1,0)

    (1,1,1,1,1,1)


    Man könnte jetzt 2 Atome als identisch charakterisieren, wenn sie denselben Wert haben. Vergleicht man aber Xa mit Xb (a,b von 1 bis 6), so gibt es immer eine Verteilung mit Xa <> Xb.

    Senkrecht betrachtet sind das unterschiedlich hohe "Türmchen" aus 1en. X1 hat sechs 1en, X2 fünf, usw. bis X6 hat eine 1.


    Wenn wir jetzt Xa auf Xb werfen mit a > b, so verändert sich diese Verteilung nicht... also kann man weiterhin keine 2 identischen Atome finden.


    Wenn wir jetzt Xa auf Xb werfen mit a < b, so vertauschen sich einfach nur die Türmchen, also aus dem Xa wird Xb und umgekehrt. Aber noch alle Türmchen mit Höhen 1 bis 6 kommen vor. Daher sind weiterhin keine identischen Atome identifizierbar.


    Und mehr kann man nicht machen... alles was man machen kann verändert nicht den Aufbau aus 7 möglichen Verteilungen mit unterschiedlich hohen 1er-"Türmchen". Damit genügen des Knecht Ruprecht nicht, um bei allen möglichen Verteilungen (also auch bei diesen 7) zwei identische Atome zu finden.

  • Vorab - das war die einzige Aufgabe, die ich nicht gelöst bekommen habe. Stundenlanges Rumprobieren, keine Strategie gefunden (was dazu geführt hab, dass ich glücklicherweise auch das richtige Kästchen angekreuzt habe).


    Ich habe jedoch gestern noch einen Programmieransatz verfolgt, den ich trotzdem gerne teilen möchte, weil vielleicht hilft er dem ein oder anderen ja mal bei ähnlichen Aufgaben.


    Mein Ziel war es, irgend eine günstige Strategie zu finden. Mir war schnell klar, dass Brute-Force hier unmöglich ist, zumindest für die größeren n. Deshalb war meine Idee, zufällig eine Strategie zu erwürfeln - also für eine Strategie, die aus n Würfen besteht, zufällig zu bestimmen, welches Atom auf welches geworfen werden muss. Und diesen Zufallsversuch führt man k mal durch und prüft danach für alle 64 Zustände der Atome, ob es funktioniert oder nicht. Wenn man sich vorher überlegt, wieviele mögliche Strategien mit n Würfen es gibt, und wieviele davon günstig sind (vorausgesetzt, es gibt eine günstige Strategie), kann man sich stochastisch errechnen, wie groß k sein muss, damit man mit (z. B.) 80%-iger Wahrscheinlichkeit eine günstige Strategie findet.


    Für dieses Rätsel scheitert die Strategie aus Laufzeitgründen leider schon bei n > 8 (wenn man so viel wie möglich optimiert), aber mit etwas Glück hätte die Antwort ja dabei sein können.

  • Man betrachte die 6 Fälle in den folgenden 6 Zeilen:

    100000

    110000

    111000

    111100

    111110

    111111

    Die Spalten sind paarweise verschieden. (Sonst wären wir schon fertig.)


    Wir betrachten die obige Ausgangssituation als Matrix. Der Rang der Matrix ist 6, der Betrag der Determinante ist 1.

    Durch Werfen kann man nur Spalten vertauschen. Dies lässte den Rang und den Betrag der Determinante unverändert.

    Unser Ziel ist es, zwei gleiche Spalten zu erhalten. Dann müsste der Rang kleiner werden und die Determinante gleich 0 werden. Dies ist durch Vertauschen von Spalten nicht zu erreichen.

  • Ich habe das Problem auf drei Atome runtergedampft. Wenn ich da eine Strategie finde, kann ich sie erweitern. Und damit alles mögliche angestellt, unter anderem auch systematisch alle Varianten von bis zu 8 Würfen durchprobiert. Einfach, weil ich nicht glauben könnte, dass 'geht nicht' richtig sein kann.

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

  • Dass die Aufgabe unmöglich ist, wirft jetzt noch mehr Fragen auf.

    Allgemein gibt es 2 verschiedene "Reaktionsvorgaben", die festlegen, ob ein Higgs-Boson übertragen wird oder nicht und jeweils eine weitere Vorgabe, die durch Vertauschen der beiden Atome A und B entsteht.

    Eine davon ist die Identität, die offensichtlich die gestellte Aufgabe unmöglich macht, und die andere ist die aus der Aufgabe, bei der es auch unmöglich ist, zwei gleiche Atome zu erhalten.

    Um eine Lösung zu finden, fällt mir die Operation auf drei Atome ein, die dafür sorgt, dass die ersten beiden dieser Atome gleich sind, und dann ist die Aufgabe durch einen Wurf lösbar. Gibt es da auch nichttriviale Lösungen (wie man so schön sagt)?

  • Eine super Lösung. :thumbsup::thumbsup:

  • Dass die Aufgabe unmöglich ist, wirft jetzt noch mehr Fragen auf.

    Allgemein gibt es 2 verschiedene "Reaktionsvorgaben", die festlegen, ob ein Higgs-Boson übertragen wird oder nicht und jeweils eine weitere Vorgabe, die durch Vertauschen der beiden Atome A und B entsteht.

    Eine davon ist die Identität, die offensichtlich die gestellte Aufgabe unmöglich macht, und die andere ist die aus der Aufgabe, bei der es auch unmöglich ist, zwei gleiche Atome zu erhalten.

    Um eine Lösung zu finden, fällt mir die Operation auf drei Atome ein, die dafür sorgt, dass die ersten beiden dieser Atome gleich sind, und dann ist die Aufgabe durch einen Wurf lösbar. Gibt es da auch nichttriviale Lösungen (wie man so schön sagt)?

    Die Aufgabe ist auch für drei Atome nicht lösbar.

  • Die Aufgabe mit den ursprünglichen Regeln ist für keine Zahl von Atomen lösbar, das stimmt.
    "Die Operation auf drei Atome" sollte eine Operation mit den gleichen Eigenschaften wie in er Aufgabe gegenen beschreiben, bei der drei anstatt zwei Atome "geworfen" werden. Das heißt, diese Operation bildet {0; 1}3 auf sich selbst ab, ist nicht (notwendigerweise) kommutativ und erhält die Summe der Argumente.

    Es gibt dann eine solche Operation, die auf drei Atome x, y, z genau einmal angewandt werden muss und dafür sorgt, dass danach x' = y' gilt. z sorgt für die Invarianz der Summe x+y+z. Die Frage war, welche anderen solchen Operationen die gegebene Aufgabe lösbar machen.