Zasada szufladkowa
-
Ruahyin
- Użytkownik
- Posty: 123
- Rejestracja: 25 kwie 2016, o 17:21
- Płeć: Kobieta
- Lokalizacja: Yakushima
- Podziękował: 80 razy
Zasada szufladkowa
Wykaż, że w dowolnym ciągu \(\displaystyle{ 2012}\) liczb naturalnych mozna wskazać pewną liczbę kolejnych wyrazów, których suma jest podzielną przez \(\displaystyle{ 2012}\).
-
bakala12
- Użytkownik
- Posty: 3035
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Zasada szufladkowa
Niech te liczby to: \(\displaystyle{ a_{1}, a_{2}, \dots a_{2012}}\)
Rozważ liczby:
\(\displaystyle{ b_{1}=a_{1} \\
b_{n}=\sum_{i=1}^{n} a_{i}}\)
Liczb \(\displaystyle{ b}\) jest 2012. Jeżeli któraś z nich dzieli się przez \(\displaystyle{ 2012}\) to mamy tezę. Załóżmy więc, że żadna z nich się nie dzieli. W taki razie każda z nich daje resztę ze zbioru \(\displaystyle{ \left\{ 1,2,\dots, 2011\right\}}\). Takich reszt jest \(\displaystyle{ 2011}\), a liczb \(\displaystyle{ 2012}\). Stąd z zasady szufladkowej Dirichleta pewne dwie reszty muszą być równe, powiedzmy, że \(\displaystyle{ b_{k} \equiv b_{l} \pmod{2012}}\) dla pewnych \(\displaystyle{ k>l}\). Stąd:
\(\displaystyle{ 2012|b_{k}-b_{l}}\), czyli
\(\displaystyle{ 2012|\sum_{i=l+1}^{k} a_{i}}\)
To kończy dowód.
Rozważ liczby:
\(\displaystyle{ b_{1}=a_{1} \\
b_{n}=\sum_{i=1}^{n} a_{i}}\)
Liczb \(\displaystyle{ b}\) jest 2012. Jeżeli któraś z nich dzieli się przez \(\displaystyle{ 2012}\) to mamy tezę. Załóżmy więc, że żadna z nich się nie dzieli. W taki razie każda z nich daje resztę ze zbioru \(\displaystyle{ \left\{ 1,2,\dots, 2011\right\}}\). Takich reszt jest \(\displaystyle{ 2011}\), a liczb \(\displaystyle{ 2012}\). Stąd z zasady szufladkowej Dirichleta pewne dwie reszty muszą być równe, powiedzmy, że \(\displaystyle{ b_{k} \equiv b_{l} \pmod{2012}}\) dla pewnych \(\displaystyle{ k>l}\). Stąd:
\(\displaystyle{ 2012|b_{k}-b_{l}}\), czyli
\(\displaystyle{ 2012|\sum_{i=l+1}^{k} a_{i}}\)
To kończy dowód.