Liczby naturalne
-
olgalagowska
- Użytkownik
- Posty: 88
- Rejestracja: 28 paź 2010, o 13:05
- Płeć: Kobieta
- Podziękował: 8 razy
Liczby naturalne
Pokaz, ze w jakimkolwiek zbiorze 172 liczb naturalnych musi byc para liczb, ktorej roznica jest podzielna przez 171. Czy rezultat jest prawdziwy jesli zamienimy "roznice" na "sume"?
-
JakimPL
- Użytkownik
- Posty: 2401
- Rejestracja: 25 mar 2010, o 12:15
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 43 razy
- Pomógł: 459 razy
Liczby naturalne
Dowód trochę poprzez machanie rękami, ale myślę, że się połapiesz .
Chcemy skonstruować taki zbiór \(\displaystyle{ 172}\) różnych liczb, dla których nie istnieje taka para liczb z tego zbioru, że ich różnica jest podzielna przez \(\displaystyle{ 171}\). Zadanie nie mówi o parach różnych liczb, ale oczywistym jest, iż tylko takie mogą być rozważane. Wybierzmy dowolną liczbę \(\displaystyle{ a_1}\). Wtedy, aby spełnione w dalszym ciągu były warunki, liczba \(\displaystyle{ a_2}\) musi spełniać warunek:
\(\displaystyle{ a_1\not\equiv a_2 \pmod{171}}\)
co jest równoważne z tym, że ich różnica nie dzieli się bez reszty przez \(\displaystyle{ 171}\). Możliwych takich liczb jest jednak tylko \(\displaystyle{ 170}\)*, gdyż każda różnica \(\displaystyle{ a_i - a_1}\) musi mieć inną resztę z dzielenia przez \(\displaystyle{ 171}\) dla \(\displaystyle{ i\in\{2,3,\ldots,171\}}\). Gdy dodamy do tego zbioru chociaż jedną liczbę, to zawsze będzie istniało takie \(\displaystyle{ i\in\{1,2,\ldots,171\}}\), dla których \(\displaystyle{ a_i\equiv a_{172} \pmod{171}}\), gdyż wszystkie możliwe reszty z dzielenia zostały wyczerpane. Sprzeczność.
* - innymi słowy: jeżeli liczby nie są przystające:
\(\displaystyle{ a_1\not\equiv a_2 \pmod{171}}\)
to musi istnieć taka liczba \(\displaystyle{ n}\) z przedziału \(\displaystyle{ 1\ldots 170}\), że \(\displaystyle{ a_2+n}\) przystaje do \(\displaystyle{ a_1}\), tj.:
\(\displaystyle{ \exists_{n\in\{1,2,\ldots,170\}}\ a_1\equiv a_2+n \pmod{171}}\)
Chcemy skonstruować taki zbiór \(\displaystyle{ 172}\) różnych liczb, dla których nie istnieje taka para liczb z tego zbioru, że ich różnica jest podzielna przez \(\displaystyle{ 171}\). Zadanie nie mówi o parach różnych liczb, ale oczywistym jest, iż tylko takie mogą być rozważane. Wybierzmy dowolną liczbę \(\displaystyle{ a_1}\). Wtedy, aby spełnione w dalszym ciągu były warunki, liczba \(\displaystyle{ a_2}\) musi spełniać warunek:
\(\displaystyle{ a_1\not\equiv a_2 \pmod{171}}\)
co jest równoważne z tym, że ich różnica nie dzieli się bez reszty przez \(\displaystyle{ 171}\). Możliwych takich liczb jest jednak tylko \(\displaystyle{ 170}\)*, gdyż każda różnica \(\displaystyle{ a_i - a_1}\) musi mieć inną resztę z dzielenia przez \(\displaystyle{ 171}\) dla \(\displaystyle{ i\in\{2,3,\ldots,171\}}\). Gdy dodamy do tego zbioru chociaż jedną liczbę, to zawsze będzie istniało takie \(\displaystyle{ i\in\{1,2,\ldots,171\}}\), dla których \(\displaystyle{ a_i\equiv a_{172} \pmod{171}}\), gdyż wszystkie możliwe reszty z dzielenia zostały wyczerpane. Sprzeczność.
* - innymi słowy: jeżeli liczby nie są przystające:
\(\displaystyle{ a_1\not\equiv a_2 \pmod{171}}\)
to musi istnieć taka liczba \(\displaystyle{ n}\) z przedziału \(\displaystyle{ 1\ldots 170}\), że \(\displaystyle{ a_2+n}\) przystaje do \(\displaystyle{ a_1}\), tj.:
\(\displaystyle{ \exists_{n\in\{1,2,\ldots,170\}}\ a_1\equiv a_2+n \pmod{171}}\)