Partialsummen und teilbare Blöcke

Schubfachprinzip und modulare Invarianten · Abschnitt 54 von 64

Definition

Partialsummen

Für eine Folge $a_1,\ldots,a_n$ setzt man $S_k=a_1+\cdots+a_k$ . Jede zusammenhängende Blocksumme ist eine Differenz $S_j-S_i$ .

Satz

Nichtleerer teilbarer Block

Unter $n$ ganzen Zahlen gibt es stets einen nichtleeren zusammenhängenden Block, dessen Summe durch $n$ teilbar ist.

Beweis

Nullrest oder Doppelrest

Ist eine Partialsumme 0 modulo $n$ , ist der Anfangsblock gefunden. Sonst liegen $n$ Partialsummen in nur $n-1$ Nichtnullklassen; zwei sind kongruent und ihre Differenz ist die gesuchte Blocksumme.

Achtung

Indizes sauber zurückübersetzen

Aus $S_i\equiv S_j$ mit $i<j$ folgt der Block $a_{i+1},\ldots,a_j$ . Das Glied $a_i$ gehört nicht mehr dazu.