Witam mam problem z rozwiązaniem zadania z olimpiady gimnazjalnej (niby studiuje).
Treść:
Wpisujemy w ciągu 13 dowolnych liczb całkowitych. Pokazać że można w tym ciągu wskazać kilka kolejnych liczb (jedną lub więcej) takich że ich suma dzieli się przez 13.
Zad z olimpiady. Ciekawostka. Trudne
-
sstanko
- Użytkownik
- Posty: 27
- Rejestracja: 10 lis 2012, o 12:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Pomógł: 5 razy
Zad z olimpiady. Ciekawostka. Trudne
Zasada szufladkowa Dirichleta.
Dowód nie wprost.
Załóżmy że w tym ciągu nie możemy wskazać takie liczby.
Rozważmy sumy \(\displaystyle{ b_1=a_1, b_2=a_1+a_2, b_3=a_1+a_2+a_3, ... , b_{13}=a_1+a_2+...+a_{13}}\)
Z założenia każda z tych sum nie jest podzielna przez 13. A wiec jest 12 możliwych reszt względem podzielności przez 13. W takim razie spośród tych sum są dwie które dają tą sama resztę, tzn różnica jest podzielna przez 13. Np \(\displaystyle{ b_8}\) i \(\displaystyle{ b_4}\). Ale wtedy \(\displaystyle{ a_5+a_6+a_7+a_8=b_8 - b_4}\) jest podzielne przez 13. Sprzeczność.
Dowód nie wprost.
Załóżmy że w tym ciągu nie możemy wskazać takie liczby.
Rozważmy sumy \(\displaystyle{ b_1=a_1, b_2=a_1+a_2, b_3=a_1+a_2+a_3, ... , b_{13}=a_1+a_2+...+a_{13}}\)
Z założenia każda z tych sum nie jest podzielna przez 13. A wiec jest 12 możliwych reszt względem podzielności przez 13. W takim razie spośród tych sum są dwie które dają tą sama resztę, tzn różnica jest podzielna przez 13. Np \(\displaystyle{ b_8}\) i \(\displaystyle{ b_4}\). Ale wtedy \(\displaystyle{ a_5+a_6+a_7+a_8=b_8 - b_4}\) jest podzielne przez 13. Sprzeczność.