Beiträge von hg1

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

    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.

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

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

    Eine geschlossene Formel für das n(x) wäre wohl (ähnlich zu der von Georg J. aus D., vielleicht minimal einfacher)


    n(x) = 100/x * [x über (x-100)/2]


    Die [x über (x-100)/2] sind ähnlich wie in pierrots Herleitung einfach die Anzahl der Wege, die nach x Sekunden die 0 erreichen, aber nicht notwendigerweise zum ersten Mal (aus x Sprüngen wird (x-100)/2 mal nach rechts und (x+100)/2 mal nach links gesprungen).


    Dieser Ausdruck ist zu hoch, da wir ja nur die Wege betrachten wollen, bei denen nach x Sekunden zum ersten Mal die 0 erreicht wird.

    Es fehlt also noch ein Korrekturfaktor: Nämlich die bedingte Wahrscheinlichkeit -- unter der Bedingung, dass nach x Sekunden die 0 erreicht wird -- dass die 0 dann zum ersten Mal (und nicht vorher schon) erreicht wird.


    Und diese bedingte Wahrscheinlichkeit ist genau 100/x.

    Mit pierrots erstem Ansatz überschätzt man also die wahre Anzahl um den Faktor x/100.

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

    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.

    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)

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

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

    Warum glaubst Du, dass es bei den Urkunden anders gehandhabt wird, als bei den Plätzen beste Aufgabe bzw bestes Bild?
    Ich kann das nicht beurteilen. Ich sehe nur ob und wie viele Personen eine Platzierung mit mir teilen.
    Eine Möglichkeit wäre natürlich Georg, dass du mit 118 Punkten Platz 3 oder schlechter belegst. Dann wäre es klar ;)

    ... oder mit 116 Punkten Platz 4 oder schlechter, mit 115 Punkten Platz 5 oder schlechter, etc. ....

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

    Eine Möglichkeit um die umzulegenden Schalter explizit zu beschreiben: Beim i-ten Gang schaltet man genau die Schalter an, deren Nummer in der Binärdarstellung an Stelle i eine 1 hat.

    Nach 11 Kellergängen hat man dann für jede Lampe eine Folge von an/aus Zuständen: die bildet gerade die 11-stellige Binärdarstellung der Nummer des zugehörigen Schalters.