LI OM - I - Zadanie 11

Zawody matematyczne:

LI OM, 1999-2000

Etap:

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ść.