XXXII - I - Zadanie 6

Dane są liczby $ a_1\geq a_2 \geq \ldots \geq a_n \geq 0 $ spełniające warunek $ \sum_{i=1}^n a_i = 1 $. Udowodnić, że istnieją liczby całkowite $ k_1\geq k_2 \geq \ldots \geq k_n \geq 0 $ takie, że

\[<br /> \sum_{i=1}^n k_i = n \quad \text{ i } \quad \frac{k_j}{n}\leq 2a_j \quad \text{ dla } j=1,2,\ldots, n.<br /> \]

Rozwiązanie

Niech $ [x] $ będzie największą liczbą całkowitą nie większą od $ x $.

Przyjmijmy $ \widetilde{k_j} = [2na_j] $. Liczby $ \widetilde{k_j} $ spełniają warunek $ \widetilde{k_1} \geq \widetilde{k_2} \geq \ldots \geq \widetilde{k_n} \geq 0 $, a ponadto $ 2na_j-1 < \widetilde{k_j} \leq 2na_j $, więc $ 2a_j - \frac{1}{n} < \frac{\widetilde{k_j}}{n} \leq 2a_j $ i wobec tego

\[<br /> \sum_{j=1}^n \frac{\widetilde{k_j}}{n} ><br /> \sum_{j=1}^n \left( 2a_j - \frac{1}{n} \right) =<br /> 2 \cdot \sum_{j=1}^n a_j - \sum_{j=1}^n \frac{1}{n} = 2-1=1.<br /> \]

Wynika stąd, że $ \sum_{j=1}^n \widetilde{k_j} > n $. Określimy teraz liczby $ k_j $ odejmując od $ \widetilde{k_j} $ odpowiednio dobrane liczby całkowite nieujemne. Niech $ d_n $ będzie maksymalną liczbą całkowitą nieujemną, dla której

\[<br /> (1) \qquad \widetilde{k_n}-d_n \geq 0,<br /> \]
\[<br /> (2) \qquad \sum_{j=1}^n \widetilde{k_j} -d_n \geq n.<br /> \]

Przyjmujemy $ k_n = \widetilde{k_n}-d_n $. Oczywiście $ \frac{k_n}{n} \leq 2a_n $. Następnie określamy $ d_{n-1} $ jako maksymalną liczbę całkowitą nieujemną, dla której

\[<br /> (1) \qquad \widetilde{k_{n-1}} - d_{n-1} \geq 0,<br /> \]
\[<br /> (2) \qquad \sum_{j=1}^n \widetilde{k_j} -d_n - d_{n-1} \geq n.<br /> \]

Przyjmujemy $ k_{n-1} = \widetilde{k_{n-1}}-d_{n-1} $ i tak dalej określamy $ d_j $ jako maksymalną liczbę całkowitą nieujemną, dla której

\[<br /> (1) \qquad \widetilde{k_j}-d_j \geq 0,<br /> \]
\[<br /> (2) \qquad \sum_{i=1}^n \widetilde{k_i} - \sum_{i=j}^n d_i \geq n<br /> \]

i przyjmujemy $ k_j = \widetilde{k_j} -d_j $.

Oczywiście jest przy tym $ \frac{k_j}{n} \leq 2a_j $ dla $ j = 1,2,\ldots,n $ oraz $ \sum_{j=1}^n k_j = n $, gdyż w przeciwnym razie byłoby $ \sum_{j=1}^n k_j > n $, a to oznaczałoby, że co najmniej jeden składnik tej sumy można zmniejszyć o $ 1 $ zachowując warunki zadania, wbrew temu, że na każdym kroku odejmowaliśmy maksymalne możliwe $ d_j $.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź