Weihnachtsmann rot

Aufgabe vom 16. Dezember

Ein sicherer Tresor

Autor: Thorsten Eidner

Aufgabe:

Diebstahl im Weihnachtsland! Schlimmer hätte es kaum kommen können: Die Wunschzettel der Kinder in der Hand des Grinchs! Dabei waren alle Dokumente vermeintlich sicher im Tresor, der sich nur durch die richtige Eingabe eines vierstelligen Codes öffnen ließ, verstaut.
Damit die Wichtel jedem Kind das richtige Geschenk einpacken, müssen sie natürlich auf die Zettel im Tresor zugreifen können. Doch auf einen Wichtel allein wollte sich der Weihnachtsmann nicht verlassen. Daher wählte er vier Wichtel aus, gab aber keinem von ihnen den kompletten Code: Atto kannte nur die 1., 2. und 3., Bilbo die 1., 2. und 4., Chico die 1., 3. und 4. sowie Dondo nur die 2., 3. und 4. Stelle des Codes. So war gesichert, dass keiner allein den Tresor öffnen konnte, zwei beliebige der vier Wichtel waren aber dazu gemeinsam in der Lage. Leider hatte der Weihnachtsmann die Bestechlichkeit von Atto, der Schokolade über alles liebte, und Bilbo, der mit Lebkuchen zu ködern war, unterschätzt. So kam der Grinch an den Code und damit an die Wunschzettel. Zwar muss Weihnachten dieses Jahr deswegen nicht ausfallen, aber ohne die Wunschzettel können die Geschenke nur zufällig verteilt werden - na, das wird ja eine schöne Bescherung!

Zukünftig darf sich so etwas auf keinen Fall wiederholen. Ein neuer, besser gesicherter Tresor muss her! Bloß gut, dass gerade ein topmodernes Fabrikat entwickelt wurde, bei dem der für die Öffnung notwendige und durch den Weihnachtsmann anfangs festzulegende Code eine beliebig große Stellenzahl haben kann. Auch weiterhin soll einer Gruppe von w Wichteln, die besonders verlässlich sind (Atto und Bilbo sind ganz bestimmt nicht mehr dabei), der Zugriff auf den Tresor möglich sein, indem jeder nach einem ausgeklügelten Plan einen Teil der Informationen über die Stellen des Codes erhält (und dann natürlich streng geheim für sich behalten muss).

Dabei sollen folgende Bedingungen 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 mindestents 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.

Damit, so denkt der Weihnachtsmann, müsste das Ganze einerseits noch halbwegs praktikabel sein und andererseits den Grinch daran hindern, sich den Code zu beschaffen. Doch ist eine solche Aufteilung überhaupt möglich? Und wenn ja, für welche Anzahl w an Wichteln ist es möglich, bei geeigneter Stellenzahl des Codes eine solche Verteilung der Information über die einzelnen Stellen des Codes an die Wichtel vorzunehmen, so dass alle genannten Bedingungen erfüllt sind?

Die Aufgabe als PDF runterladen (flagge nl NL Download)

Antwortmöglichkeiten:
(Lösung als PDF herunterladen)

  1. Nur für w = 5.

  2. Nur für w = 6.

  3. Nur für w = 7.

  4. Nur für w = 8.

  5. Nur für w = 9.

  6. Nur für w = 10.

  7. Nur für w = 11.

  8. Es gibt genau eine solche Anzahl w mit w 12.

  9. Es gibt keine Anzahl w, mit der die Bedingungen zu erfüllen sind.

  10. Es gibt mindestens zwei Werte für w, für die eine solche Verteilung möglich ist.

Sie müssen sich einloggen um die Aufgaben abgeben zu können.