Wichteln/Fixpunktfrei/Verfahren/Papier/Aufgabe

Aus Wikiversity

In einem Raum befinden sich Personen, die wichteln wollen. D.h. für jede Person muss eine weitere Person bestimmt werden, für die ein Geschenk besorgen soll. Jede Person darf nur wissen (und weiß), wen sie beschenken soll, und keine Person darf mehr wissen. Die Personen bleiben die ganze Zeit im Raum, sie schauen nicht weg oder Ähnliches. Es stehen allein Papier und Stifte zur Verfügung. Mischen ist erlaubt, d.h. man darf „zufällige“ Permutationen von optisch gleichen Objekten vornehmen, und diese sind nicht rekonstruierbar. Es darf gelost werden und dabei darf eine gezogene Information verdeckt gelesen werden. Zettel dürfen (auch heimlich) beschrieben werden.

Entwerfe ein einmalig durchzuführendes Verteilungsverfahren, das all diese Bedingungen erfüllt.