10: Xmasium

  • Hier meine Lösung dieser wirklich tollen Aufgabe:


    Es genügen 16 Atome mit jedes Atomgewichts g. Die Verteilung auf die Schritte ist wie folgt:


    Schritt k
    4g - 3
    4g - 2
    4g - 1
    4g 4g + 1 4g + 2
    4g + 3
    Benötigte Atome mit Gewicht g
    1 2 3 4 3 2 1



    Man kann sich leicht verdeutlichen, dass das Schema funktioniert: Beispielsweise setzt sich der Schritt 11 zusammen aus 1 Atom des Atomgewichts 2 (k = 11 = 4 * 2 + 3) und 3 Atomen des Atomgewichts 3 (k = 11 = 4 * 3 - 1). Somit also Gesamtatomgewicht der Runde 11: 1 * 2 + 3 * 3 = 11.



    Beweis, dass es kein Schema gibt, welches mit weniger als 16 Atomen jedes Atomgewichts auskommt:


    Annahme: Für die Atomgewichte 0, 1, 2, ..., 18, 19 stehen jeweils maximal 15 Atome zur Verfügung. Das sind insgesamt 300 Atome. Damit ergibt sich in der Summe ein Minimalgewicht für 300 Atome von 19 * 20 / 2 * 15 = 190 * 15 = 2850.


    Man betrachte nun die ersten 76 Schritte. Die Summe der Atomgewichte all dieser Schritte beträgt 76 * 77 / 2 = 2926. Dafür müssen insgesamt 76 * 4 = 304 Atome entnommen werden. Das Minimalgewicht für 300 Atome beträgt aber 2850. Die restlichen 4 Atome dürfen also zusammen nicht mehr als 76 wiegen.
    Allerdings sind die Atomgewichte 0 ... 19 bereits ausgeschöpft. Das minimal noch zur Verfügung stehende Atomgewicht wäre somit 20. 4 * 20 ist aber bereits 80. Wenn also maximal 15 Atome von jeder Sorte zur Verfügung stünden, würde die Entnahme für Schritt 76 nicht mehr funktionieren.


    16 Atome jeder Sorte ist damit die Minimallösung.

  • Ich hatte exakt den gleichen Beweis, allerdings hatte es etwas gedauert bei mir. Der Witz an dieser Aufgabe war, dass man die 16 schnell hatte, der Beweis für die Optimalität aber nicht so einfach zu sehen war, zumindest für mich.

    Man kann das noch schön verallgemeinern, im Prinzip mit der angegebenen Argumentation:


    Sei n die Anzahl der in jedem Schritt zu kombinierenden Atome (in der Aufgabe ist n = 4). Dann gilt:


    1) Die Anzahl benötigter Atome pro Atommasse ist n2

    2) Die max. Anzahl von Schritten, wenn man nur n2 - 1 Atome pro Atommasse zulässt, ist (n + 1)2 (n-1)

  • Dieser Tag hat mich fast zur Verzweiflung gebracht, weil ein Beweis für meine Lösung (16) schwierig war. Zunächst, wie komme ich auf 16?


    Für jede Gesamtmasse 4*n ziehe ich 4 Atome mit Masse n, für jede Gesamtmasse 4*n+1 ziehe ich 3 n-Atome und ein n+1-Atom usw. Dann brauche ich genau 6 Nullen und 16 von jeder anderen Masse. Ich habe lange darüber gerätselt, ob die Tatsache, dass man zehn Nullatome „verschwendet“ es einem bis ins Unendliche erlaubt, mit 15 Atomen pro Masse auszukommen, oder ob man damit eben nur endlich weit kommt. Der Beweis ist dabei erstaunlich kurz:


    Will Knecht Ruprecht n Schritte ziehen, zieht er insgesamt 4n Atome. Diese haben nach Gauß eine Gesamtmasse von n*(n+1)/2. Nehmen wir an, es gäbe eine Strategie, bei der genau alle N Atome der Massen 0 bis m_max genutzt werden (jede tatsächlich mögliche Strategie kann dann auf keinen Fall weniger Atome pro Masse benötigen, höchstens mehr. Wenn also ein krummen N herauskommt, muss aufgerundet werden). Dann hätten diese eine Gesamtmasse von (N * m_max * (m_max + 1))/2 bei einer Gesamtanzahl von N*(m_max+1) Atomen. Es gilt also

    4n = N*(m_max+1) (I)

    n*(n+1)/2 = (N * m_max * (m_max + 1))/2 (II)

    Teilen wir (II) durch (I) [n ist offensichtlich >0] folgt

    (n+1)/8 = m_max/2 <=> m_max = (n+1)/4 (III)

    Aus (I) folgt wiederum mit Einsetzen von (III)

    N = 4n/(m_max+1) = 16n/(n+5) = 16/(1+5/n)

    Für n gegen Unendlich läuft N offensichtlich gegen 16. Spannend ist noch, bis wohin man mit 15 Atomen kommt. Dazu setzen wir 15=N und erhalten n=75, wofür sich tatsächlich eine Verteilung finden lässt, die wie behauptet jedes Atom von Masse 0 bis 19 exakt 15mal benötigt.

  • Sehr interessante Ableitungen mit richtigen Ergebnissen, nur, ein Beweis ist es nicht. Es hat sowas Euler-haftes an sich: unexakt aber intelligent argumentiert mit richtigem Ergebnis (16, 75).

    Denn: "Nehmen wir an, es gäbe eine Strategie, bei der genau alle N Atome der Massen 0 bis m_max genutzt werden" - darf man das denn einfach so annehmen? Ich meine: nein.


    Ich will hier aber nicht als Mecker-Heini dastehen. Natürlich ist es möglich, dass ich was nicht oder falsch verstehe oder einen Zusammenhang nicht sehe.


    Der Beweis von Pi mal Daumen ist - meine ich - völlig korrekt.

  • Genau den entscheidenden Satz hast du dann nicht zitiert: "jede tatsächlich mögliche Strategie kann dann auf keinen Fall weniger Atome pro Masse benötigen". Ich wollte also nicht sagen, dass eine optimale Strategie existiert, sondern nur erstmal ausrechnen, wie viele man bei einer solchen bräuchte. Jede nicht optimale Strategie braucht dann mehr. Wenn selbst optimal nur 75 Züge mit 15 Atomen/Masse möglich sind, sind es in der Realität auf jeden Fall auch nur so viele.

  • Genau den entscheidenden Satz hast du dann nicht zitiert: "jede tatsächlich mögliche Strategie kann dann auf keinen Fall weniger Atome pro Masse benötigen". Ich wollte also nicht sagen, dass eine optimale Strategie existiert, sondern nur erstmal ausrechnen, wie viele man bei einer solchen bräuchte. Jede nicht optimale Strategie braucht dann mehr. Wenn selbst optimal nur 75 Züge mit 15 Atomen/Masse möglich sind, sind es in der Realität auf jeden Fall auch nur so viele.


    Wie lautet denn die Definition einer "optimalen Strategie"? Woran erkennt man eine "optimale Strategie"? Und wie unterscheidet sie sich von einer Strategie "n der Realität"?

  • Genau den entscheidenden Satz hast du dann nicht zitiert: "jede tatsächlich mögliche Strategie kann dann auf keinen Fall weniger Atome pro Masse benötigen". Ich wollte also nicht sagen, dass eine optimale Strategie existiert, sondern nur erstmal ausrechnen, wie viele man bei einer solchen bräuchte. Jede nicht optimale Strategie braucht dann mehr. Wenn selbst optimal nur 75 Züge mit 15 Atomen/Masse möglich sind, sind es in der Realität auf jeden Fall auch nur so viele.

    Diese Anmerkung in Klammern ist mir nicht entgangen. Nur: es bleibt dabei: Du nimmst etwas an, dessen Existenz nicht bewiesen ist. Worauf du abzielst, ist mir schon klar: Wenn wir für diesen Fall eine bestimmte Abschätzung bekommen, dann erst recht bei allen anderen Strategien. Aber, wie gesagt, der Ausgangspunkt ...

    Und: "jede tatsächlich mögliche Strategie kann dann auf keinen Fall weniger Atome pro Masse benötigen" - wenn man m_max nicht verändert.


    Aber wir wollen hier nicht streiten, vielleicht hast du doch recht und ich sehe das irgendwann ein. Schon möglich.

  • Ich habe es mir so verdeutlicht:


    Gesamtgewicht - Atomgewichte der vier Atome


    1 - 0 0 0 1

    2 - 0 0 1 1

    3 - 0 1 1 1

    4 - 1 1 1 1

    5 - 1 1 1 2

    6 - 1 1 2 2

    7 - 1 2 2 2

    8 - 2 2 2 2

    9 - 2 2 2 3

    ...


    Dieses lässt sich ewig fortsetzen.

    Nun zähle ich die benötigten 1er-Atome, denn gleiches gilt ja auch für alle folgenden und komme auf 16!


    Das dürfte dem ziemlich ähnlich sein, was "Pi mal Daumen" oben vorgestellt hat, nur für mich als Laien etwas anschaulicher.

    Die Lösung war so "schön", dass sie einfach richtig sein musste - deshalb verweise ich für den Beweis, dass man nicht mit weniger auskommen kann auch auf meine Vorredner... :saint:


    Tolle Aufgabe!!!!

  • Ja, ist schon eine tolle Aufgabe.

    Deine Aufteilung (und die von Pi mal Daumen) ist sozusagen die gleichmäßigste, die man haben kann. Rechnerisch bekommt man sie so:


    z1 = n / 4

    z2 = (n - z1)/3

    z3 = (n - z1 - z2)/2

    z4 = n - z1 - z2 - z3


    alle Divisionen ganzzahlig.


    So kommt man ganz schnell auf die 16er-Lösung. Ich war mir auch sicher, dass es die Lösung der Aufgabe war, nur fehlte der Beweis. Und dann kam ein Zweifel: vielleicht ist das der Gag der Aufgabe; man denkt sofort, 16 muss es sein, aber es gibt doch eine geschickte Strategie, die mit 15 auskommt. Ich hab's dann probiert, mit 15 auszukommen, und siehe da, zunächst schien es fast, als würde man mit 15 hinkommen, denn erst nach 75 Schritten brach das System zusammen. Das hatte zwei gute Effekte. Erstens war wohl 16 doch richtig und zweitens wurde mir klar, wie man das auch beweisen kann. Es ist der Pi mal Daumen - Beweis von oben. Außerdem hat Math5d oben noch einen etwas anderen Beweis geliefert.

    Mathematisch wahrscheinlich eine der interessantesten Aufgaben in diesem Kalender.

  • Ein ganz anderer Ansatz, den ich leider nicht beweisen konnte, aber auch nicht widerlegen konnte durch ein Gegenbeispiel - vlt gelingt das eine oder andere einem Forumteilnehmer?


    Der Widerspruchsbeweis für N=15: System bricht nach 75 Schritten zusammen ist natürlich hübsch und wasserdicht :thumbsup:.


    Meinen Ansatz nenne ich "Freistellen-Erhaltung bzw Masse-Erhaltung". Ich habe verschiedene Lösungen für N=16 gefunden, zwei davon habe ich im Download angegeben. Alle Ansätze haben gemeinsam, dass es genau 10 "Freistellen" gibt: Der kanonische von den meisten gefundene Ansatz hat ja 6 Nuller, dann 16 1er, 2er etc. das heißt nur die Nuller werden weniger oft als 16 Mal benötigt: genau 6 Mal, ich nenne das mal: 10 Freistellen: 16-6=10.
    Anfangs sah ich da Luft und überlegte, ob das optimal ist, bis mir auffiel, dass auch bei allen anderen Lösungen genau 10 Freistellen auftreten: Man kann sie denke ich nur verschieben (Masse-Erhaltung). Für N=15 bräuchte man aber unendlich viele solcher Freistellen. Wie gesagt, kein Beweis, nur eine Vermutung.


    Hier ist das veranschaulicht:

    https://www.dropbox.com/s/3vmw…um_W%C3%B6ginger.JPG?dl=0

  • ... dass auch bei allen anderen Lösungen genau 10 Freistellen auftreten: Man kann sie denke ich nur verschieben (Masse-Erhaltung). Für N=15 bräuchte man aber unendlich viele solcher Freistellen ...


    ... invariante Zahl von "Freistellen" bei unendlichen Aufzählungen. Ein hübscher Gedanke, aber wirklich kühn, Hilberts Hotel lässt grüßen :)

  • Interessante Idee. Allerdings gibt es - oder täusche ich mich? - eine Strategie, die ins Unendliche fortgesetzt, von allen Gewichten 16 Atome verbraucht, also keine Freistellen lässt.

    Strategie für die n-te Ziehung: für die ersten 3 Gewichte nehme man die kleinstmöglichen, ohne die Anzahl 16 zu überschreiten, für das 4. Gewicht den Rest, um in der Summe n zu haben. Das beginnt so:

    0 0 0 1

    0 0 0 2

    0 0 0 3

    ...

    0 0 0 5

    0 1 1 4 die 0en sind jetzt verbraucht

    1 1 1 4

    1 1 1 5

    1 1 1 6

    1 1 1 7

    1 2 2 6 nun auch die 1en

    2 2 2 6

    usw.

    Ich glaube, dieser Prozess lässt sich ins Unendliche fortsetzen, hab's aber nur bis n = 2000 getestet, nicht bewiesen.


    Dennoch: die Idee ist interessant, aber wie soll's formuliert werden? Beispielsweise könnte man fragen, ob die Anzahl von Freistellen eine obere Grenze hat (vielleicht 10?) und, wenn ja, welche.

  • Ich glaube, dieser Prozess lässt sich ins Unendliche fortsetzen, hab's aber nur bis n = 2000 getestet, nicht bewiesen.


    Ja, das lässt sich unendlich fortsetzen. Dafür hab ich einen wahrhaft phantastischen Beweis gefunden, der aber leider doch etwas zu lang für diesen Forenbeitrag ist :)



    Damit wäre schon mal pierrot's Vermutung geklärt. Für den zweiten Teil (obere Grenze der Anzahl der Freistellen) habe ich noch keine greifende Idee.

  • Der Beweis von Pi mal Daumen ist überzeugend, aber ich kann mir das (noch) nicht intuitiv vorstellen. Darf ich Euch meine Gedanken mal zeigen?


    Jeder (bitte verzeiht die abstrakt männliche Form!) hatte bisher einen 4er-Zyklus in seiner Konstruktionsvorschrift - irgendwie muss man die Unendlichkeit ja sortieren bei 4 Atomen...:|

    4 Atome im 4er-Zyklus sind freilich 16 Atome, bevor es wieder von vorne losgeht 8). In meiner Tabellendarstellung sieht man die 4er-Zyklen und ihr Fortschreiten, z.B. bei Pi mal Daumens Plan: https://www.dropbox.com/s/0d3iobdfn0ji7is/10_1.jpg?dl=0..

    Oder bei einem anderen Plan mit 3-4 Atomgewichten pro Runde: https://www.dropbox.com/s/98m0n3baf13bav7/10_2.jpg?dl=0.

    Und jetzt schaut Euch mal die Spalten an: In jeder Spalte (die ja für ein Atomgewicht steht) addieren sich die Zahlen (spätestens ab Spalte 3) auf 16! Warum wohl? Weil die bunten Blöcke (mit je 16 Atomen) immer um 1 nach rechts rutschen, so dass dadurch in jeder Atomgewicht-Spalte alle Spalten EINES bunten Blocks aufaddiert werden. Egal wie breit der bunte Kasten ist.

    Demnach MUSS nach meiner Auffassung jeder Plan, der überhaupt so einen Zyklus enthält, einen 4er-Zyklus haben, und dieser wiederum seine 16 Atome in jeder Spalte aufaddieren. Nicht mehr und nicht weniger als 16.

    Ist das ein Beweis? Könnte es auch zyklenfreie Pläne geben? :/ Edit: der von Ce1 vielleicht? Hab ihn noch nicht aufgemalt, geh jetzt ins Bett!

  • Könnte es auch zyklenfreie Pläne geben? :/ Edit: der von Ce1 vielleicht?

    Ja, es gibt sie, solch zyklenfreie Pläne, sogar unendlich viele.


    Aus obiger Analyse von Ce1's Folge (dass diese überhaupt wohldefiniert ist, sprich: dass die Konstruktionsvorschrift niemals über ihre eigenen Beine stolpert, wenn der rechte Summand kleiner/gleich den linken Summanden werden würde) folgt auch schon implizit, dass diese Folge zyklenfrei ist (und auch niemals in einen Zyklus führt).


    Für den weniger am Detail Interessierten sie hier mal nur das Ergebnis nachfolgender Überlegungen vorweggenommen:


    Zitat

    10 Freistellen ⟺ Zyklus der Länge 4.


    Weniger Freistellen resultieren in entsprechend vielen Drölfzahlketten und damit in zunehmend ungeordnetem, nichtzyklischen Verhalten. ... Erinnert mich irgendwie an den Beweis des Vierfarbensatzes...



  • Klingt wie bei Fermat: ... habe wunderbaren Beweis gefunden, leider fehlt mir der Platz ...


    Ich habe auch nach längerer Grübelei - gerade heute - und nach ausführlichem Testen einen Beweis dafür gefunden, dass "meine" Konstruktion funktioniert. Endlich, endlich. Die Stimmung ist gerettet!

    Jetzt sehe ich, dass du deinen Beweis öffentlich gemacht hast. Meine "Erkenntnisse" gehen in genau die Richtung deines Beweises. Allerdings habe ich es nicht aufgeschrieben. Die wesentliche Beobachtung ist zunächst mal, dass, so weit man auch geht, die Anzahl der rechten Summanden nie 4 überschreitet, damit also für die ersten drei Plätze diese Zahl immer mindestens 12 Plätze frei hat. Und je weiter man nach hinten geht, um so seltener werden die 3er, die vorne eben 13 Plätze frei haben, und damit die "Drölfzahlen" (habe ich das richtig verstanden?).

    Und um das zu beweisen, geht man durch die Fallunterscheidungen, die du angeführt hast.

    Wirklich witzig, aber ich war genau an dem Punkt, als ich deinen Beweis gefunden habe. Allerdings, wie schon angedeutet, die Details hätten noch einige Arbeit verlangt.


    Deine/eure Gedanken und Ideen zu "Freistellen" und "Drölfzahlen" muss ich mir noch genauer zu Gemüte führen. Ich werde mir jetzt mal ansehen, wie die Dinge liegen, wenn man statt 4 Atomen 2 oder 3 oder 5 oder so kombiniert.

  • Also auch ich habe 10 solche "Freistellen" verwendet:


    0001 0002 0003 0004

    1112 1113 1114 1115

    2223 2224 2225 2226

    3334 3335 3336 3337

    4445 4446 4447 4448

    .....


    Es werden nur 12 Nullen, 13 Einser, 14 Zweier und 15 Dreier verwendet. Alle anderen Gewichte kommen je 16 mal vor.

    Also bleiben 4 Nullen, 3 Einser, 2 Zweier und ein Dreier übrig, insgesamt 10 Atome.