0 Daumen
854 Aufrufe

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?

Avatar von

2 Antworten

+1 Daumen
 
Beste Antwort

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.

Avatar von 29 k

K1,…,K9 weil wir die Zahlen von 1 bis 140 modulo 10 betrachten?

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

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


Beispiel K9: 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.

K1,…,K9

Schreibfehler, meinte natürlich K0,…,K9

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 K0,…,K9.

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


102030405060708090100110120130140
1112131415161718191101111121131
2122232425262728292102112122132
3132333435363738393103113123133
4142434445464748494104114124134
5152535455565758595105115125135
6162636465666768696106116126136
7












8













9













Erste Zeile ist K0 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

0 Daumen

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...

Avatar von 477 k 🚀

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

12345678910
11121314151617181920

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.

K1K2K3K4K5K6K7K8K9K0
12345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100
101102103
104
105
106
107
108
109
110
111112
113
114
115
116
117
118
119
120
121122123124125
126
127
128
129
130
131132
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 :)!

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community