Aloha :)
Du kannst jede natürlich Zahl \(z\) in ihre Primfaktoren zerlegen. Da die einzige gerade Primzahl die \(2\) ist, gibt es also für jede natürliche Zahl \(z\) eine Darstellung der Form:$$z=2^k\cdot u\quad;\quad z\in\mathbb N\quad;\quad k\in\mathbb N_0\quad;\quad u\in\mathbb N\;\text{und ungerade}$$Für den Fall, dass \(z\) eine Zweierpotenz ist, setze \(u=1\). Für alle anderen Fälle ist \(u\) das Produkt aus allen ungeraden Primfaktoren der Zahl \(z\). In jedem Fall ist \(u\) daher ungerade.
Guppiere nun alle Zahlen der Menge \(M_n=\{1,\ldots,2n\}\) in Form dieser Zerlegung.
Für \(n=8\) als Beispiel sähe diese Zerlegung wie folgt aus:$$\begin{array}{c||c|c|c|c|c} & k=0 & k=1 & k=2 & k=3 & k=4\\\hline u=1 & 2^0\cdot1=1 & 2^1\cdot1=2 & 2^2\cdot1= 4& 2^3\cdot1=8 & 2^4\cdot1=16\\ u=3 & 2^0\cdot3=3 & 2^1\cdot3=6 & 2^2\cdot3=12& & \\ u=5 & 2^0\cdot5=5 & 2^1\cdot5=10& & & \\ u=7 & 2^0\cdot7=7 & 2^1\cdot7=14 & & & \\ u=9 & 2^0\cdot9=9 & & & & \\ u=11 & 2^0\cdot11=11 & & & & \\ u=13 & 2^0\cdot13=13 & & & & \\ u=15 & 2^0\cdot15=15 & & & & \end{array}$$
Alle ungeraden Zahlen werden in die Gruppe \(k=0\) einsortiert, die geraden Zahlen werden auf alle anderen Gruppen verteilt. Alle Zahlen, die in derselben Zeile stehen, haben den gemeinsamen Teiler \(u\), der sich bei der Division wegkürzt. Überig belibt im Zähler und im Nener jeweils eine Zweier-Potenz, sodass die größere Zahl in einer Zeile durch jede kleinere Zahl in derselben Zeile ohne Rest teilbar ist.
Da die Menge \(M_n\) genau \(n\) gerade und \(n\) ungerade Zahlen enthält, müssen bei der Auswahl von \((n+1)\) Zahlen mindestens 2 in dieselbe Zeile einsortiert werden. Die kleinere dieser beiden Zahlen teilt die größere ohne Rest.
