Du feierst Geburtstag und möchtest für deine Gäste Party-Pizzen bestellen. Die Pizzeria deines Vertrauens bietet die Sorten A, B, C, …, Z an. Natürlich soll jeder Gast mindestens eine Pizza bekommen, die ihm oder ihr schmeckt – aber du kannst (und willst) nicht für jeden eine eigene Pizza bestellen.
Deshalb sammelst du für jeden Gast eine Liste mit den Sorten, die er oder sie mag. Nun suchst du nach einer möglichst kleinen Auswahl an Pizzasorten, sodass jeder Gast mindestens eine Sorte davon mag.
Du hast dir die folgenden Strategien überlegt:
(1) Sortiere die Gäste nach der Anzahl der Sorten, die sie mögen – beginnend mit demjenigen, der am wenigsten Auswahl hat. Gehe dann der Reihe nach alle Gäste durch. Falls ein Gast noch keine Sorte aus der aktuellen Auswahl mag, füge zufällig eine Sorte aus seiner Liste hinzu.
(2) Sortiere alle Pizzasorten danach, wie viele Gäste sie mögen – beginnend mit der beliebtesten. Nimm der Reihe nach so lange Sorten in die Auswahl auf, bis alle Gäste mindestens eine davon mögen.
(3) Wie Strategie 2, aber nach jeder hinzugefügten Sorte bestimmst du die Sortierung neu, basierend auf den noch nicht zufriedengestellten Gästen.
Bei Gleichständen entscheidest du dich jeweils zufällig.
Führt eine dieser Strategien immer zu einer Auswahl mit der kleinstmöglichen Anzahl an Pizzasorten, unabhängig davon, welche Vorlieben die Gäste haben? Was wenn die Vorlieben so sind, dass es bei (2) und (3) nie zu Gleichständen in der Sortierung kommt?
