16. Türchen

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

    • Das war eine sehr schöne Aufgabe! Und hat genau eine Lösung! ^^

      Folgende Bedingungen sollten erfüllt sein:
      1. Die Information über eine Stelle des Codes erhält jeweils nur ein Teil der Wichtel, und zwar für jede Stelle die gleiche Anzahl an Wichteln. Diese bilden jeweils eine Gruppe. Es soll aber keine zwei Stellen des Codes geben, die genau der gleichen Gruppe von Wichteln bekannt sind.
      2. Es gibt eine natürliche Zahl n mit folgender Eigenschaft: Immer wenn sich n beliebige der w Wichtel treffen, sind sie mit den ihnen bekannten Stellen des Codes nicht in der Lage, den Tresor zu öffnen. Treffen sich hingegen (n + 1) beliebige der w Wichtel, dann können sie mit ihrem gemeinsamen Wissen den kompletten Code eingeben und damit den Tresor öffnen.
      3. n soll mindestens 2 und höchstens w - 3 betragen.
      4. Jeder Wichtel soll höchstens 35 Stellen des Codes kennen.
      5. Kein Wichtel soll mehr als ein Drittel aller Stellen des Codes kennen.
      Ich stelle die Wichtel als Zeilen in einer Tabelle dar - und die Spalten sind die Codestellen.
      Da die Bedingung 2 sehr hart ist und erschwerend Bedingung 5 erfüllt sein muss, wähle ich (zunächst für den Versuch) n = w-3.
      Sprich:
      Wenn ich von allen Wichteln drei wegnehme (egal welche) dann können die verbleibenden Wichtel den Code NICHT knacken.
      Wenn ich aber von allen Wichteln nur zwei wegnehme (auch egal welche) dann KÖNNEN die verbleibenden Wichtel den Code knacken, in jedem Fall.

      In der Tabelle steht eine 1, wenn Wichtel wi Codestelle cj kennt, eine 0 sonst.
      Jede Codestellenspalte hat genau drei Einsen, jede Einserkombination in einer Spalte soll genau einmal in der Tabelle vorkommen.
      Dafür benötige ich (w über 3) Codestellen, da es genau soviele Anordnungen von drei Einsen in w Positionen gibt.

      Damit ist Bedingung 1 erfüllt. Alle Spalten sind verschieden.

      Bedingung 2 ist auch erfüllt,
      - egal welche 3 Wichtel ich wegnehme, es enteht eine Spalte mit nur Nullen, der Code wird nicht geknackt.
      - wenn ich nur zwei Wichtel entferne, so bleibt per Konstruktion mindestens eine Eins in jeder Spalte stehe, der Code wird geknackt.

      Bedingung 3: OK.

      Zwischenüberlegung:
      Wie viele Stellen des obigen Codes kennt jeder der w Wichtel?
      Das sind genau so viele Stellen, wie man 2 Einsen in w-1 Positionen anordnen kann: D.h. es sind hier (w-1 über 2).

      Dazu eine Skizze (5 Wichtel => Codelänge 10):

      1111110000
      1110001110
      1001101101
      0101011011
      0010110111


      Betrachte z.B. die erste Zeile, Wichtel 1 kennt 6 Codestellen (wie natürlich die anderen Wichtel auch).
      Diese 6 Codestellen entsprechen genau den Anordnungsmöglichkeiten von 2 Einsen in 4 Positionen (4 über 2) - das sind die 4 Zeilen unter den Einsen in der ersten Zeile.
      Hier sind das also (4 über 2) = 6 Stellen, aber das haben wir ja schon gewusst. 8o
      Also stimmt: Jeder Wichtel kennt genau (w-1 über 2) Codestellen.

      Jetzt kommt das Pascalsche Dreieck ins Spiel (für die Bedingungen 4 und 5):


      1
      11
      121
      1331
      14641
      15101051
      1615201561
      172135352171
      18285670562881
      193684126126843691


      Man erkennt: die 36 als (9 über 2) ist zu groß, so viele Codestellen darf nach Bedingung 4 kein Wichtel kennen => Es müssen weniger als 10 Wichtel sein.
      Also darf die Anzahl der Codestellen höchstens (8 über 2) = 28 sein - und was für ein Glück ( 8o ) hier gilt sogar:

      (8 über 2) * 3 = (9 über 3), 28*3 = 84, also auch Bedingung 5 ist erfüllt. Denn (9 über 3) ist die Länge des Codes und jeder Wichtel kennt genau ein Drittel dieser Stellen (8 über 2).

      Mit weniger Wichteln geht es nicht, wie man leicht anhand der orange markierten Felder (8 über 3) und (7 über 2) sieht, Bedingung 5 ist nicht erfüllt (21 > 56/3).
      Und auch alle Versuche mit n = w-4 oder kleiner werden scheitern, wie man unschwer aus dem Pascalschen Dreieck abliest.

      Es gibt also genau eine Lösung: 9 Wichtel.

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von mr.x ()

    • Skeeve schrieb:

      Ab da setzt es aus.

      Wie sieht denn so eine Verteilung des Codes aus?
      Ich weiß nicht genau, was Dir unklar bleibt.
      Aus Sicht der Codestellen (Spalten) gibt es immer genau 3 Wichtel, welche diese Stelle kennen (das gilt für jede Codestelle).
      Alle Spalten sind verschieden per Konstruktion - es gibt (w über 3) Codestellen (Spalten). Die Bedingungen kann man dann step-by-step abhaken.
      Ist die Anzahl der Stellen, welche jeder Wichtel kennt, unklar? Das ist eine entscheidende Stelle für die Eindeutigkeit der Lösung...
      Wenn Du Dir das obere Bild (Verteilung von Wichtel zu Codestelle) anschaust, dann siehst Du die 10 verschiedenen Spalten (5 über 3) und Bedingung 2 kann hier leicht gecheckt werden. Die Konstruktion ist genauso für größere Wichtelanzahlen (3 Einsen je Spalte). Und für w = 9 sind dann endlich auch die Bedingungen 4 und 5 erfüllt. :)