Schubfachprinzip

Neue Frage »

KiAn Auf diesen Beitrag antworten »
Schubfachprinzip
Moin moin!
Kann mir jemand vielleicht mit meinem Poblem weiterhelfen??

Ich weiß zwar, dass ich diese Aufgabe mit Hilfe des Schubfachprinzips lösen muss, allerdings kann ich dieses Prinzip praktisch bei schwierigen Aufgaben noch nicht anwenden.

eine Menge von ganzen Zahlen. Zeigen Sie: Es gibt eine Teilmenge von M wofür die Summe der Elemente durch n teilbar ist .

DAnke schonmal
AD Auf diesen Beitrag antworten »

Betrachte doch mal die speziellen Teilmengen

und für .

Das sind genau Stück...
KiAn Auf diesen Beitrag antworten »

Vielen Dank für den Tipp, werde dann mal versuchen einen Beweis aufzubauen.
KiAn Auf diesen Beitrag antworten »

Hallo nochmal...ich habe mir das mit den Teilmengen mal überlegt....sind das nicht
Teilmengen???

Viele Grüße
AD Auf diesen Beitrag antworten »

Insgesamt schon.

Was aber auch bedeutet, dass du meinen Tipp nicht verstanden hast. In dem geht es nicht um alle Teilmengen, sondern um (im Inklusionssinn) aufsteigende Teilmengen, d.h.

.


Das Schubfachprinzip ist an sich sehr einfach. Richtig wertvoll wird es eben erst, wenn man es kreativ einzusetzen vermag. Im vorliegenden Fall habe ich dir passende Mengen genannt - aber noch nicht die Art der Schubfächer, wo diese Mengen einzusortieren sind. Welche Schubfachfestlegung ist denn naheliegend (und dann auch sinnvoll), wenn es um Teilbarkeit durch geht?
KiAn Auf diesen Beitrag antworten »

Mich stört dabei die leere Menge so ein bißchen, die ist für diese Aufgabe ja nicht hilfreich mit einzubeziehen. Denn die leere Menge ist ja sicher nicht teilbar durch n.

Wenn ich nun die Summe der Teilmengen A1 bis An betrachte, so haben diese n Restklassen.

Sind diese Summen aber nicht teilbar durch n, gehört keine Summe zur ersten Restklasse (also Rest=0).

D.h. ja, dass diese Summen in die anderen (n-1) Restklassen fallen.

Wenn ich nun die n Summen auf die Restklassen verteile, dann gibt es mind. zwei Summen, die in der gleichen Restklasse sind.
Bilde ich die Differenz der beiden Summen, so hebt sich der Rest auf und dies wird dann sicher durch n teilbar sein..... oder? verwirrt

mmmhh
 
 
AD Auf diesen Beitrag antworten »

Ganz genau - fehlt nur noch ein Baustein:

Wie kriegt man eine Menge, deren Elementsumme gerade der von dir genannten "Differenz der beiden Summen" entspricht?

Zitat:
Original von KiAn
Mich stört dabei die leere Menge so ein bißchen, die ist für diese Aufgabe ja nicht hilfreich mit einzubeziehen. Denn die leere Menge ist ja sicher nicht teilbar durch n.

Eine falsche Meinung, wie du der endgültigen Lösung ansehen wirst. Die Elementsumme der leeren Menge ist ganz einfach Null.
Neue Frage »
Antworten »



Verwandte Themen

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