Schubfachprinzip - Teilbarkeit von Teilmengen

Neue Frage »

Zuse123 Auf diesen Beitrag antworten »
Schubfachprinzip - Teilbarkeit von Teilmengen
Hallo,

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.
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)
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:
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? smile

Edit: Nehmen wir als Beispiel mal folgendes Dann ist keine der Summen durch 5 teilbar.
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 .
URL Auf diesen Beitrag antworten »

@HAL Da hast du natürlich recht, das vereinfacht die Sache, weil man keinen Spezialfall aussortieren muss.
 
 
Zuse123 Auf diesen Beitrag antworten »

Hatte eine Pause eingelegt. ^^

Zitat:
Original von URL
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.

Edit: Nehmen wir als Beispiel mal folgendes Dann ist keine der Summen durch 5 teilbar.

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:

Zitat:
Original von URL
In meiner Zeitzone ist es ca 20 Uhr GMT, wo lebst du denn? smile

Leben in der selben Zeitzone. smile Bin heute schon sehr lange mit Mathematik beschäftigt, fühlte sich nur sehr spät an. Big Laugh

Zitat:
Original von HAL 9000
@URL

Ich würde auch die leere Summe hinzunehmen, das macht die Argumentation m.E. noch "geschlossener": Es gilt dann

für alle mit .

OK, damit ließen sich wohl alle möglichen Teilmengen konstruieren.
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.
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?
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.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »