Pferde-Paradox

Pferde-Paradox, Induktionsschritt funktioniert nur für ${\displaystyle n\geq 2}$ und nicht für ${\displaystyle n=1}$

Die zu beweisende Aussage kann wie folgt formuliert werden:[2]

In einer Herde mit ${\displaystyle n}$ Pferden besitzen alle ${\displaystyle n}$ Pferde die gleiche Farbe.

Nun führt man eine Induktion über ${\displaystyle n}$ durch und verankert die Induktion für ${\displaystyle n=1}$.

Besteht die Herde nur aus einem Pferd, so besitzen offensichtlich alle Pferde der Herde die gleiche Farbe.[3][2]

Nun setzt man voraus, dass die Aussage bereits für jede Herde mit ${\displaystyle n}$ Pferden gilt und zeigt, dass sie dann auch für jede Herde mit ${\displaystyle n+1}$ Pferden gilt. Eine Herde mit ${\displaystyle n+1}$ Pferden spaltet man in eine Herde von ${\displaystyle n}$ Pferden und ein einzelnes Pferd auf. In der Herde mit ${\displaystyle n}$ Pferden besitzen nun nach Induktionsvoraussetzung alle die gleiche Farbe, allerdings ist noch unklar, ob diese der des einzelnen Pferdes entspricht. Nun entfernt man ein weiteres Pferd aus der Herde mit ${\displaystyle n}$ gleichfarbigen Pferden, damit hat man nun eine gleichfarbige Herde von ${\displaystyle n-1}$, ein Einzelpferd, das dieselbe Farbe wie die Herde besitzt, und ein Einzelpferd unbekannter Farbe. Nun fasst man das Einzelpferd unbekannter Farbe mit der Herde von ${\displaystyle n-1}$ Pferden zu einer neuen Herde von ${\displaystyle n}$ Pferden zusammen. Nach Induktionsvoraussetzung müssen alle Pferde dieser neuen Herde gleichfarbig sein und damit dieselbe Farbe besitzen wie die vorherige Herde von ${\displaystyle n-1}$ Pferden und das zuvor entfernte gleichfarbige Einzelpferd. Damit hat man insgesamt ${\displaystyle n+1}$ Pferde gleicher Farbe.[3][2]

Der Induktionsschritt selbst ist korrekt, allerdings benötigt er eine Herde von mindestens zwei Pferden, damit das zusätzliche Einzelpferd unbekannter Farbe die Farbe der bisherigen Herde annimmt. Besteht die Herde nur aus einem Pferd, so erhält man nach dem Entfernen eines Pferdes gleicher Farbe eine leere Herde, in die das Pferd unbekannter Farbe eingefügt wird. Die leere Herde aber hat keine Farbe, die per Induktionsvoraussetzung auf das Pferd unbekannter Farbe übertragen werden könnte. Anders ausgedrückt, die ursprüngliche Herde von ${\displaystyle n}$ Pferden und die neue Herde von ${\displaystyle n}$ Pferden, bei der ein Pferd durch das Pferd unbekannter Farbe ausgetauscht wurde, müssen eine nicht leere Schnittmenge besitzen. Für einen korrekten Beweis müsste die Induktionsverankerung daher für ${\displaystyle n=2}$ anstatt für ${\displaystyle n=1}$ durchgeführt werden. Dies ist jedoch nicht möglich, da man nicht garantieren kann, dass zwei beliebige Pferde die gleiche Farbe besitzen.[3][2]