0 Daumen
1k Aufrufe

Es seien a1, . . . , an ganzen Zahlen, dann gibt es eine ”aufeinanderfolgende Summe” ak+ak+1+ak+2+. . .+ak+m welche durch n teilbar ist. 


Ich soll hier mit dem Schubfachprinzip argumentieren, jedoch erschließt sich mir nicht, wie ich das auf die Aufgabe anwenden kann.

Mein einziger Ansatz: Es gibt 2 Fächer, für n gerade und n ungerade


:)

Avatar von

1 Antwort

0 Daumen

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.

Avatar von 48 k

Bist Du sicher, das Du \( s_m -a_1 \) meinst und nicht die Differenz zweier Summen mit gleichem Rest bei Division durch \( n \)?

Hallo ullim,

Danke für den Hinweis. Ja - natürlich meine ich die Differenz der Summen. Ich korrigiere das.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community