Question

Beweisen Sie folgende Aussagen mit Hilfe des Schubfachprinzips:

(a) Sei \( M=\{1,2, \ldots, 14\} \). Weiter sei \( S \subseteq M \) mit \( |S|=6 \). Dann gibt es zwei verschiedene echte, nichtleere Teilmengen \( A \) und \( B \) von \( S \), d.h. also \( \emptyset \neq A \subsetneq S \) und \( \emptyset \neq B \subsetneq S \) mit \( A \neq B \), so dass die Summe der Elemente in \( A \) gleich der Summe der Elemente in \( B \) ist.
(b) Sei \( n \in \mathbb{N} \) und seien \( a_{1}, \ldots, a_{n} \in \mathbb{Z} \). Dann gibt es \( k, \ell \in \mathbb{N} \) mit \( 0 \leq k<\ell \leq n \), so dass gilt:
\( n \mid a_{k+1}+\ldots+a_{\ell} \)
(Hinweis: Sie dürfen verwenden, dass es auf \( \mathbb{Z} \) eine Division mit Rest gibt, d.h. für \( a, b \in \mathbb{Z} \) mit \( b \neq 0 \) gibt es eindeutige \( q, r \in \mathbb{Z} \) mit \( a=q b+r \) und \( 0 \leq r<|b| \).)

Answer 1

a) Sei \( S \subseteq\{1,2, \ldots, 14\} \) mit \( |S|=6 \). Es gibt insgesamt \( 2^{6}-1 \) nichtleere Teilmengen von \( S \). Da \( A \) und \( B \) verschieden und nicht leer sein müssen, unterscheiden sie sich in mindestens einem Element, somit muss gelten \( |A| \leq 5 \wedge|B| \leq 5 \). Die maximale Summe, welche die Mengen \( A \) bzw. \( B \) erreichen können beläuft sich also auf

\( 14+13+12+11+10=60 \)
und somit könne maximal 60 Zahlen durch die Summen der potentiellen \( 2^{6}-2 \) Teilmengen erreicht werden (wir schliessen die Leere und ganze Menge aus, wie beschrieben). Wollen wir jetzt diese 62 Teilmengen auf die 60 möglichen Summen verteilen, so müssen mindestens zwei Teilmengen die gleiche Summe haben.

b) Es gibt \( n-1 \) Schubfächer, nämglich die Reste bei der Division Modulus \( n \). Betrachten wir die \( n \) Summen
\( a_{1}, a_{1}+a_{2}, \ldots, \sum \limits_{i=1}^{n} a_{i} \)
Wir nehmen an, alle obigen Summen sind nicht durch \( n \) Teilbar, sonst wären wir ja fertig. Dann gibt es jedoch nach dem Schubfachprinzip 2 Summen, welche den Gleichen Rest Modulus \( n \) haben (es gibt ja schliesslich nur \( n-1 \) Reste). Wir bezeichnen diese Summen mit \( S_{1}=\sum \limits_{i=1}^{k} \) und \( S_{2}=\sum \limits_{i=1}^{\ell} \) (o.V.d.A. nehmen wir an, \(k<\ell\)) und somit
\( S_{1} \equiv_{n} S_{2} \Longleftrightarrow S_{2}-S_{1} \equiv_{n} 0 \)
womit \( S_{2}-S_{1}=\sum \limits_{i=k}^{\ell} a_{i} \) durch \( n \) teilbar ist.