17. Türchen

    Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

    • 17. Türchen

      Hmm, geschafft habe ich es leider nicht, aber ich war dicht dran und hatte auf 9 getippt und das kam so:

      1. Jeder Wichtel kann den nach ihm kommenden Wichteln genau 1 Bit an Information geben: ja/nein, 0/1, höher/niedriger, +/-, gerade/ungerade, usw.
      2. Die Information muss für jeden Wichtel individuell nutzbar sein, also etwas für ihn höchst persönliches aussagen.
      3. Dazu muss jeder Wichtel diese Information mit dem verrechnen, was er selber sieht.
      4. Jeder Wichtel sieht die Summe aller (oder einer Teilmenge der) Mützen minus der eigenen, diese Summe ist um 0 bis 4 kleiner als der Wert wenn er seine eigene Mütze mitzählen könnte.
      5. Die ersten Wichtel können eine Aussage über die Gesamtsumme der Mützen der restlichen Wichtel treffen.
      6. Wenn man mit Informationsbits arbeitet, dann ist ein Darstellung im 2er-System hilfreich.
      5. Eine Zahl im Bereich 0-4 kann man mit 3 Bit darstellen - es brauchen sich also höchstens 3 Wichtel opfern, nur wie?

      Zum Beispiel so:
      Die ersten 3 Wichtel sagen jeweils ob das 1., 2. bzw. 3. Bit der Gesamtsumme der Mützen der restlichen Wichtel gerade oder ungerade ist. Jeder der restlichen Wichtel kann damit die Differenz zu seiner für ihn sichtbaren Summe feststellen, was also seiner eigenen Mütze entspricht. Damit können 9 Wichtel auf jeden Fall korrekt antworten.

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von frank.buchholz ()

    • Da wüsste ich die Lösung für 10 auch gerne.
      9 gehen jedenfalls so: Der 1. Wichtel betrachtet die Summe aller anderen und bei 0mod2 sagt er ja, bei 1mod2 sagt er nein.
      Genau so gibt der 2. Wichtel bekannt, was er mod4 sieht.
      Da aber 0 und 4 noch äquivalent sind, muss so der 3. Wichtel nochmal mod8 ansagen, die restlichen 9 werden gerettet.

      Mir war fast klar, dass das nicht optimal ist, denn die Wichtel bekommen im Falle eines "JA"s mit, ob die angesagte Zahl auch wirlich stimmt, was bei meinem Vorgehen überflüssig wäre. Ich habe einige Nächte darüber nachgedacht, wie man damit etwas verschlüsseln kann, kam aber immer wieder auf das Problem zurück, dass man als zweiter Wichtel zwar "JA" sagen und erzwingen kann, dass die geratene Zahl falsch ist (denn mod2 weiß man sie schon), aber zu erzwingen, dass sie richtig ist, geht offensichtlich nicht (sonst könnte man ja sogar 11 Wichtel retten).
      \binom{2^{\binom{2^2}{2}}}{2} = 2016
    • Hier ist eine mögliche Lösung (die sicher nicht die einzige ist):
      Die Wichtel 1 und 2 betrachten die Summe der übrigen Wichtel und ermitteln,
      welchen Rest sie bei Division durch 5 lässt. Diesen Rest gilt es, mit den
      Antworten der Wichtel 1 und 2 an die übrigen Wichtel zu übermitteln.
      Nennen wir den Rest n.

      Da bei einem Ja etwas mehr Informationen verpackt werden können (der Wichtel nennt ja dem Weihnachtsmann
      noch eine Zahl), sollte ein Nein etwas einschränkender sein als ein Ja. Außerdem hängt von der
      Mützenzahl ab, ob bei einem Ja der Wichtel raus muss oder bleibt. Also sollte die Unterscheidung
      zwischen Ja und Nein von der Mützenzahl des jeweils anderen Wichtels abhängen.

      Die Grundidee ist nun, die Menge {0,1,2,3,4} abhängig von der Mützenzahl von Wichtel 1 bzw. 2
      in verschiedene Dreier- und Zweiermengen zu zerlegen. Die Dreier- und Zweiermengen sollen verschieden
      sein, so dass ihre Schnittmengen möglichst klein sind. Nenne D1, D2, Z1, Z2 die Dreier- und Zweiermengen
      in Abhängigkeit von der Mützenzahl von Wichtel 1 und 2. Dann wäre eine mögliche Zerlegung
      D1(n1) = {n1,n1+1,n1+4}, Z1(n1) = {n1+2, n1+3} für die Mützenzahl n1 von Wichtel 1
      D2(n2) = {n2,n2+2,n2+3}, Z2(n2) = {n2+1, n2+4} für die Mützenzahl n2 von Wichtel 2
      Alle Summen sind hier als Rest bei Division durch 5 (modulo 5) zu verstehen, also z.B. 3+4=2.

      Wichtel 1 und 2 wählen nun ihre Antworten danach, ob der Rest n in der mützenzahlabhängigen
      Dreier- oder Zweiermenge des jeweils anderen Wichtels vorkommt, n1 und n2 sei die Mützenzahl
      von Wichtel 1 bzw. 2:
      Wichtel 1 sagt Nein, wenn n in Z2(n2), er sagt Ja, wenn n in D2(n2).
      Wichtel 2 sagt Nein, wenn n in Z1(n1), er sagt Ja, wenn n in D1(n1).
      (So ist Nein einschränkender als Ja.)

      Die übrigen Wichtel kennen n1, n2 und die Zerlegungen und können, falls die Schnittmengen einelementig
      sind, daraus bereits n bestimmen. Das sind die folgenden Fälle ("." steht hier für den Durchschnitt)
      Z1(m).Z2(m+1) = Z1(m).Z2(m+3) = {m+2}
      Z1(m).Z2(m+2) = Z1(m).Z2(m+4) = {m+3}
      Z1(m).D2(m+1) = Z1(m).D2(m+3) = {m+3}
      Z1(m).D2(m+2) = Z1(m).D2(m+4) = {m+2}
      D1(m).Z2(m+1) = D1(m).Z2(m+4) = {m}
      D1(m).Z2(m+2) = {m+1}
      D1(m).Z2(m+3) = {m+4}
      D1(m).D2(m) = {m}
      (Z1(m) und Z2(m) haben leeren Durchschnitt {})

      Falls die Schnittmengen zweielementig sind, muss die Zahl, die der Wichtel dem Weihnachtsmann nennt,
      die Unterscheidung bringen, so dass in beiden möglichen Fällen die Wichtel unterschiedlich rausfliegen
      oder bleiben.
      Die Fälle mit zweielementigen Schnittmengen sind:
      D1(m).Z2(m) = {m+1,m+4}
      Z1(m).D2(m) = {m+2,m+3}
      D1(m).D2(m+1) = D1(m).D2(m+4) = {m+1,m+4}
      D1(m).D2(m+2) = {m,m+4}
      D1(m).D2(m+3) = {m,m+1}
      Antwortet nun Wichtel 1 bei Ja (wenn n in D2(n2)) mit der Zahl
      • n2 für n = n2+2
      • n2+1 für n = n2
      • n2+2 für n = n2+3
      und Wichtel 2 bei Ja (wenn n in D1(n1)) mit:
      • n1 für n = n1+1
      • n1+1 für n = n1+4
      • n1+2 für n = n1
      so unterscheiden sich die Resultate (raus oder bleiben) für alle Fälle mit zweielementigen Schnittmengen.Konkret:
      Falln1n2nAntw. W1Antw. W2Wichtel 1Wichtel 2
      D1(m).Z2(m)mmm+1NeinJa/mrausbleibt
      D1(m).Z2(m)mmm+4NeinJa/m+1rausraus
      Z1(m).D2(m)mmm+2Ja/mNeinbleibtraus
      Z1(m).D2(m)mmm+3Ja/m+2Neinrausraus
      D1(m).D2(m+1)mm+1m+1Ja/m+2Ja/mrausraus
      D1(m).D2(m+1)mm+1m+4Ja/m+3Ja/m+1rausbleibt
      D1(m).D2(m+2)mm+2mJa/m+4Ja/m+2rausbleibt
      D1(m).D2(m+2)mm+2m+4Ja/m+2Ja/m+1rausraus
      D1(m).D2(m+3)mm+3mJa/m+3Ja/m+2rausraus
      D1(m).D2(m+3)mm+3m+1Ja/mJa/mbleibtraus
      D1(m).D2(m+4)mm+4m+1Ja/m+4Ja/mrausraus
      D1(m).D2(m+4)mm+4m+4Ja/mJa/m+1bleibtraus


      So können die 10 übrigen Wichtel aus n1, n2, den Antworten von Wichtel 1 und 2 (Ja oder Nein)
      und dem Ergebnis (raus oder bleiben) den Rest n eindeutig bestimmen und ihre eigene Mützenzahl
      aus denen der anderen 9 Wichtel bestimmen.
    • Ich bin schwer beeindruckt, dass du das so hinbekommen hast ... aber wenn man das so komplex lösen muss wäre ich auch schwer von der Aufgabe enttäuscht.

      Mal sehen ob wir gemeinsam etwas eleganteres finden. Deine Hauptidee ist, dass man nicht nur "ja/nein" verwendet, sondern auch "ja" in die Fälle "bleibt/raus" unterteilt, so dass folgende Ergebniskombinationen genutzt werden (wobei du "nein/nein" gar nicht verwendest):


      Wichtel 1Wichtel 2
      nein nein
      ja bleibtnein
      ja rausnein
      neinja bleibt
      neinja raus
      ja bleibtja bleibt
      ja rausja bleibt
      ja bleibtja raus
      ja rausja raus
    • Nein/nein verwende ich weiter oben, wo die Schnittmengen nur ein Element haben:
      Z1(m).Z2(m+1) = Z1(m).Z2(m+3) = {m+2}
      Z1(m).Z2(m+2) = Z1(m).Z2(m+4) = {m+3}
      Die Tabelle listet nur die Fälle, wo Nein/Nein, Nein/Ja, Ja/Nein, Ja/Ja allein nicht ausreicht.
      Aber eine wesentlich einfachere Lösung gibt es ja auch schon, siehe Link in Post 5. :)

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von rs3095 () aus folgendem Grund: Link mit URL hinterlegt

    • Schwerste Mathekalender-Aufgabe aller Zeiten!


      Hier mal noch ein Nachtrag, da inzwischen die Statistik erschienen ist.
      Nimmt man den Anteil richtiger Antworten als Maß für die Schwierigkeit einer Aufgabe, so hat sich die diesjährige Mützenaufgabe mit nur 11,5 % richtigen Antworten auf Platz eins gesetzt (von 264 Aufgaben, die es seit 2006 - erst seitdem gibt es im Archiv eine Statistik - gab).
      Bisher lag die legendäre Elfenstadt-Aufgabe vom 18.12.2006 mit nur 12,2 % richtigen Antworten auf Platz 1.
      Diese hat also jetzt mit der wirklich genialen Mützenaufgabe einen würdigen Nachfolger gefunden!