Beweis mit Schubfachprinzip Aufgabe?
Sei A eine Menge von 10 beliebigen natürlichen Zahlen zwischen 1 und 100. Es existieren zwei verschiedene Teilmengen von A, deren Elemente die gleiche Summe ergeben. Beweise mithilfe des Schubfachprinzips.
Ich verstehe nicht was ich machen soll, und vorgehen soll.
1 Antwort
Wie viele Möglichkeiten gibt es denn, Teilmengen aus 10 Elementen zu bilden?
Dazu muss man wissen, dass für die Mächtigkeit der Potenzmenge gilt...
Wir haben also 2^10 mögliche Teilmengen (Eigentlich 2^10-1 weil eine davon leer ist, aber vielleicht definiert ihr die Summe von der leeren Menge ja als 0).
Wenn wir jetzt also 1024 verschiedene Teilmengen haben und wir annehmen, dass jede dieser Teilmengen eine andere Summe hat (denn wenn es mind. 2 gibt, die gleich wären, wären wir schon fertig), dann gibt es 1024 verschiedene Zahlen.
Weil aber die maximale Teilmenge, also...
ist, was bedeutet, dass es keine Teilmenge gibt, deren Summe größer als 1000 ist, (also im Intervall 1-1000 liegt [oder 0-1000, wenn die leere Menge wie oben definiert]), folgt mit dem Schubfachprinzip, dass es mindestens zwei Mengen geben muss, deren Summe dieselbe ist.
Oder um es deutlicher auszudrücken: Ich habe 1024 verschiedene Teilmengen, denen ich aber nur 1000 (1001) verschiedene Werte zuweisen kann. Darum muss es Teilmengen geben, die denselben Wert haben.