Mam takie zadanko:
Doszedłem już do tego, że jeżeli każdy wyraz zbioru \(\displaystyle{ A}\), czyli \(\displaystyle{ a_{x}}\) podzielimy modulo przez \(\displaystyle{ n}\) to nasz ciąg \(\displaystyle{ A}\) będzie można zastąpić przez \(\displaystyle{ A'}\), którego elementami będą reszty z dzielenia, czyli \(\displaystyle{ \left\{ a_{1} \mod n, a_{2} \mod n, ..., a_{n} \mod n \right\} = \left\{r_{1}, r_{2}, ..., r_{n}\right\} = A'}\).Dany jest ciąg liczb naturalnych \(\displaystyle{ A = \left\{ a_{1}, a_{2}, ..., a_{n}\right\}}\) Pokaż, że istnieją takie i oraz j, \(\displaystyle{ i \le j}\), że suma \(\displaystyle{ a_{i} + a_{i+1} + ... + a_{j}}\) jest podzielna przez n.
Jeżeli w \(\displaystyle{ A'}\) znajdziemy \(\displaystyle{ 0}\), to teza z treści polecenia jest potwierdzona, bo \(\displaystyle{ 0}\) reprezentuje tą liczbę \(\displaystyle{ a_{x}}\) podzielną przez \(\displaystyle{ n}\) (gdzie \(\displaystyle{ x = i = j}\)).
Mam problem z dowodem, gdy w \(\displaystyle{ A'}\) nie będzie \(\displaystyle{ 0}\). Wydaje mi się, żeby zrobić to indukcyjnie, ale kompletnie nie wiem jak do tego podejść.
Mogę zacząć od przypadku, że każde \(\displaystyle{ r_{x} = 1}\), czyli suma wszystkich elementów z \(\displaystyle{ A'}\) będzie równa \(\displaystyle{ n}\) (czyli będzie też podzielna przez \(\displaystyle{ n}\)). Następnie mogę "zwijać" elementy ciągu, czyli wybrany element zastąpić większą liczbą i zacząć liczyć od wybranego miejsca, lecz nie wiem jak się za to zabrać.
Z góry dziękuję za pomoc