Partialsummen und teilbare Blöcke

Schubfachprinzip und teilbare Summen · Abschnitt 54 von 64

Intuition

Blocksumme als Differenz

Für $S_k=a_1+\cdots+a_k$ ist $S_j-S_i=a_{i+1}+\cdots+a_j$ . Eine Restkollision zweier Partialsummen erzeugt daher automatisch einen zusammenhängenden Block.

Gelöstes Beispiel

Folge 3, 1, 4, 1, 5

Modulo 5 gilt $S_1=3\equiv S_3=8$ . Also ist $S_3-S_1=1+4=5$ eine durch 5 teilbare Blocksumme.

Satz

Nichtleerer teilbarer Block

In jeder Folge von $n$ ganzen Zahlen gibt es einen nichtleeren zusammenhängenden Block, dessen Summe durch $n$ teilbar ist.

Checkliste

Zwei Erfolgsfälle

Eine Partialsumme hat Rest 0 → Anfangsblock verwenden.
Keine hat Rest 0 → $n$ Partialsummen liegen in $n-1$ nichtnulligen Restklassen; zwei Reste stimmen überein.