Aufgaben-Feedback 17. Türchen

    • Das war mit Sicherheit die schwierigste Aufgabe und meiner Meinung nach gibt es auch keine einfache Strategie.
      Meine Lösung sieht folgendermaßen aus (dabei ist S = Summe der Zahlen der letzten 10 Wichtel):

      Zahl auf Mütze von Bilbo: 0 1 2 3 4
      ------------------------------------------------------------------
      S mod 5 = 0 NJ1 NJ1 NJ1 NJ1 NJ1
      S mod 5 = 1 JN JN JN JN JN oder NJ4
      S mod 5 = 2 JJ0 JJ0 NN JJ0 NN
      S mod 5 = 3 NN NN JJ2 NN JJ2
      S mod 5 = 4 JJ4 NJ3 JJ4 NJ3 JJ4

      Die Tabelle gibt an, wie Atto und Bilbo antworten müssen in Abhängigkeit von der Summe der letzten 10 mod 5 und der Zahl von Bilbo.
      Dabei kennt Atto beide Informationen, während Bilbo nur die Summe kennt (also die Zeile). Daher ist die Antwort von Bilbo in jeder Zeile nur abhängig von der Antwort von Atto.
      Wenn also die Summe mod 5 = 2 ist, antwortet Atto in Abhängigkeit von Bilbos Zahl mit J(a) oder N(ein) und Bilbo sagt, falls Atto J(a) sagt auch J(a) und "ratet" die Zahl 0. Falls Atto N(ein) sagt, sagt Bilbo auch N(ein).
      Die anderen Wichtel kennen Bilbos Zahl, also die Spalte, und können nun die Zeile eindeutig bestimmen.
      Dabei ist in jeder Zeile eine Kombimation aus J(a) und N(ein) doppelt, aber das macht nichts, denn an der Reaktion des Weihnachtsmanns (Bilbo darf ins Kaffeezimmer (hier unterstrichen) oder muss heim) kann man die Zeile eindeutig erkennen.
      Wenn die Wichtel die Zeile kennen und somit die Summe modulo 5, können sie ihre Zahl leicht berechnen.

      Frohes neues Jahr!
    • Lebossle schrieb:

      I thought the statement was very clear that you only got one bit from each question, I'm not finding anywhere that states that elf's successes are another source of common knowledge.
      Well it says he is sent home immediately, so when he is not going through the door to the hall, they can see it. But now that you say that, it is never clearly stated that these are two different doors. It just might be that in both cases the elves just leave and in this case, obviously 9 is the optimal answer.
    • Hm, ich hatte richtig geraten, und zwischen Weihnachten und Neujahr noch eine Möglichkeit gefunden. Ich nenne a die Zahl der Mütze von Atto, b die Zahl der Mütze von Bilbo, x die Summe der restlichen Zahlen mod 5. Klar ist, wenn die letzten 10 Wichtel x kennen, kennen sie auch ihre eigene Zahl.

      Zunächst ist schnell klar, dass der simple Versuch mit Ja/Nein bei A und B nicht ausreicht. Deshalb sollte A noch mehr Informationen übermitteln: Er sollte auch dann Nein sagen, wenn b=x ist. Ich zeige erstmal nur die Fälle der Nein-Antworten von A (und als zweites immer das, was B sagt):


      b=0b=1b=2b=3b=4
      x=0NNNNNNNNNN
      x=1NJ1NJ1NJ1NJ1NJ1
      x=2NJ1
      x=3NJ1
      x=4NJ1


      Immerhin etwas mehr Info. Trotzdem reicht es nicht aus. Dummerweise bin ich nicht auf die Idee gekommen, hier weiter zu optimieren, sondern überlegte, wie A noch mehr Informationen übermitteln kann. Und das geht tatsächlich: A sagt bei "Ja" nämlich immer (x+b) mod 5. Im Fall, dass das richtig ist, dürfen alle 12 Wichtel zum Kaffeetrinken, weil sie nun (x+b) mod 5 kennen (und außerdem b oder x). Im Fall, dass das nicht richtig ist, kann man etwas ausschließen, nämlich (x + b) mod 5 = a. Leider muss man dann für alle 5 Werte von a überlegen, wie die weiteren Antworten aussehen, z.B. könnte es bei a = 0 so sein(nur die Fälle, bei denen A "Ja" sagt und falsch liegt; "---" bedeutet: ist ausgeschlossen, weil die Antwort von A nicht richtig war):

      b=0b=1b=2b=3b=4
      x=0
      x=1
      x=2JJ0JJ0---JJ0
      x=3JNJN---JN
      x=4JJ3---JJ3JJ3

      Etwas mühsam, für jedes a das zu machen, aber nicht schwierig, wenn man mal so weit ist. Auf jeden Fall aber weniger elegant als bei jewill...


      Die eigentliche Frage, die sich mir stellt, ist aber: "Wie kommt man denn auf so was???". 8|
    • Bei mir war es wie bei Nachvogel: erst mal die vermutete Lösung abgegeben nach dem Motto
      "es wird schon irgendwie gehen" und dann zwischen Weihnachten und Neujahr eine Möglichkeit
      für die Lösung gefunden.

      Meine Lösung ist im Vergleich zu der von jewill eigentlich viel zu kompliziert, um sie hier zu erwähnen,
      aber sie löst eine verschärfte Form der Aufgabe, und das könnte vielleicht doch interessant sein.

      Nehmen wir mal an, der Weihnachtsmann verschärft die Bedingungen, indem er fordert,
      dass alle Wichtel paarweise antworten müssen, so dass Bilbo die Antwort von Atto nicht
      verwenden kann. Können dann immer noch 10 Wichtel garantiert Kaffee und Kuchen
      bekommen?

    • Eine einfache und bestimmt unzulässige Variante auf 10 Kaffee-Wichtel zu kommen, könnte wie folgt ablaufen:

      Nachdem der Weihnachtsmann den Wichteln die Mützen aufgesetzt hat, wird er Atto etwas Zeit gönnen, bevor er ihm die Frage stellt. Falls Atto feststellt, dass die Summe der Zahlen auf den Mützen der letzten 10 Wichtel mod 5 = 4 ist, verlässt er gespielt wütend ungefragt den Raum und geht nach Hause. Alle anderen 4 möglichen Reste, können Atto und Bilbo binär durch entsprechende Ja/Nein Antworten an die 10 letzten Wichtel übermitteln. Natürlich müsste diese "Strategie" vorab festgelegt worden sein, was sehr unwahrscheinlich ist, da die vorhergehende Diskussion zu lange gedauert hatte. ;)
    • War mit meiner Antwort sicher, dass N=9; weil der Wertebereich 0,1,2,3,4,5 minimal mit 3 Bit, statt 2 Bit verschlüsselt werden kann (dazu müssen sich die ersten 3 Wichtel opfern um dem Rest der 9 Wichtel die Summe S Modulo 5 mitteilten zu können.) Dabei habe ich berücksichtigt, dass auf die Frage

      „Dürfen wir so laut flüstern, dass auch die anderen Wichtel die Zahl hören?“ fragt Harpo.

      der Weihnachtsmann geantwortet hat mit

      – „Nein, natürlich nicht!“, antwortet der Weihnachtsmann. „Keine Schummeleien!“

      Von daher war ich auf die Lösung gespannt und bin nun etwas enttäuscht, dass die Vermittlung der Zahl von Bilbo für die Lösungsfindung eine Rolle spielt
    • AugustaSibylla schrieb:

      Von daher war ich auf die Lösung gespannt und bin nun etwas enttäuscht, dass die Vermittlung der Zahl von Bilbo für die Lösungsfindung eine Rolle spielt
      Der Trick ist, dass Bilbo eine mit den anderen Wichteln vorab vereinbarte Zahl sagt - sie kennen sie also bereits vorher gemäß Tabelle und es ist nicht nötig sie zu hören.

      In der Tabelle von jewill im Beitrag 61 oben sagt Bilbo für S mos 5 = 0 immer die "1", für S mos 5 = 2 immer "0", für S mos 5 = 3 immer "2" und nur bei S mos 5 = 4 ist es etwas komplizierter: Bilbo sagt "3" wenn Atto "N" sagt und ansonsten "4").

      Zahl auf Mütze von Bilbo01234
      S mod 5 = 0NJ1NJ1NJ1NJ1NJ1
      S mod 5 = 1JNJNJNJNJN
      S mod 5 = 2JJ0JJ0NNJJ0NN
      S mod 5 = 3NNNNJJ2NNJJ2
      S mod 5 = 4JJ4NJ3JJ4NJ3JJ4


      Je nachdem ob der Weihnachtsmann Bilbo akzeptiert (fett unterstrichen) oder nicht (kursiv) können die anderen Wichtel also zwischen den beiden Zeilen mit gleichen J/N Kombination unterscheiden.
      Bei