Zadanie, które podobno sam Erdos zadawał młodym studentom jako swoistą inicjację.
Korzystając z zasady szufladkowej, udowodnij, że w każdym (n+1)-elementowym podzbiorze zbioru {1, 2,..., 2n} istnieją dwie liczby k i l tż. k dzieli l.
Zagadka Pala Erdosa (zasada szufladkowa)
-
- Użytkownik
- Posty: 384
- Rejestracja: 3 maja 2007, o 22:44
- Płeć: Kobieta
- Lokalizacja: Wrocław
- Pomógł: 92 razy
- fon_nojman
- Użytkownik
- Posty: 1599
- Rejestracja: 13 cze 2009, o 22:26
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 68 razy
- Pomógł: 255 razy
Zagadka Pala Erdosa (zasada szufladkowa)
Mam pytanko w dowodzie tego zadania korzysta się z tego, że każdą liczbę \(\displaystyle{ a\in \{ 1,2,\ldots,2n \}}\) da się zapisać w postaci \(\displaystyle{ 2^km,\ m}\) - nieparzyste. Jak to pokazać?
Jeżeli \(\displaystyle{ a}\) jest nieparzyste to wiadomo kładziemy \(\displaystyle{ k=0}\) i \(\displaystyle{ m=a}\), a jeżeli \(\displaystyle{ a}\) jest parzyste?
Jeżeli \(\displaystyle{ a}\) jest nieparzyste to wiadomo kładziemy \(\displaystyle{ k=0}\) i \(\displaystyle{ m=a}\), a jeżeli \(\displaystyle{ a}\) jest parzyste?
- Dasio11
- Moderator
- Posty: 10227
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Zagadka Pala Erdosa (zasada szufladkowa)
Rozkładamy na czynniki pierwsze, oddzielamy dwójki od reszty, całą resztę mnożymy. Np. \(\displaystyle{ 30=2 \cdot 3 \cdot 5=2^1 \cdot 15}\)
- fon_nojman
- Użytkownik
- Posty: 1599
- Rejestracja: 13 cze 2009, o 22:26
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 68 razy
- Pomógł: 255 razy
Zagadka Pala Erdosa (zasada szufladkowa)
Dzięki. Ciężko mi się myśli i wychodzą z tego jakieś głupie pytania.