Schubfachprinzip, wie geht das?

Question

Aufgabe:

Sei A Teilmenge von {1,…,140} mit 71 Elementen. Gibt es a,b aus A mit |a-b|=10? Wie ist die Antwort im Fall |A|=70?

Hinweis: Schubfachprinzip mit 10 Schubfächern.  

Problem/Ansatz:

Ich habe echt überhaupt keine Ahnung und wäre über eine Erklärung für Anfängern dankbar!

Mein Ansatz ist: Ich habe a Objekte und n Fächer. Verteile ich a*n+1 Objekte auf n Fächer, so hat ein Fach mehr als a Objekte. Deshalb habe ich 71=n*a+1 gesetzt. Mein n ist ja nach dem Hinweis 10. Dann habe ich 71=10*a+1, so muss mein a=7 sein.

Aber ist das richtig?

Answer 1

Wir betrachten die 10 Kongruenzklassen mod 10.

Wenn wir die 71 Elemente auf die 10 Klassen verteilen,

gibt es nach dem Schubfachprinzip eine Klasse, die mindestens

8 Elemente besitzt. Diese seien

\(a_1\equiv a_2\equiv a_3\equiv a_4\equiv a_5\equiv a_6\equiv a_7 \equiv a_8\) mod 10.

Seien diese der Größe nach angeordnet. Wäre nun der Abstand zweier

aufeinander folgender immer \(\geq 2\cdot 10\), dann wäre

\(a_8\geq a_1+140\), da aber \(a_1\geq 1\) ist, wäre dann

\(a_8\geq 141\) im Widerspruch zur Voraussetzung.

Da du dich als Anfänger bezeichnest, hier eine andere Formulierung:

Seien \(K_0,K_1,\cdots,K_9\) die Klassen der Zahlen aus \(\{1,\cdots,140\}\)

mit \(x\in K_i\iff \text { Einerstelle von } x \text{ ist } i\).

Je zwei Elemente einer solchen Klasse unterscheiden sich

um ein ganzzahliges Vielfaches von \(10\). Man verteile nun die 71 Zahlen

auf diese Klassen. Dann gibt es nach dem Schubfachprinzip

eine Klasse \(K_i\), die mindestens 8 Zahlen enthält, usw. usw.

Comments

K₁,…,K₉ weil wir die Zahlen von 1 bis 140 modulo 10 betrachten?

Und wie kommst Du auf die Zeile danach? 19 fällt beispielsweise in K₉ weil 19=1 Rest 9?

Je zwei Elemente einer solchen Klasse unterscheiden sich um ein ganzzahliges Vielfaches von 10.

Beispiel K₉: 9, 19, 29,…

Man verteile nun die 71 Zahlen auf diese Klassen.

Aber es sind doch 71 zufällige/verschiedene aus der Menge {1,…,140}… ?

---

Wir betrachten nicht \(K_1\) bis \(K_9\), sondern \(K_0\)  bis \(K_9\).

Jede Zahl hat doch eine Einerstelle aus 0 bis 9. Natürlich sind

ds die Kongruenzklassen (Restklassen) mod 10. Aber es hätte ja sein

können, dass du noch keine Ahnung von Kongruenzen hast.

Man verteile nun die 71 Zahlen auf diese Klassen.

Meinetwegen sage: die 71 Zahlen verteilen SICH auf die 10 Klassen.

Dass ich das etwas dynamischer formuliere, ist meiner Freude

an lebendiger Darstellung mathematischer Sachverhalte geschuldet.

---

K₁,…,K₉

Schreibfehler, meinte natürlich K₀,…,K₉

Meinetwegen sage: die 71 Zahlen verteilen SICH auf die 10 Klassen.

Aber da diese 71 Zahlen zufällig ausgewählte Zahlen aus der Menge {1,…,140} sind, müssen sie sich doch nicht gleichmäßig auf die Klassen verteilen, sodass in allen Klassen jeweils 7 sind und in einer 8. Ich weiß nicht, ob Du meinen Denkfehler/Verständnisproblem verstehst.

Und noch eine Frage: Da es mindestens eine Zahl gibt, die in dieselbe Klasse fällt, wie eine andere, gilt |a-b|=10 nicht für jedes a und b aus A. Folglich gilt die erste Aussage nicht. Aber für |A|=70 gibt es ein a und b, sodass |a-b|=10, richtig?

---

Das Schubfachprinzip setzt keine besondere Verteilung voraus.

Das ist ja gerade der "Witz" des Prinzips.

Doch: für \(|A|=71\) gilt das. Das habe ich doch gerade bewiesen.

Ich habe nicht bewiesen, dass es genau eine Klasse mit

8 Zahlen gibt, sondern dass es mindestens eine solche

Klasse gibt. Hätten alle 10 Klassen weniger als 8 Elemente, also

höchstens 7, dann gäbe es in A max. \(10\cdot 7=70\) Zahlen.

Den Fall 70 habe ich nicht weiter untersucht.

---

Achso!, das eine Element, was sich in irgendeine Restklasse einordnet, wo bereits ein Element aus A ist, hat ja auch Abstand 10 zu der anderen Zahl und deswegen gilt die Aussage für |A|=71

---

Für |A|=70 könnte man doch dieselbe Argumentation nutzen oder? Man verteilt einfach die 70 Zahlen auf die Restklassen K₀,…,K₉.

Ich habe überlegt, die Zahlen 1,…,140 auf die Restklassen zu verteilen:

	10	20	30	40	50	60	70	80	90	100	110	120	130	140
1	11	21	31	41	51	61	71	81	91	101	111	121	131
2	12	22	32	42	52	62	72	82	92	102	112	122	132
3	13	23	33	43	53	63	73	83	93	103	113	123	133
4	14	24	34	44	54	64	74	84	94	104	114	124	134
5	15	25	35	45	55	65	75	85	95	105	115	125	135
6	16	26	36	46	56	66	76	86	96	106	116	126	136
7	…
8
9

Erste Zeile ist K₀ und so weiter…

Wenn ich 70 Zahlen habe und sie sich alle auf die Restklassen verteilen, kann ich niemals einen Abstand von 10 haben oder?

---

Warum sollte das nicht möglich sein?

Du solltest lieber schauen, ob es eine Verteilung gibt,

so dass es kein Paar (a,b) mit |a-b|=10 gibt.

Du scheinst an dieser Stelle ein "Logik-Problem"

zu haben ;-)

---

Aber der Abstand von 10 ist doch nur innerhalb einer Restklasse möglich. Zwei a und b aus der Menge A und jeweils verschiedener Restklasse, haben nie genau Abstand 10. Höchstens Abstand 9.

Und ja, das habe ich leider… :(

---

Betrachte mal$$A=\{10,30,50,70,90,110,130,\\11,31,51,71,91,111,131,\\12,32,52,72,92,112,132,\\13,33,53,73,93,113,133,\\14,34,54,74,94,114,134,\\15,35,55,75,95,115,135,\\16,36,56,76,96,116,136,\\17,37,57,77,97,117,137\\18,38,58,78,98,118,138\\19,39,59,79,99,119,139\}$$In dieser Menge gibt es kein Paar mit Abstand 10.

---

Zur Logik:

Bei |A|=71 gilt für jede Verteilung, dass ein Paar a,b mit Abstand 10

existiert. Bei |A|=70 gilt dies nicht, d.h. nicht für jede Verteilung

ist es wahr, dass ein Paar mit Abstand 10 existiert, oder

anders ausgedrückt:

Bei |A|=70 gibt es eine Verteilung, so dass für jedes Paar

a,b der Abstand ungleich 10 ist.

---

Herzlichen Dank! Auch an MatheCoach!

Ich habs endlich verstanden!

---

Aber da diese 71 Zahlen zufällig ausgewählte Zahlen aus der Menge {1,…,140} sind, müssen sie sich doch nicht gleichmäßig auf die Klassen verteilen,

Nirgends steht dass sich die Zahlen gleichmäßig verteilen. Du kannst 71 Zahlen auch so aus 1, ..., 140 auswählen, dass darunter 14 Zahlen mit Endziffer 1 sind, aber keine mit Endziffer 4 ist.

Das Schubfachprinzip sichert dir nur zu dass für jede mögliche Menge an 71 Zahlen irgendeine dieser Mengen mindestens 8 Elemente hat

Answer 2

Nach genauerem Überlegen war dieser erste Ansatz falsch!

Wenn ich die Elemente wie folgt wähle...

{1, 3, 5, 7, 9, 10, 12, 14, 16, 18, 19, ...}

dann bekomme ich mehr als 70 unter und keine 2 Zahlen haben einen Abstand von genau 10.

Also im Kommentar weiterlesen...

Comments

Wie bist Du denn vorgegangen und wie hast Du das Schubfachprinzip angewendet? Und was sind Deine Fächer? Sry, aber ich verstehe nicht die Vorgehensweise bei diesem Prinzip…

Hast Du jetzt quasi ein Gegenbeispiel gefunden?

---

Wenn wir ein Schubfach nehmen für einen Zehnerbereich mit dem Abstand 2.

Für die Zahlen von 1 bis 10 also 1, 3, 5, 7, 9

Für die Zahlen von 11 bis 20 also 12, 14, 16, 18, 20

Für die Zahlen von 21 bis 30 also 21, 23, 25, 27, 29

...

Dann habe ich 14 * 5 Zahlen also 70 Zahlen die ich unterbringen kann. Eine 71 Zahl kann ich nicht mehr unterbringen.

---

Oder betrachte mal 2 Zehnerreihen

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20

Von diesen 20 Zahlen kannst du genau 10 auswählen. Nämlich aus jeder Spalte genau eine Zahl.

Sie dürfen eben nur nicht genau übereinander liegen. D.h. von diesen 20 Zahlen können wir genau 10 auswählen.

Da sich das so vortsetzt kannst du von 140 Zahlen eben genau 70 auswählen die nie eine Differenz von 10 haben. Die 71 Zahl kannst du nicht mehr auswählen, da sie in einen der belegten 20er Blocks fallen würde.

---

{1, 3, 5, 7, 9, 10, 12, 14, 16, 18, 19, ...}

dann bekomme ich mehr als 70 unter und keine 2 Zahlen haben einen Abstand von genau 10.

19-9=10

---

19-9=10

Gut erkannt! Deswegen hatte ich das schon vor 2 Stunden korrigiert und geschrieben

Nach genauerem Überlegen war dieser erste Ansatz falsch!

ich sollte es besser löschen und gleich durch den Kommentar ersetzen.

---

Ok. Ich dachte, der "erste Ansatz" bezog sich auf die Überlegungen des Fragestellers.

---

ermanus hat das sehr schön erklärt. Meine Zehlerreihen laufen auf genau das hinaus man hat genau 10 Spalten und in diesen Spalten sind 14 Zeilen und man darf nur in 7 von diesen 14 Zahlen wählen. Die 8. Zahl hätte einen Abstand von weniger als 20 und damit 10.

---

@mathematiquaa

Irgendwie Scheinst du immer noch so große Probleme zu haben.

Mach doch die Tabelle die ich angefangen habe einfach mal weiter mit den 10 Resteklassen.

K1	K2	K3	K4	K5	K6	K7	K8	K9	K0
1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100
101	102	103	104	105	106	107	108	109	110
111	112	113	114	115	116	117	118	119	120
121	122	123	124	125	126	127	128	129	130
131	132	133	134	135	136	137	138	139	140

Du sollst jetzt aus der Tabelle 71 Zahlen wählen die Paarweise eine Differenz von ungleich 10 haben. Zunächst mal kannst du in jeder Spalte 7 Zahlen auswählen die keinen Abstand von 10 haben. Das funktioniert prima. Du kannst allerdings keine 71 Zahl finden die keinen Abstand von 10 zu einer bereits gewählten Zahl hat weil das die 8. Zahl in einer Spalte mit 14 Zeilen wäre. Und dort gibt es nur 7 Zahlen die jeweils einen Abstand von 20 haben.

---

Ich glaube das habe ich jetzt endlich verstanden: Wenn ich den Auftrag hätte, 71 Zahlen zu wählen, die keinen Abstand von 10 haben, würde ich einfach die ersten 10 aus der ersten Zeile, die nächsten 10 aus der 3. Zeile usw. auswählen (jeweils eine Zeile immer überspringen). Das geht aber nur 7 mal, da ich 14 Zeilen habe. Die 71. Zahl muss also aus einer „Zwischenzeile“, die wir übersprungen sind, gewählt werden, sodass wir einen Abstand von 10 haben.

Aber mit |A|=70 geht das sehr wohl, denn da habe ich das Problem mit der 71.Zahl nicht mehr und kann 70 Zahlen finden, wo der Abstand zwischen zwei Zahlen paarweise ungleich 10 ist. Das bedeutet für den Fall |A|=70 gilt die Aussage nicht, für |A|=71 aber schon, richtig?

---

gilt die Aussage nicht,

Du hattest keine Aussage sondern eine Frage

Sei A Teilmenge von {1,…,140} mit 71 Elementen. Gibt es a,b aus A mit |a-b|=10?

Ja hier gibt es mind. ein paar Zahlen a, b für die der Betrag der Differenz 10 ist.

Wie ist die Antwort im Fall |A|=70

Hier muss es kein paar Zahlen a, b geben, für die der Betrag der Differenz 10 ist.

---

Dank für die Hilfe und die Geduld :)!

---

Viel Erfolg für die Arbeit.

---

Dankeschön :)!