Aufgabensammlung Mathematik: Auf einer Party haben alle denselben Namen

Auf einer Party haben alle denselben Namen

Behauptung: Auf einer Party mit $n\geq 1$ Gästen heißt jeder gleich.

Induktionsanfang: Wenn auf einer Party nur ein Gast ist, ist die Aussage wahr (weil es nur einen Namen gibt).

Induktionsschritt: Seien auf einer Party $n+1$ Gäste. Wir schicken einen raus. Dann sind auf dieser Party nur noch $n$ Gäste. Nach Induktionsvoraussetzung haben all diese $n$ Gäste den gleichen Namen. Nun holen wir den Gast, der draußen stand, wieder rein und schicken einen anderen Gast raus. Nun haben nach Induktionsvoraussetzung wieder alle den gleichen Namen. Also müssen alle $n+1$ Gäste den gleichen Namen haben.

Daraus folgt, dass alle Gäste auf einer Party gleich heißen.

Lösungshinweis

Versuche die einzelnen Induktionsschritte nacheinander explizit durchzuführen. Versuche also den Induktionsschritt von $n=1$ auf $n=2$, von $n=2$ auf $n=3$, usw. nachzuvollziehen.

Lösung

Der Induktionsschritt kann nicht von $n=1$ auf $n=2$ durchgeführt werden. Dies kannst du erkennen, wenn du dir den obigen Induktionsschritt für $n=1$ anschaust (Ersetzungen der ursprünglichen Variablen $n+1$ und $n$ sind orange markiert):

Seien auf einer Party zwei Gäste. Wir schicken einen raus. Dann ist auf dieser Party nur noch ein Gast. Nach Induktionsvoraussetzung hat dieser eine Gast den gleichen Namen wie alle anderen auf der Party. Nun holen wir den Gast, der draußen stand, wieder rein und schicken einen anderen Gast raus. Nun haben nach Induktionsvoraussetzung wieder alle den gleichen Namen. Also müssen alle zwei Gäste den gleichen Namen haben.

Wenn du aber zwei Gäste auf einer Party hast und jeweils einen rausschickst, dann verbleibt auf der Party jeweils nur ein Gast. Aber dies bedeutet nicht, dass beide rausgeschickten Gäste dengleichen Namen haben, weil es keine Person auf der Party gibt, die die ganze Zeit auf der Party ist ↯.