Frage von Oeliberg, 88

Kann mir bitte jemand bei dieser Mathe Aufgabe helfen (Mengenlehre)?

Aufgabe 3.3 Schubfachprinzip (4 Punkte)

Sei X = (1, 2 ...., 100). Zeigen Sie, dass es für alle Y ⊆ X mit |Y| = 10 zwei nicht leere Mengen Z, Z' ⊂ Y mit Z geschnitten Z' = leere Menge und Σ z (z€Z) = Σ z (z€Z') gibt.

Wie kann ich da das Schubfachprinzip drauf anwenden, hab es schon mehrfach versucht und komme eunfach zu keinem Ergebnis. Vielen Dank im Vorraus für Hilfe! :)

Antwort
von gunterled, 73

So habe ich mir das gedacht :

Es sei N die Menge aller Summen der echten Teilmengen von Y.

Pot(Y) sei die Potenzmenge von Y, also die Menge aller Teilmengen von Y. Es gilt: |P(Y)| = 2^|Y| = 2^10= 1024 Da es keine leeren Teilmengen von Y und es echte Teilmengen sein sollen, dürfen die Menge Y selber und die leer Menge, die Elemente von P(Y) sind nicht mitgezählt werden dürfen. Daraus folgt: |n|=|P(Y)| - 2 = 1024-2=1022 D.h. es müssen 1022 Summen, die von den Elementen von Z und Z' gebildet werden, miteinander verglichen werden.

Es sei M die Menge aller möglichen Ergebnisse der Addition der Elemente einer echten Teilmenge von Y.

Echte Teilmengen beinhalten maximal 9 Elemente. Die größte Summe, die von einer Teilmenge von Y gebildet werden könnte wäre die Summe aller Elemente der Teilmenge T={92,93,94,95,96,97,98,99,100} Σ t (t€T) = 864

D.h. es können nur Zahlen zwischen 1 und 864 als Ergebnisse vorkommen.

Nun wendet man das Schubfachprinzip an, Die Mächtigkeit der Menge aller Summen der echten Teilmengen von Y ( also N) ist größer als die Mächtigkeit der Menge aller Ergebnisse, die sich aus der Addition aller Elemente einer echten Teilmenge ergeben können ( also M).

Daher müssen einige Ergebnisse gleich sein.

Eine Funktion f: N -->M die alle Summen auf die Ergebnisse abbildet, wäre surjektiv und nicht Injektiv da |M| echt größer |N|, d.h. für mindestens ein Ergebnis € M liegen mehrere Summen € N als Urbilder vor. Es wird mindestens ein Ergebnis mehr als einmal abgebildet.

Kommentar von Oeliberg ,

Hmm, danke für die ausführliche Antwort. :)

Der Anfang hätte aber echt gereicht, ich hatte leider einfach keine Ahnung, wie ich das so beweisen sollte. Werd' mir das jetzt mal durchlesen und schauen ob das so klappt, scheint aber auf den ersten Blick wirklich so zu funktionieren. Ich selbst, hätte eigentlich auch einen Beweis mittels Kontraposition für sinnvoller gehalten (Zweierpotenzen), allerdings scheint bei der Vorangehensweise dann doch das Schubfachprinzip sinnvoller.  Die Aufgabe hat mich echt schon viel zu lange aufgehalten. -_-

Vielen Dank! :)

Antwort
von Juvenal, 88

Das Schubfachprinzip eine Methode, um Aussagen über eine endliche Menge zu machen.

Das Schubfachprinzip besagt:

Falls man n Objekte auf m Mengen (n,m > 0) verteilt, und n größer als m ist, dann gibt es mindestens eine Menge, in der mehr als ein Objekt landet.

Noch Fragen?

Kommentar von Oeliberg ,

Das Schubfachprinzip an sich ist mir schon bekannt. Nur ist mir nicht klar, wie ich es hier spezifisch anwenden soll.  Bin soweit, dass ich Y als n ansehe und m eben als Z + Z'. Allerdings weiß ich nicht wie mir das bei der Aufgabe so wirklich weiterhilft.

Kommentar von Juvenal ,

SO einfach lockst Du mich nicht aus der Reserve...........

Kommentar von Oeliberg ,

Entschuldige mal, ja. Du hast nicht einmal versucht hier irgendwie zu helfen. Das einzige, was du hier getan hast, war etwas vollkommen triviales und ergooglebares hinzuschreiben. Jeglicher Bezug zur Aufgabe fehlt. Ich habe mich durchaus mit meiner Lerngruppe schon eine Weile mit der Aufgabe beschäftigt, aber auf einen anständigen Weg, das mit dem Schubfachprinzip zu beweisen, sind wir nicht gekommen. Ich will hier keineswegs eine vollständige Lösung der Aufgabe bekommen sondern nur einen Hinweis, was ich betrachten sollte. Der lieber gunterled hat zwar gleich einen ganzen Lösungsweg bereitgestellt, es hätten aber auch nur der Anfang oder 'nen Hinweis zur Vorangehensweise gereicht. Wenn du nicht helfen möchtest, dann lass es doch bitte gleich sein.

Sie kennen die Antwort?

Fragen Sie die Community