Question

Zeige: Wählt man n + 1 Zahlen aus der Menge { 1, 2, 3, . . . , 2 n − 1, 2 n } ,so gibt es unter ihnen immer zwei, die zueinander teilerfremd sind

Wenn man die Paare (1,2) (3.4)... als Schubfächer annimt und die n+1 Zahlen als Tauben, kann man ja sagen ich habe n Paare und n+1 Tauben. Ich weiß außerdem das aufeinanderfolgende Zahlen immer teilerfrem sind.
Weiter weiß ich aber noch nicht., wie soll ich die Zahlen auf die Paare verteilen ? Sagen wir mal ich hätte n= 3 also 1,2,3,4,5,6
Die Paare wäre (1,2)(3,4)(5,6) und ich suche mir die Zahlen 2,3,4,5 aus.

Wie muss ich die jetzt verteilen ?

Comments

oder um es vielleicht besser zu verdeutlichen, ich nehme die Zahlen 1,2,3,6 oder 2,3,4,6
Die Reihenfolge müsste egal sein oder?

Answer 1

Wählt man n+1 verschiedene Zahlen aus {1,...2n}, dann gibt es mindestens ein Paar die benachbart sind, da es höchstens n "Lücken" gibt.
Seien k und k-1 diese Zahlen, dann sind sie teilerfremd, weil falls m die Zahl k und k-1 teilt, dann teilt sie auch ihre Differenz k-(k-1)=1. Also ist m=1 und deswegen teilerfremd.