Das Problem bei dem Schubfachprinzip ist immer: was sind die Schubfächer und was kommt rein? Die Schubfächer sind hier die Reste bei der Division durch \(n\) - zwangsläufig sind das \(n\) Stück für die Reste \(0\) bis \(n-1\). Das was rein kommt ist schon schwieriger.
Das sind die Reste der Division durch \(n\) der Partialsummen \(p_m\) mit der Definition$$p_m = \sum_{i=1}^m a_i \quad m \in [1;n]$$Nun kann man zwei Fälle unterscheiden.
Fall 1: einer der Reste ist =0 - also \(p_m \equiv 0 \mod n\), dann ist \(j=1\) und \(k=m\)
Fall 2: keiner der Reste ist =0, dann müssen mindestens in einem Fach zwei Partialsummen \(p_{j-1}\) und \(p_k\) (\(j \le k\)) mit identischem Rest liegen, da nur noch \(n-1\) Fächer (Fach 0 bleibt frei) gefüllt werden, aber immer noch \(n\) Reste von \(n\) Partialsummen vorhanden sind. In diesem Fall gilt \(n \mid \sum_{i=j}^k a_n\).
Siehe auch bei FU-Berlin.
Gruß Werner
