Schubfachprinzip 10 elementige Teilmenge der Zahlen {1, 2 . . . , 100}

Question

kann mir jemand bei der Aufgabe helfen bitte, ich weiß nicht wie ich das angehen soll.

Sei X eine beliebige 10-elementige Teilmenge der Zahlen {1, 2 . . . , 100}. Zeigen Sie, dass dann immer
zwei nichtleere, disjunkte Mengen Y, Y'  ⊆ X exisitieren, so dass die Summe aller Zahlen aus Y mit
der Summe aller Zahlen aus Y' übereinstimmt.

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

Answer 1

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.