Beweis zur Teilerfremdheit in einer Liste

Question

Ich weiß nicht wie die Aufgabe löst

Aufgabe:

Beweisen Sie, dass, wenn man 31 Zahlen aus der Menge {1, 2, 3, …, 60} auswählt, zwei dieser Zahlen Teilerfremd zueinander sein müssen.

Comments

Soll das für beliebige 31 Zahlen gelten?

lul

---

Soll das für beliebige 31 Zahlen gelten?

Sicher nur für 31 verschiedene Zahlen aus der Menge {1, ..., 60}.

Ich darf also sicher nicht 31-mal die 2 nehmen.

Answer 1

Egal welche $31$ Zahlen du wählst, zwei werden immer direkt aufeinander folgend sein, insbesondere teilerfremd. Denn sonst müsste deine Menge ja mindestens $31 + 30 = 61$  Zahlen haben.