Schubfachprinzip, Beweis Taubenschlag-Prinzip

Question

Zeigen Sie die Gültigkeit der folgenden Aussage:

Wenn man aus einer Menge M =  {1, 2, ..., 3279} acht verschiedene Zahlen beliebig auswählt,

dann gibt es unter diesen stets zwei Zahlen a, b für die 1 ≤ a/b ≤ 3 gilt.

Hinweis: Das Schubfachprinzip (auch Taubenschlag-Prinzip) ist ein wichtiges mathematis ches Beweisprinzip. In seiner einfachsten Form sagt es über 10 Ta ubenschläge Folgendes aus: Sind in den Taubenschlägen 11 Tauben, so halten sich in wenigsten s einem Taubenschlag zwei Tauben auf. In seiner allgemeineren Form kann man für 51 Taub en folgern, dass sich in einem Taubenschlag sechs Tauben aufhalten. Überlegen Sie, wie si ch dieses Prinzip für obige Aufgabe anwenden lässt.

Answer 1

Wählt man die 1 dann müsste die nächste die 4 sein damit nicht gilt 4/1 <= 3.

Die nächste zahl wär dann die 4*3+1 = 13. Das führt man fort bis man 8 Zahlen hat.

1, 4, 13, 40, 121, 364, 1093, 3280

Die 3280 können wir aber gerade nicht mehr wählen und damit muss ein Verhältnis kleiner gleich drei sein.

Comments

Danke. Leider verstehe ich nur deine erste Zeile.

---

Naja. Welche Zahl geteilt durch vier ergibt ein Ergebnis > 3. Nenne die kleinste mögliche Zahl. Ist es die 13? Und jetzt nenne die kleinste Zahl die geteilt durch 13 mehr als 3 ergibt usw.

Erkenne ein Muster.

---

Und wie beweißt dies die Gültigkeit?

---

Er zieht einfach Kugeln, für die die Bedingung gerade nicht mehr eintrifft.

Das ist für 1 und 4 der Fall

4/1 = 4 >3 -> Bed. nicht erfüllt

Die nächste Kugel, für die die Bed gerade nicht erfüllt ist, ist die 13. 13/4 = 3,25 > 3 Bed. nicht erfüllt

Und das macht er solange bis er 8 Kugeln gezogen hat. Dann hat er 8 Kugeln, wo nie 2 Kugeln ein Verhältnis <3 haben. Da die letzte Kugel aber dann den Wert 3280 haben müsste, der größte Wert der verfügbaren Kugeln aber kleiner ist, folgt daraus, dass die Menge bei 8-maligem Ziehen zu klein ist, um die Bedingung 8 mal nicht zu erfüllen und es deshalb spätestens mit dem achten Zug zwei Kugeln geben muss, die die Bedingung erfüllen müssen.