Zagadka Pala Erdosa (zasada szufladkowa)

[Platonik]

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.

[sigma_algebra1]

57445.htm

[fon_nojman]

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?

[Dasio11]

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]

Dzięki. Ciężko mi się myśli i wychodzą z tego jakieś głupie pytania.