Beweise Es gibt zwei disjunkte nichtleere Teilmengen mit gleicher Summe.

Question

Sei \( S \subseteq\{x \in \mathbb{N} \mid x \leq 100\} \) mit \( |S|=10 . \) Zeigen Sie, dass es dann imme zwei nicht-leere, disjunkte Mengen \( S_{1}, S_{2} \subseteq S \) gibt, für die gilt

\( \sum \limits_{x \in S_{1}} x=\sum \limits_{x \in S_{2}} x \)

(Hinweis: Vergleichen Sie die Anzahl der Teilmengen \( S^{\prime} \subseteq S \) mit de Größe des Bereichs, in dem die Summen \( \sum \limits_{x \in \mathcal{S}^{\prime}} x \) liegen können.)

Ich bin schon auf die Idee gekommen das dies mit dem Schubfachprinzip zusammenhängen könnte.

Answer 1

Beginne vielleicht mit dem Hinweis aus dem Duplikat.

S hat 2^10 Teilmengen. Davon sind 2^10 - 2 = 1022 'echte Teilmengen'
Somit müssen 1022 Summen verglichen werden.

Echte Teilmengen enthalten max. 9 Elemente. Nun schätze ich die möglichen Ergebnisse der Addition ab. Die Summe von 91+....+ 99 < 9*99 <900

Es können nur Zahlen zwischen 1 und 900 als Ergebnisse vorkommen. Folglich müssen einige der 1022 Ergebnisse gleich sein. qed.