Podzielność sumy elementów zbioru
-
Rafsaf
- Użytkownik
- Posty: 466
- Rejestracja: 19 lut 2017, o 11:04
- Płeć: Mężczyzna
- Lokalizacja: Podkarpacie/Wrocław
- Podziękował: 54 razy
- Pomógł: 80 razy
Podzielność sumy elementów zbioru
Zadanie sprowadza się do tego, aby pomyśleć o resztach z dzielenia liczb naturalnych przez \(\displaystyle{ 4}\)
Łatwo zauważyć, że są cztery możliwości:
\(\displaystyle{ r _{0} =0 \\
r _{1} =1 \\
r _{2} =2 \\
r _{3} =3 \\}\)
zauważ że wśród \(\displaystyle{ 5}\) jakichkolwiek liczb naturalnych można zawsze znaleźć \(\displaystyle{ 2}\) takie, że ich reszta z dzielenia przez \(\displaystyle{ 4}\) jest taka sama.
No czyli reszta z dzielenia przez \(\displaystyle{ 4}\) sumy tych dwóch pewnych liczb z \(\displaystyle{ 5}\) naturalnych może wynosić
\(\displaystyle{ 2 \cdot r _{0} =0 \\
2 \cdot r _{1} =2 \\
2 \cdot r _{2} =4=0 \\
2 \cdot r _{3} =6=4+2=2 \\}\)
No to ostatecznie,
A. Jeśli są co najmniej \(\displaystyle{ 4}\) liczby co dają taką samą resztę, to koniec.
B. Jeśli nie ma, to są co najmniej \(\displaystyle{ 2}\) pary takich, co dają taką samą resztę.
1 przypadek, to gdy suma tych dwóch par daje liczbę podzielną przez \(\displaystyle{ 4}\), wtedy koniec.
2 przypadek, to gdy suma tych dwóch par nie daje liczby podzielnej przez \(\displaystyle{ 4}\), wtedy daje zawsze resztę \(\displaystyle{ 2}\)(z tego wyżej)
Ale to nic, bo są jeszcze \(\displaystyle{ 3}\) inne liczby.
a) Jeśli choć \(\displaystyle{ 2}\) z tych \(\displaystyle{ 3}\) dają tą samą resztę, to spełniają przypadek \(\displaystyle{ 1}\).
b) Jeśli nie ma takich, to znaczy że są przynajmniej \(\displaystyle{ 3}\) takie same(w sensie reszty dają te same), co zaś prowadzi do tego suma tych \(\displaystyle{ 3}\) da resztę \(\displaystyle{ 0,1,2,3}\) a wśród pozostałych \(\displaystyle{ 4}\) liczb każda daje inną reszte, \(\displaystyle{ 1}\)lub \(\displaystyle{ 2}\)lub \(\displaystyle{ 3}\) lub \(\displaystyle{ 0}\), więc po dodaniu któraś na pewno spełni zadanie, bo będą \(\displaystyle{ 4}\) z resztą inną niż daje ta suma tych \(\displaystyle{ 3}\) liczb, więc jedna na pewno "dopełni" tą sumę. Jeśli nie znajdzie się taka, to wystąpi przypadek 1.
Nie jest to najszybsza droga, pewnie przyjdzie ktoś mądrzejszy i zrobi to szybciej, ale poprawna.
Edit: poprawa wiadomości.
Łatwo zauważyć, że są cztery możliwości:
\(\displaystyle{ r _{0} =0 \\
r _{1} =1 \\
r _{2} =2 \\
r _{3} =3 \\}\)
zauważ że wśród \(\displaystyle{ 5}\) jakichkolwiek liczb naturalnych można zawsze znaleźć \(\displaystyle{ 2}\) takie, że ich reszta z dzielenia przez \(\displaystyle{ 4}\) jest taka sama.
No czyli reszta z dzielenia przez \(\displaystyle{ 4}\) sumy tych dwóch pewnych liczb z \(\displaystyle{ 5}\) naturalnych może wynosić
\(\displaystyle{ 2 \cdot r _{0} =0 \\
2 \cdot r _{1} =2 \\
2 \cdot r _{2} =4=0 \\
2 \cdot r _{3} =6=4+2=2 \\}\)
No to ostatecznie,
A. Jeśli są co najmniej \(\displaystyle{ 4}\) liczby co dają taką samą resztę, to koniec.
B. Jeśli nie ma, to są co najmniej \(\displaystyle{ 2}\) pary takich, co dają taką samą resztę.
1 przypadek, to gdy suma tych dwóch par daje liczbę podzielną przez \(\displaystyle{ 4}\), wtedy koniec.
2 przypadek, to gdy suma tych dwóch par nie daje liczby podzielnej przez \(\displaystyle{ 4}\), wtedy daje zawsze resztę \(\displaystyle{ 2}\)(z tego wyżej)
Ale to nic, bo są jeszcze \(\displaystyle{ 3}\) inne liczby.
a) Jeśli choć \(\displaystyle{ 2}\) z tych \(\displaystyle{ 3}\) dają tą samą resztę, to spełniają przypadek \(\displaystyle{ 1}\).
b) Jeśli nie ma takich, to znaczy że są przynajmniej \(\displaystyle{ 3}\) takie same(w sensie reszty dają te same), co zaś prowadzi do tego suma tych \(\displaystyle{ 3}\) da resztę \(\displaystyle{ 0,1,2,3}\) a wśród pozostałych \(\displaystyle{ 4}\) liczb każda daje inną reszte, \(\displaystyle{ 1}\)lub \(\displaystyle{ 2}\)lub \(\displaystyle{ 3}\) lub \(\displaystyle{ 0}\), więc po dodaniu któraś na pewno spełni zadanie, bo będą \(\displaystyle{ 4}\) z resztą inną niż daje ta suma tych \(\displaystyle{ 3}\) liczb, więc jedna na pewno "dopełni" tą sumę. Jeśli nie znajdzie się taka, to wystąpi przypadek 1.
Nie jest to najszybsza droga, pewnie przyjdzie ktoś mądrzejszy i zrobi to szybciej, ale poprawna.
Edit: poprawa wiadomości.