Wenn es um Teilbarkeit geht, so liegt es doch nahe, den Modulo einer Zahl zu betrachten. Hier wäre es der Modulo zu \(n\). Wenn man \(n\) Schubfächer hat und jedem Schubfach die Modulo \(0\) bis \(n-1\) zuordnet, so wäre die Zahl (oder Summe) in dem Fach mit Modulo \(0\) durch \(n\) teilbar.
Beginne mit \(s_1= a_1\) und lege die Zahl in das Fach \(i_1\) mit \(s_1 \equiv i_1 \mod n\). Jetzt füge \(a_2\) hinzu und man bekommt \(s_2=a_1 + a_2\) und lege die Summe in das Fach \(i_2\) mit \(s_2 \equiv i_2 \mod n\). Führe das solange fort, bis Du entweder im \(m\)'ten Schritt das Fach mit dem Modulo \(0\) erreichst, oder ein Fach, welches bereits von einer Summe \(s_j\) belegt ist. Im ersten Fall ist \(s_m\) durch \(n\) teilbar und im zweiten Fall, also wenn das Fach bereits mit \(s_j\) belegt ist, dann ist
$$s_m -s_j= \sum_{k=j+1}^m a_k \equiv 0 \mod n$$
weil beide Summen \(s_m\) und \(s_j\) den gleichen Rest bei der Division durch \(n\) haben. Da nur \(n\) Fächer zur Verfügung stehen und \(n\) Summen gebildet werden können, muss eines der beiden Ereignisse mindestens einmal auftreten.
q.e.d.
Edit: \(a_1\) durch \(s_j\) ersetzt. Siehe auch Kommentare unten.
