Zeigen, dass ein Teiler existiert

Question

Aufgabe:

Sei $n\in \mathbb{N}_{>0}$ und $M \subset \{1, . . . , 2n\}$ eine Menge von ganzen Zahlen mit $\vert M \vert = n + 1$ Elementen. Zeigen Sie, dass $a, b \in M$ mit $a \neq b$ existieren, sodass $a\vert b$ .

Problem/Ansatz:

Ich hab mich mittlerweile bei der Aufgabe komplett verrannt und bräuchte dringend mal einen Ansatz für die Aufgabe.

Comments

Jede Zahl z ∈ M lässt sich eindeutig in der Form z = 2^k*u mit k ∈ ℕ₀ und einer ungeraden Zahl u ∈ { 1 , ... , 2n-1 } schreiben.

Answer 1

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.

Comments

Vielleicht noch als Hinweis für den FS: Stichwort aus dem Unterricht ist (wahrscheinlich) Schubfachprinzip.