Schubfachprinzip - Teilbarkeit von Teilmengen |
09.02.2021, 20:15 | Zuse123 | Auf diesen Beitrag antworten » | ||||||
Schubfachprinzip - Teilbarkeit von Teilmengen ich knobel nun an einer Übungsaufgabe, an der ich leider scheitere:' Aufgabe: Gegeben sei eine Menge M bestehend aus n verschiedenen natürlichen Zahlen. Zeigen Sie, dass es eine Teilmenge N von M gibt, sodass die Summe der Elemente von N durch n teilbar ist. Hinweis: Nummerieren Sie die Zahlen und betrachten Sie Summen aufeinanderfolgender Zahlen. Idee: Ich kann leider mit dem Hinweis wenig anfangen. Ich habe eine Menge M mit zufälligen Zahlen konstruiert (d.h. nicht nur aufeinanderfolgende Zahlen, da dass in der Aufgabenstellung so nicht spezifiziert ist) und diese nummeriert, aber ich kann irgendwie keine Muster erkennen. Dass die Summe der Elemente von N (nennen wir das mal m) durch n teilbar sind, bedeutet, dass ein k aus den natürlichen Zahlen existiert mit m = n * k. |
||||||||
09.02.2021, 20:24 | URL | Auf diesen Beitrag antworten » | ||||||
RE: Schubfachprinzip - Teilbarkeit von Teilmengen Nenne die Zahlen und betrachte die Summen für (das ist wohl mit aufeinander folgenden Zahlen gemeint) |
||||||||
09.02.2021, 20:56 | Zuse123 | Auf diesen Beitrag antworten » | ||||||
OK, also ich habe nun eine Menge M = {1,4,7,8,10,14} gewählt. D.h. |M| = n = 6. Nun habe ich wie von dir erklärt für j = 1...n Summen gebildet. s1 = 2 s2 = 1+4 = 5 s3 = 1+4+7 = 12 (durch n teilbar) s4 = 20 s5 = 30 (durch n teilbar) s6 = 44 Ich habe dies nun auch mit kleineren Mengen probiert. Die Aussage scheint stand zu halten, aber irgendwie kann ich keine allgemeine Aussage darauf ableiten. Vllt. ist es einfach zu spät geworden :gähn: |
||||||||
09.02.2021, 21:08 | URL | Auf diesen Beitrag antworten » | ||||||
Ja, so ist das gedacht, wobei s1=1, aber das nehme ich als Flüchtigkeitsfehler. Jetzt kann man sich fragen, ob immer eine der Summen durch n teilbar ist - oder allgemeiner, welche Zahlen man erhalten kann, wenn man eine solche Summe mit Rest durch n dividiert. In meiner Zeitzone ist es ca 20 Uhr GMT, wo lebst du denn? Edit: Nehmen wir als Beispiel mal folgendes Dann ist keine der Summen durch 5 teilbar. |
||||||||
09.02.2021, 21:36 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
@URL Ich würde auch die leere Summe hinzunehmen, das macht die Argumentation m.E. noch "geschlossener": Es gilt dann für alle mit . |
||||||||
09.02.2021, 21:43 | URL | Auf diesen Beitrag antworten » | ||||||
@HAL Da hast du natürlich recht, das vereinfacht die Sache, weil man keinen Spezialfall aussortieren muss. |
||||||||
Anzeige | ||||||||
|
||||||||
09.02.2021, 22:09 | Zuse123 | Auf diesen Beitrag antworten » | ||||||
Hatte eine Pause eingelegt. ^^
In deinem Bsp. wären s1 bis sn nicht teilbar, aber wenn man die Zahlen einzeln betrachtet und den Rest, den sie bei der Division mit n hinterlassen darunter schreibt, kann man einfach eine Summe konstruieren, sodass der Rest gleich n ist, also kein Rest besteht. Die Teilmenge, die das erfüllt wäre also N = {2, 6, 7}, oder N = {2,3} oder N = {3,7}. Mit dem Gedankengang verlasse ich wahrscheinlich den Pfad auf den der Hinweis mich bringen soll. Dass die Kombination der Reste mich auf eine teilbare Summe bringt, verstehe ich, aber warum das nun für jede Menge M möglich sein soll, ergibt sich mir einfach nicht. Warum wäre es nicht möglich eine Menge M so zu konstruieren, dass solche Kombinationen ausgeschlossen sind. :think:
Leben in der selben Zeitzone. Bin heute schon sehr lange mit Mathematik beschäftigt, fühlte sich nur sehr spät an.
OK, damit ließen sich wohl alle möglichen Teilmengen konstruieren. |
||||||||
09.02.2021, 22:21 | URL | Auf diesen Beitrag antworten » | ||||||
Angenommen du hast zwei Summen , die beide bei Division durch n den gleichen Rest haben. Was folgt dann für deren Differenz? Wenn du also zeigen kannst, dass es immer zwei derartige Summen gibt, bist du fertig. Um das zu zeigen,i ist das Schubfachprinzip nützlich. |
||||||||
09.02.2021, 23:44 | Zuse123 | Auf diesen Beitrag antworten » | ||||||
Hmm, meine Vermutung ist folgende: Man nehme die Summen s0 bis sn als Objekte und die Restklassen modulo n als Kategorien. Da Elemente der Restklasse Modulo 0 die gesuchte Teilmenge N liefern würde, kann man diese unberücksichtigt lassen. D.h. wir haben die Restklassen 1 .. n-1. Das sind mehr Kategorien als Objekte. Also kann man das Schubfachprnzip anwenden und erhält somit stets 2 Summen, dessen Differenz durch n teilbar ist. Wäre das so korrekt? |
||||||||
10.02.2021, 19:53 | URL | Auf diesen Beitrag antworten » | ||||||
Ja, so geht die Argumentation. Wobei man sich durch die Hinzunahme von die Überlegung zur Restklasse 0 sparen kann: Man hat die Summen aber nur n mögliche Reste bei Division durch n. Allso liefern mindestens zwei Summen bei Division durch n den gleichen Rest, ihre Differenz ist also durch n teilbar. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
Die Neuesten » |
|