Beweis zu Schubfachprinzip: Unter n+1 Zahlen aus {1, …, 2n} gibt es immer zwei aufeinanderfolgende Zahlen.

Question

Aufgabe (Schubfachprinzip):

Zeigen Sie, dass für alle \( n \in \mathbb{N}_{0} \backslash\{0\} \) die folgende Aussage gilt:

Unter \( n+1 \) Zahlen aus \( \{1, \ldots, 2 n\} \) gibt es immer zwei aufeinanderfolgende Zahlen.

Problem/Ansatz:

Ich habe mir zunächst für n=4 verdeutlicht, was die Aussage bedeutet. Für n=4 ergibt sich dann ja folgende Menge : {1,2,3,4,5,6,7,8}. Wenn ich n+1 Zahlen aus dieser Menge auswähle (also 5) soll es nach der Aussage immer zwei aufeinanderfolgende Zahlen geben. Da $$n+1 > \frac{2n}{2}$$  gilt, kann es ja maximal n Lücken geben und wenn ich n+1 Zahlen auswähle, muss es somit immer zwei aufeinanderfolgende Zahlen geben.

Answer 1

Hallo Max,

Deine Überlegung mit den Lücken ist völlig ok. Nun sollst Du diese Behauptung aber mit Hilfe des Schubfachprinzips lösen. Und beim 'Schubfachprinzip' stellt sich stets die Frage:

Was sind hier die Schubfächer?

Vorschlag: Definiere in diesem Fall ein Schubfach als ein Paar auf einander folgender Zahlen, wobei aber keine Zahl in zwei unterschiedlichen Schubfächern vorkommt. Also $$\begin{aligned}1.&\text{Fach:} && \{1,\, 2\} \\ 2.&\text{Fach:} && \{3,\, 4\} \\3.&\text{Fach:} &&\{5,\, 6\} \\&\dots\\n.&\text{Fach:}&&\{2n-\!1,\, 2n\}\end{aligned}$$Das sind genau \(n\) Fächer. Die ersten \(n\) Zahlen werden in (aus) den \(n\) Fächern verteilt. Und für die \(n+1\)'te Zahl muss zwangsläufig ein Fach genutzt werden, wo schon eine Zahl drin steckt. Und damit liegt in diesem Fach ein Zahlenpaar aus zwei auf einander folgenden Zahlen.

Gruß Werner