Teilmengensummen-Training

Sechs positive ganze Zahlen sind jeweils höchstens 9. Zeige, dass zwei verschiedene Teilmengen dieselbe Summe besitzen.

Folgere aus Aufgabe 1, dass es zwei disjunkte nichtleere Indexmengen mit gleicher Summe gibt.

Zehn positive ganze Zahlen haben Gesamtsumme höchstens 100. Zeige, dass zwei disjunkte nichtleere Teilmengen dieselbe Summe besitzen.

Zeige: Sind $a_1,\ldots,a_n$ positiv mit Summe $S$ und gilt $2^n>S+1$, dann gibt es zwei disjunkte nichtleere Teilmengen der Indizes mit gleicher Summe.

Zeige: Unter zehn positiven ganzen Zahlen, die jeweils höchstens 10 sind, existieren zwei disjunkte nichtleere Teilfamilien gleicher Summe.

Zeige: Haben $n$ positive ganze Zahlen paarweise verschiedene Teilmengensummen, so ist ihre Gesamtsumme mindestens $2^n-1$.

Zeige, dass $1,2,4,\ldots,2^{n-1}$ tatsächlich paarweise verschiedene Teilmengensummen besitzen.

Zeige: Jede Liste von $n$ positiven ganzen Zahlen mit Gesamtsumme höchstens $2^n-2$ besitzt zwei disjunkte nichtleere Teilmengen gleicher Summe, und die Schranke kann nicht erhöht werden.