Ihr hab mich mit eurem Spaltentauschen ganz schön verwirrt bis ich gemerkt hab dass ihr euch auf sortierte Reihen bezieht...
Zu meinem Ansatz:
Ich hab auch relativ schnell gemerkt dass man sortieren kann und das nicht hilft. Also war meine Vermutung "unmöglich".
Ich wollte das aber nicht glauben und hab das noch gebruteforced....das hat ein paar Stunden Rechenpower gekostet und hatte das gleiche Ergebnis...
[...]
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.
Hm - ist etwas schwer zu fassen, aber ich denke, dein Beweis ist nicht hieb- und stichfest.
Wenn ich es richtig verstanden habe, versuchst Du den Beweisschritt der vollständiger Induktion mit einen Widerspruchsbeweis zu führen.
Also Aussage S über einen mathematischen Sachverhalt ändert sich unter einer diskreten Variablen n so, dass Sn -> Sn+1 eine bekannte Abbildung ist. Für n=0 ist die Aussage bewiesen. Unter der Annahme, dass sie für ein beliebiges n bewiesen sei, versuchst Du zu zeigen, dass sie auch für n+1 stimmen muss, indem Du einen Widerspruch konstruierst, also: "Wenn sie für n+1 nicht stimmen würde, kann sie bereits für n nicht gestimmt haben".
Die Aussage Sn, die Du beweisen willst (Du solltest S vielleicht nicht "Annahme" nennen - dies verwirrt mit der späteren Annahme des Widerspruchbeweises - "Vermutung" wäre besser), ist:
Annahme: Ruprecht kann nach n Würfen keine 2 identischen Teile identifizieren.
Das Problem ist jetzt, dass dieses Aussage / Vermutung für das gesamte Ensemble aller 64 Konstellationen der X-Masium Zustände ( |0>, |1> ) der 6 Atome gelten muss.
Heißt: auch dein Beweis muss für das gesamte Ensemble gelten. Du kannst nicht für einzelne Schritte deines Beweises nur spezielle Konstellationen herauspicken.
In der Induktions-Vorraussetzung (n=0) ist der Beweis diesbezüglich noch sauber.
Deine Widerspruchsannahme ist ebenfalls noch korrekt: Du nimmst an die Aussage S wäre für n+1 falsch und versuchst nun damit zu beweisen, dass sie dann schon für n falsch gewesen seien muss. Da dies nicht stimmt (Induktion-Vorraussetzung), wäre die Widerspruchsannahme falsch und Aussage S gilt auch für n+1.
Für n -> n+1 gibt es viele verschiedene Wege. OBdA versuchst Du einen allgemeinen herauszunehmen und landest bei zwei Unterfällen:
Alles anzeigenAlso 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.
Da Du einen Widerspruchsbeweis führst, musst Du nun die Annahme (Sn+1 sei falsch) für beide Unterfälle zu einem Widerspruch mit der grundlegenden Induktions-Vorraussetzung (Sn ist richtig) führen.
Hier gibt es jetzt einige Probleme deines Beweises:
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.
Es geht doch gerade darum, zu zeigen, dass Ruprecht die Konstellation |0>|0>|0>|0>|0>|0> nicht von anderen Konstellationen unterscheiden kann. Und, dass es nicht gelingen kann, alle möglichen Konstellationen des Ensembles in einen Zustand zu bringen, der (trotz Ununterscheidbarkeit der Atome) eine eindeutige Aussage zum Zustand (|0>, |1>) zweier Atome erlaubt.
Was Dein Beweis beweist, ist nur, dass es für den Zustand |0>|0>|0>|0>|0>|0> nicht möglich ist nach n+1 Würfen zwei Atome zu unterscheiden.
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.
Beim letzten Wurf ändert sich der Zustand aber nur für diejenigen Ausgangsverteilungen, für die man auch die maximale Zahl an Würfen benötigt. Wenn es einen Algorithmus gäbe, dann gäbe es eine Reihe von Würfen und die Atome A und B, die danach gleich wären bei jeder beliebigen Ausgangsverteilung. Dann hast du auch im Fall (0 0 0 0 0 0) die Atome A und B, die am Ende des Algorithmus gleich sind.
Dieses Verhalten steht nicht im Widerspruch zur Annahme, dass es einen endlichen Algorithmus gibt.
Beweisschritt der vollständiger Induktion
Ich hab schon damals in der Schule festgestellt, dass manchmal der Beweis durch vollständige Intuition viel besser und vor allem schneller ist 
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?
Ich hatte vor kurzem einen Beweis auf YouTube gesehen, der zeigt, dass X4 + Y4 = Z4 keine ganzzahligen Lösungen besitzt.
Ohne das Video anzugucken bin ich mir sicher, dass dieser Beweis nicht richtig sein kann: X=42, Y=0, Z=42 ist eine ganzzahlige Lösung von X4 + Y4 = Z4.
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.
Wenn X, Y, Z positive ganze Zahlen sein sollen ist das durchaus eine legitime Beweismethode.
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.
Ich versuche nochmal genau zu erläutern was aus meiner Sicht das Problem hier ist.
n+1 Würfe sind die kürzeste Strategie, sodass ausgehend von jeder Anfangskombination An+1=Bn+1 gilt.
Es gilt also NICHT für jede Anfangskombination An=Bn.
Das bedeutet: Bei manchen Anfangskombinationen gilt An=Bn (etwa bei 000000) und bei manchen nicht.
Also muss bei manchen Anfangskombinationen im (n+1)-ten Wurf ein Wechsel B<->C stattfinden und bei manchen nicht.
Daher ist es kein Widerspruch, dass ausgehend von der Anfangskombination 000000 beim (n+1)-Wurf kein Wechsel B<->C stattfindet.
Ich bin jedenfalls gespannt wie der Beweis im Lösungsheft aussieht...
Die Aufgabe hatte ich selbst auch mit Computerhilfe gelöst, durch Bestimmen aller erreichbaren Zustandsmengen. (Da das "nur" 577802 Mengen waren, waren die in ein paar Sekunden durchprobert...)
Alles anzeigenWenn X, Y, Z positive ganze Zahlen sein sollen ist das durchaus eine legitime Beweismethode.
Ich versuche nochmal genau zu erläutern was aus meiner Sicht das Problem hier ist.
n+1 Würfe sind die kürzeste Strategie, sodass ausgehend von jeder Anfangskombination An+1=Bn+1 gilt.
Es gilt also NICHT für jede Anfangskombination An=Bn.
Das bedeutet: Bei manchen Anfangskombinationen gilt An=Bn (etwa bei 000000) und bei manchen nicht.
Also muss bei manchen Anfangskombinationen im (n+1)-ten Wurf ein Wechsel B<->C stattfinden und bei manchen nicht.
Daher ist es kein Widerspruch, dass ausgehend von der Anfangskombination 000000 beim (n+1)-Wurf kein Wechsel B<->C stattfindet.
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.