[MIX] próbny II etap (1)

[qjon]

Zad 1
Rozważmy sumy:
\(\displaystyle{ S_{1}=a_{1}}\)
\(\displaystyle{ S_{2}=a_{1}+a_{2}}\)
...
\(\displaystyle{ S_{n}=a_{1}+a_{2}+...+a_{n}}\)

Jeśli pewna z nich daje resztę \(\displaystyle{ 0}\) przy dzieleniu przez \(\displaystyle{ n}\) to fajnie. Jeśli żadna nie daje, to z zasady szufladkowej istnieją takie \(\displaystyle{ S_{i}, S_{j}}\) gdzie \(\displaystyle{ i<j}\), które dają tę samą resztę z dzielenia przez \(\displaystyle{ n}\). Wtedy \(\displaystyle{ S_{j}-S_{i}}\) jest podzielne przez \(\displaystyle{ n}\).

Istnieje więc podciąg, którego suma jest podzielna przez \(\displaystyle{ n}\), ale suma dowolnego podciągu jest większa od \(\displaystyle{ 0}\) i mniejsza od \(\displaystyle{ 2n}\), więc suma wyrazów tego podciągu jest równa \(\displaystyle{ n}\).