Schubfachprinzip: Unter 52 Zahlen zwischen 0 und 99 gibt es stets zwei Zahlen, deren Summe 100 ist.

Question

Aufgabe: Verwenden Sie das Schubfachprinzip, um folgende Behauptungen zu beweisen:

(a) Unter 52 Zahlen zwischen 0 und 99 gibt es stets zwei Zahlen, deren Summe 100 ist.

Problem/Ansatz:

Folgende Tupel wären doch (49,51), (48,52), (47,53).

Sind laut Schubfachprinzip dann die 52 Zahlen die Kategorien, und die von mir gefundenen Tupel die Objekte? Wie gehe ich laut Schubfachprinzip hier richtig vor?

Answer 1

Jede Zahl lässt sich eindeutig einem der folgenden Paare zuordnen:

(1, 99)

(2, 98)

(3, 97)

...

(49, 51)

und das "außergewöhliche" Paar (0,50)

Ist es möglich, die 52 Zahlen so auszuwählen, dass bei keinem dieser Paare die Summe 100 entsteht?

Comments

Wieso denn 52? Die Zahlen in den Tupeln, die du aufgeschrieben hast, gehen doch nur von 1-49, und von der rechten seite von 51 bis 99. Also das erste Element insgesamt 49 Zahlen, das zweite Element auch 49.

---

und das "außergewöhliche" Paar (0,50)

habe ich noch ergänzt.

Es sind also 49 Paare mit der Summe 100 und zwei Einzelzahlen, die für die Summe 100 "nicht zu gebrauchen sind".

Die Aufgabe verlangt nun die Auswahl von 52 Zahlen.

---

Ich stehe auf dem Schlauch. Ich glaube, bei 52 Zahlen ist dies nicht möglich, aber bei 51, oder?

Bei 52 muss es doch zwangsläufig immer 100 ergeben. Da wir ja 2 mehr als die Hälfte haben. He.... ich bin total verwirrt. Wie wäre denn der korrekte Gedankengang, wie man da an so eine Aufgabe ran geht?

Beim Schubfachprinzip gab es doch immer so Kästchen, in die man die Objekte einordnet. Wenn die Tupel die Objekte wären, könnten wir die doch alle einordnen, ohne, dass eins über bleibt, oder, dass ein Kästchen zwei Tupel besäße. Oder nicht?

---

Ich stehe auf dem Schlauch. Ich glaube, bei 52 Zahlen ist dies nicht möglich, aber bei 51, oder?

Richtig.

Bei 50 Paaren, aber 52 Zahlen muss man mindestens 2 Paare vollständig auswählen. Da nur eins der 50 Paare nicht die Summe 100 hat, muss wenigstens eins der beiden vollständig ausgewählten Paare die Summe 100 haben.

---

Na gut.

Dann gibt es da noch eine weitere Aufgabe:

Unter 55 Zahlen zwischen 1 und 100 gibt es stets zwei, deren Differenz 9 ist.
Gilt dies auch für 54 Zahlen?

Beispieltupel wären:

(100,91),

(99, 90),

(98, 89),

usw...

Aber wie gehe ich denn jetzt mit den Zahlen 55 und 54 um? Wie muss ich denken, bzw. was muss ich tun, um zu sehen, ob dies für 55 oder 54 Zahlen gilt, oder eben nicht? Muss ich dafür ALLE Tupel aufschreiben?

---

Ich habs. HIer gilt dann

(1,10), (2,11), (3,12), (4,13), (5,14), (6,15), (7,16), (8,17), (9,18)  => 1. Reihe

(19,28), (20,29), (21,30), (22,31), (23,32), (24,33), (25,34), (26,35), (27,36) => 2. Reihe

(37, 46), (38,47), (39,48), (40,49), (41,50), (42,51), (43,52), (44,53), (45, 54), => 3. Reihe

(55, 64), (56,65), (57,66), (58,67), (59,68), (60,69), (61,70), (62,71), (63,72) => 4. Reihe

(73, 82), (74,83), (75, 84), (76,85), (77,86), (78,87), (79,88), (80,89), (81,90) => 5. Reihe

(91, 100), (92), ... (((hier dann die Zahlen einzeln??? aber dann haben wi rnicht mehr zwei Zahlen, wobei die Differenz ja 9 sein muss) (100) => 6. Reihe

Je Reihe 9 Elemente. 9 * 6 Reihen = 54 Zahlen. Aber durch meine ausführliche Beschreibung sieht man ja, dass es dann für 54 Zahlen wohl nicht gilt, oder? Denn bei der letzten Reihe geht es ja nicht auf. Aber für 55 ja doch dann auch nicht. Oder? hä?

---

Die 92 "kann auch" mit der 83.

Die 93 "kann auch" mit der 84.

---

Stimmt! Aber darf man denn Zahlen doppelt verwenden? Weil die 83,84 usw wurden ja schon verwendet. Angenommen man darf.

Wie sieht es dann mit 55 zahlen aus? Wie erkenne ich das?

---

Ich würde hier mit Restklassen arbeiten.

Ein Schubfach enthält in dieser Reihenfolge die 12 Zahlen 1, 10, 19, 28, ...,91, 100 (also alle, die bei Teilung durch 9 den Rest 1 lassen.)

Das zweite Schubfach enthält die 11 Zahlen 2, 11, 20, 29, ...,92 (also alle, die bei Teilung durch 9 den Rest 2 lassen)

usw.

Das neunte Schubfach enthält die 11 Zahlen 9, 18, 27, 36, ...,99 (also alle, die bei Teilung durch 9 den Rest 0 lassen)

Die Differenz zweier Kugeln kann nur dann durch 9 teilbar sein, wenn sie aus dem gleichen Schubfach kommen UND dort auch noch benachbarte Zahlen sind.

Wenn man 54 Kugeln zieht, kann man aus jedem der 9 Schubfächer 6 Kugeln ziehen.

Zeige, dass dabei zwischen zwei gezogenen Kugeln eines jeden Schubfachs eine nicht gezogene Kugel stecken kann!

Was passiert mit der 55. Kugel?

---

Naja, die 55. Kugel bleibt dann über, oder? Die muss aber ja in irgend eins der Schubfächer rein. Was heißt das dann für mich? Dass es mit 55 Kugeln eben nicht aufgeht, oder?

Also wenn die Anzahl der Zahlen begrenzt ist, und die 9 Schubfächer so fest definiert sind, wie sie von dir definiert wurden. Und es also nur möglich ist, aus jedem Schubfach 6 Kugeln zu ziehen, * 9, dann sind es insgesamt 54. Dann kann man eben nicht 55 ziehen. Die wird dann zwar aus einem der 9 Schubfächer gezogen, aber die Differenz beträgt dann nicht 9, oder?