XXXII - I - Zadanie 6

Zawody matematyczne:

XXXII OM, 1980-1981

Etap:

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

$ \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. $

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

$ \sum_{j=1}^n \frac{\widetilde{k_j}}{n} > \sum_{j=1}^n \left( 2a_j - \frac{1}{n} \right) = 2 \cdot \sum_{j=1}^n a_j - \sum_{j=1}^n \frac{1}{n} = 2-1=1. $

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

$ (1) \qquad \widetilde{k_n}-d_n \geq 0, $

$ (2) \qquad \sum_{j=1}^n \widetilde{k_j} -d_n \geq n. $

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

$ (1) \qquad \widetilde{k_{n-1}} - d_{n-1} \geq 0, $

$ (2) \qquad \sum_{j=1}^n \widetilde{k_j} -d_n - d_{n-1} \geq n. $

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

$ (1) \qquad \widetilde{k_j}-d_j \geq 0, $

$ (2) \qquad \sum_{i=1}^n \widetilde{k_i} - \sum_{i=j}^n d_i \geq n $

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$ .