Wie zeigt man dass 2 nichtleere disjunkte Mengen Y, Y' ⊆ X existieren wo die Summen der Zahlen aus Y & Y' übereinstimmen

Question

Sei X eine beliebige 10-elementige Teilmenge der Zahlen {1, 2 . . . , 100}.

Wie zeigt manmit dem Schubfachprinzip, dass immer zwei nichtleere, disjunkte Mengen Y, Y' ⊆ X exisitieren, so dass die Summe aller Zahlen aus Y mit der Summe aller Zahlen aus Y' übereinstimmen?

Ein Hinweis: Es ist bekannt, dass eine n-elementige Menge genau 2n Teilmengen besitzt.

Danke schon mal im Voraus,

MfG

Answer 1

Hier muss doch irgendwo ein Nest sein!
Die Frage begegnet mir heute zum dritten Mal. Also:

Es gibt 2^10=1024 Teilmengen einer 10-elementigen Menge, davon 1023 nichtleere Teilmengen.
10 ausgewählte Zahlen haben eine Summe von höchstens 91+92+...+99+100=945, wählt man weniger aus oder kleinere Zahlen, ist die Summe entsprechend kleiner.
Es gibt also maximal 945 verschiedene Summe, die eine ausgewählte nichtleere Teilmenge haben kann.
Da es mehr Teilmengen als mögliche Summen gibt, gibt es mindestens zwei Teilmengen mit der gleichen Summe. Diese Teilmengen müssen zwar noch nicht als disjunkt vorausgesetzt werden, aber wenn man aus beiden Mengen die übereinstimmenden Elemente entfernt, hat man disjunkte Restmengen mit wiederum übereinstimmender Summe.