0 Daumen
545 Aufrufe

Seien n∈ℕ und a1,a2,...,an∈ℕ. Zeigen Sie, dass die Indizes j,k mit j≤k existieren, sodass n|aj+...+ak.


Problem/Ansatz: also für mich klingt es zwar logisch, jedoch habe ich keinen wirklichen Ansatz, wie ich die Aufgabe beweisen soll. Die erste Schlussfolgerung wäre das Schubfachprinzip, da wir das momentan behandeln...

Ich wäre sehr dankbar für Hilfe.

Avatar von

1 Antwort

0 Daumen


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

Avatar von 48 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community