C'è sempre un multiplo

[sqrt2]

Semplice ma elegante:

Dimostrare che presi n+1 numeri tra 1,2,..., 2n, ce ne sono due tali che uno divide l'altro.

[moebius]

Scrivo i miei $ n+1 $ numeri (che suppongo distinti, atrimenti è banale) come $ 2^{i_k} d_k $ con $ d_k $ dispari e $ i_k $ opportuni.
Consideriamo i $ d_k $. Quanti sono distinti? Al più $ n $.
Ma io ne ho presi $ n+1 $, quindi due sono uguali, diciamo $ d_1 $ e $ d_2 $. Necessariamente allora se $ i_1 < i_2 $, $ 2^{i_1} d_1 \mid 2^{i_2} d_2 $. Altrimenti $ 2^{i_2} d_2 \mid 2^{i_1} d_1 $.

[sqrt2]

perfetto