Mam problem z zadaniem, nie wiem jak je rozwiązać. Muszę skorzystać z ZSD:
Udowodnij, że dla dowolnej liczby naturalnej istnieje taka jej wielokrotność, którą można zapisać w systemie dziesiętnym używając wyłącznie cyfr 1 i 0.
Zasada szufladkowa Dirichletta
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: Zasada szufladkowa Dirichletta
Stare:
ustalmy dowolne \(\displaystyle{ n\in \NN^+}\) i rozpatrzmy reszty z dzielenia przez \(\displaystyle{ n}\) liczb:
\(\displaystyle{ 1\\11\\111\\\ldots\\\overbrace{11\ldots 1}^{n+1 \text{ jedynek }}}\)
Tych liczb jest \(\displaystyle{ n+1}\), a reszt z dzielenia przez \(\displaystyle{ n}\) jest \(\displaystyle{ n}\), więc z Dirichleta są takie liczby spośród powyższych, które dają tę samą resztę z dzielenia przez \(\displaystyle{ n}\). Odejmijmy mniejszą z tych liczb od większej, a uzyskamy żądaną wielokrotność \(\displaystyle{ n}\).
ustalmy dowolne \(\displaystyle{ n\in \NN^+}\) i rozpatrzmy reszty z dzielenia przez \(\displaystyle{ n}\) liczb:
\(\displaystyle{ 1\\11\\111\\\ldots\\\overbrace{11\ldots 1}^{n+1 \text{ jedynek }}}\)
Tych liczb jest \(\displaystyle{ n+1}\), a reszt z dzielenia przez \(\displaystyle{ n}\) jest \(\displaystyle{ n}\), więc z Dirichleta są takie liczby spośród powyższych, które dają tę samą resztę z dzielenia przez \(\displaystyle{ n}\). Odejmijmy mniejszą z tych liczb od większej, a uzyskamy żądaną wielokrotność \(\displaystyle{ n}\).