Korzystając z zasady szufladkowej wykazać, że jeśli mamy zbiór liczb całkowitych liczący 2014 elementów, to istnieje niepusty podzbiór tego zbioru, taki że suma liczb będących elementami tego podzbioru jest podzielna przez 2014.
Nie rozczajam tej zasady szufladkowej na tyle, żeby korzystając z niej, wykazać cokolwiek... pomocy!
Zasada szufladkowa Dirichleta
- mol_ksiazkowy
- Użytkownik
- Posty: 11409
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
Zasada szufladkowa Dirichleta
wsk Jesli \(\displaystyle{ X =\{ a_1,...,a_n\}}\) to niech \(\displaystyle{ Y =\{ b_1,...,b_n\}}\) gdzie \(\displaystyle{ b_j =a_1+...+a_j}\) dla \(\displaystyle{ j \geq 1}\) , etcjeśli mamy zbiór liczb całkowitych liczący 2014 elementów, to istnieje niepusty podzbiór tego zbioru, taki że
-
- Użytkownik
- Posty: 103
- Rejestracja: 30 lis 2013, o 17:02
- Płeć: Kobieta
- Lokalizacja: Kraków
- Podziękował: 3 razy
- Pomógł: 3 razy
Zasada szufladkowa Dirichleta
Dzięki! Jednak wciąż nie wiem, jak to rozwiązać.
Po co mi tak zdefiniowany zbiór Y?
Wiem, że w zbiorze X są co najmniej dwa elementy, które przy dzieleniu przez 2013 dają tę samą resztę, tudzież że w zbiorze X są co najmniej 3 elementy, które przy dzieleniu przez 1007 dają tę samą resztę... i tylko tyle wiem i co gorsze, nie wiem, jak to wykorzystać....
A już zupełnie nie wiem, co zrobić ze zbiorem Y.-- 8 sty 2014, o 22:39 --Dzięki! Już wiem, o co chodzi.
Mamy dwa przypadki:
albo jakaś liczba b jest podzielna przez 2014, albo mamy 2013 możliwych reszt z dzielenia, co oznacza, ze przynajmniej dwie liczby dają tę samą resztę. Wówczas ich różnica jest podzielna przez 2014, a ich różnica jest i tak sumą wyjściowych liczb a:)
Po co mi tak zdefiniowany zbiór Y?
Wiem, że w zbiorze X są co najmniej dwa elementy, które przy dzieleniu przez 2013 dają tę samą resztę, tudzież że w zbiorze X są co najmniej 3 elementy, które przy dzieleniu przez 1007 dają tę samą resztę... i tylko tyle wiem i co gorsze, nie wiem, jak to wykorzystać....
A już zupełnie nie wiem, co zrobić ze zbiorem Y.-- 8 sty 2014, o 22:39 --Dzięki! Już wiem, o co chodzi.
Mamy dwa przypadki:
albo jakaś liczba b jest podzielna przez 2014, albo mamy 2013 możliwych reszt z dzielenia, co oznacza, ze przynajmniej dwie liczby dają tę samą resztę. Wówczas ich różnica jest podzielna przez 2014, a ich różnica jest i tak sumą wyjściowych liczb a:)