LI OM - I - Zadanie 11

Dana jest liczba całkowita dodatnia $ n $ oraz zbiór $ M $, złożony z $ n^2 + 1 $ różnych liczb całkowitych dodatnich i mający następującą własność: wśród $ n+1 $ liczb dowolnie wybranych ze zbioru $ M $ znajduje się para liczb, z których jedna dzieli się przez drugą. Udowodnić, że w zbiorze $ M $ istnieją różne liczby $ a_1,a_2,\ldots,a_{n+1} $ spełniające warunek: dla $ i = 1,2,\ldots,n $ liczba $ a_i $ dzieli się przez $ a_{i+1} $.

Rozwiązanie

Niech $ k \in M $. Oznaczmy przez $ d(k) $ największą liczbę naturalną $ \ell $, dla której istnieją różne liczby $ a_1 = k, a_2, a_3, \ldots, a_\ell $ spełniające warunek: dla $ i = 1,2,\ldots,\ell-1 $ liczba $ a_i $ dzieli się przez $ a_{i+1} $.

Przypuśćmy, że teza zadania nie jest spełniona. To oznacza, że dla dowolnego $ k \in M $ mamy $ 1 \leq d(k) \leq n $. Wówczas na mocy zasady szufladkowej, istnieją takie różne liczby $ k_1,k_2,\ldots,k_{n+1} $, że

\[<br />
d(k_1) = d(k_2) = \ldots = d(k_{n+1}) = m.<br />
\]

Z założeń zadania wynika, że dla pewnych różnych liczb $ s $, $ t $ zachodzi podzielność $ k_s|k_t $. Warunek $ d(k_s) = m $ oznacza, że istnieją liczby $ a_1 = k_s, a_2, \ldots, a_m $, spełniające: dla $ i = 1,2,\ldots,m-1 $ liczba $ a_i $ dzieli się przez $ a_{i+1} $. Jednak wtedy liczby $ b_1 = k_t, b_2 =a_1 = k_s , b_3 = a_2, \ldots , b_{m+1} =a_m $ spełniają warunek: dla $ i = 1,2,\ldots,m $ liczba $ b_i $ dzieli się przez $ b_{i+1} $. To dowodzi, że $ d(k_t) \geq m + 1 $ wbrew założeniu, że $ d(k_t) = m $.

Otrzymaliśmy sprzeczność.

Komentarze

Dodaj nową odpowiedź