Shortlist 2021, A3

Domaine : Algèbre · Difficulté : ★★☆☆☆ · Proposé par : non indiqué

Concepts : Partie entière et majorations · Récurrence et constructions récursives · Sommes, télescopage et transformation d'Abel

Solution officielle : Shortlist officielle 2021 (avec solutions), p. 16 (page 16 du PDF)

Énoncé

Given a positive integer \(n\), find the smallest value of \(\left\lfloor \frac{a_1}{1} \right\rfloor + \left\lfloor \frac{a_2}{2} \right\rfloor + \cdots + \left\lfloor \frac{a_n}{n} \right\rfloor\) over all permutations \((a_1, a_2, \ldots, a_n)\) of \((1, 2, \ldots, n)\).

Indices : les idées clés

• Construction par cycles : découper \(1, \ldots, n\) en blocs \([2^j, 2^{j+1} - 1]\) et permuter circulairement chaque bloc ; chaque bloc ne contribue que \(1\).
• Partie entière : minorations du type \(\left\lfloor \frac{2^{k+1}}{m} \right\rfloor \geq \left\lfloor \frac{b + m}{m} \right\rfloor\), ou \(\left\lfloor \frac{a}{b} \right\rfloor \geq \log_2 \frac{a + 1}{b}\) (solution 3).
• Récurrence (solution 1) : un énoncé plus général sur \(2^k\) entiers distincts quelconques se démontre par récurrence sur \(k\).
• Intervalles « bons » et puissances de 2 (solution 2) : les intervalles \([i, a_i]\) avec \(a_i \geq i\) recouvrent \(\{1, \ldots, n\}\), et chacun paie au moins le nombre de puissances de 2 qu'il contient.
• Télescopage (solution 3) : \(\sum \left(\log_2(a_i + 1) - \log_2 i\right) = \log_2(n + 1)\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2021 (trois solutions ; les solutions 2 et 3 donnent d'autres preuves de la minoration).

Réponse. Le minimum vaut \(\lfloor \log_2 n \rfloor + 1\) : si \(2^k \leq n < 2^{k+1}\), le minimum est \(k + 1\).

Solution 1

Supposons \(2^k \leq n < 2^{k+1}\) avec \(k\) entier positif ou nul. On exhibe d'abord une permutation \((a_1, \ldots, a_n)\) telle que \(\left\lfloor \frac{a_1}{1} \right\rfloor + \cdots + \left\lfloor \frac{a_n}{n} \right\rfloor = k + 1\), puis on montre que cette somme vaut au moins \(k + 1\) pour toute permutation. La valeur minimale est donc \(k + 1\).

I. Construction. Considérons la permutation

\[\begin{aligned} &(a_1) = (1), \quad (a_2, a_3) = (3, 2), \quad (a_4, a_5, a_6, a_7) = (7, 4, 5, 6), \quad \ldots, \\ &(a_{2^{k-1}}, \ldots, a_{2^k - 1}) = (2^k - 1, 2^{k-1}, 2^{k-1} + 1, \ldots, 2^k - 2), \\ &(a_{2^k}, \ldots, a_n) = (n, 2^k, 2^k + 1, \ldots, n - 1). \end{aligned}\]

Elle est formée de \(k + 1\) cycles. Dans chaque cycle \((a_p, \ldots, a_q) = (q, p, p + 1, \ldots, q - 1)\), on a \(q < 2p\), donc

\[\sum_{i=p}^{q} \left\lfloor \frac{a_i}{i} \right\rfloor = \left\lfloor \frac{q}{p} \right\rfloor + \sum_{i=p+1}^{q} \left\lfloor \frac{i - 1}{i} \right\rfloor = 1.\]

La somme totale sur tous les cycles vaut exactement \(k + 1\).

II. Minoration. On démontre un énoncé plus général.

Affirmation. Si \(b_1, \ldots, b_{2^k}\) sont des entiers strictement positifs distincts, alors

\[\sum_{i=1}^{2^k} \left\lfloor \frac{b_i}{i} \right\rfloor \geq k + 1.\]

L'affirmation entraîne immédiatement

\[\sum_{i=1}^{n} \left\lfloor \frac{a_i}{i} \right\rfloor \geq \sum_{i=1}^{2^k} \left\lfloor \frac{a_i}{i} \right\rfloor \geq k + 1.\]

Preuve de l'affirmation. Par récurrence sur \(k\). Pour \(k = 0\), l'affirmation est triviale : \(b_1 \geq 1\).

Le livret écrit « pour \(k = 1\) » ; il s'agit du cas \(k = 0\) (un seul nombre \(b_1\)).

Supposons l'affirmation vraie pour un entier \(k \geq 0\) et considérons \(k + 1\).

S'il existe un indice \(j\) avec \(2^k < j \leq 2^{k+1}\) et \(b_j \geq j\), alors, par hypothèse de récurrence,

\[\sum_{i=1}^{2^{k+1}} \left\lfloor \frac{b_i}{i} \right\rfloor \geq \sum_{i=1}^{2^k} \left\lfloor \frac{b_i}{i} \right\rfloor + \left\lfloor \frac{b_j}{j} \right\rfloor \geq (k + 1) + 1,\]

et l'affirmation est vérifiée.

Sinon, \(b_j < j \leq 2^{k+1}\) pour tout \(2^k < j \leq 2^{k+1}\). Parmi les \(2^{k+1}\) nombres distincts \(b_1, \ldots, b_{2^{k+1}}\), l'un, disons \(b_m\), est au moins égal à \(2^{k+1}\) ; il figure nécessairement parmi \(b_1, \ldots, b_{2^k}\). Donc \(1 \leq m \leq 2^k\) et \(b_m \geq 2^{k+1}\).

Appliquons l'hypothèse de récurrence aux nombres

\[c_1 = b_1, \ldots, c_{m-1} = b_{m-1}, \quad c_m = b_{2^k + 1}, \quad c_{m+1} = b_{m+1}, \ldots, c_{2^k} = b_{2^k},\]

c'est-à-dire aux \(2^k\) premiers nombres, où l'on a remplacé \(b_m\) par \(b_{2^k + 1}\) (ils restent distincts). Comme \(b_{2^k + 1} \leq 2^k\) et \(m \leq 2^k\), la partie entière vérifie

\[\left\lfloor \frac{b_m}{m} \right\rfloor \geq \left\lfloor \frac{2^{k+1}}{m} \right\rfloor = \left\lfloor \frac{2^k + 2^k}{m} \right\rfloor \geq \left\lfloor \frac{b_{2^k + 1} + m}{m} \right\rfloor = \left\lfloor \frac{c_m}{m} \right\rfloor + 1.\]

Pour les autres indices \(i\), \(1 \leq i \leq 2^k\), \(i \neq m\), on a \(b_i = c_i\), donc

\[\sum_{i=1}^{2^{k+1}} \left\lfloor \frac{b_i}{i} \right\rfloor \geq \sum_{i=1}^{2^k} \left\lfloor \frac{b_i}{i} \right\rfloor \geq \sum_{i=1}^{2^k} \left\lfloor \frac{c_i}{i} \right\rfloor + 1 \geq (k + 1) + 1.\]

Cela démontre l'affirmation et achève la solution. \(\blacksquare\)

Solution 2

On donne une autre preuve de la minoration. Supposons encore \(2^k \leq n < 2^{k+1}\), et soit \(P = \{2^0, 2^1, \ldots, 2^k\}\) l'ensemble des puissances de 2 parmi \(1, 2, \ldots, n\). On dit qu'un entier \(i \in \{1, 2, \ldots, n\}\), ainsi que l'intervalle \([i, a_i]\), est bon si \(a_i \geq i\).

Lemme 1. Les bons intervalles recouvrent les entiers \(1, 2, \ldots, n\).

Preuve. Soit \(x \in \{1, 2, \ldots, n\}\) ; cherchons un bon intervalle \([i, a_i]\) contenant \(x\), c'est-à-dire avec \(i \leq x \leq a_i\). Considérons le cycle de la permutation qui contient \(x\), à savoir \((x, a_x, a_{a_x}, \ldots)\). Dans ce cycle, soit \(i\) le premier élément tel que \(a_i \geq x\) (il existe, car le prédécesseur de \(x\) dans le cycle a pour image \(x\)) ; alors \(i \leq x \leq a_i\) (si \(i \neq x\), \(i\) est l'image d'un élément précédent, image qui est \(< x\)). \(\square\)

Lemme 2. Si un bon intervalle \([i, a_i]\) contient \(p\) puissances de 2 distinctes, alors \(\left\lfloor \frac{a_i}{i} \right\rfloor \geq p\) ; formellement, \(\left\lfloor \frac{a_i}{i} \right\rfloor \geq \left|[i, a_i] \cap P\right|\).

Preuve. Le rapport entre la plus grande et la plus petite puissance de 2 de l'intervalle est au moins \(2^{p-1}\). Par l'inégalité de Bernoulli, \(\left\lfloor \frac{a_i}{i} \right\rfloor \geq 2^{p-1} \geq p\). (Si \(p = 0\), c'est évident.) \(\square\)

D'après le lemme 1, les bons intervalles recouvrent \(P\). Avec le lemme 2, on obtient

\[\sum_{i=1}^{n} \left\lfloor \frac{a_i}{i} \right\rfloor \geq \sum_{i \text{ bon}} \left\lfloor \frac{a_i}{i} \right\rfloor \geq \sum_{i \text{ bon}} \left|[i, a_i] \cap P\right| \geq |P| = k + 1. \qquad \blacksquare\]

Solution 3

Encore une autre preuve de la minoration, fondée sur l'inégalité suivante.

Lemme 3. Pour tous entiers \(a, b \geq 1\), on a \(\left\lfloor \frac{a}{b} \right\rfloor \geq \log_2 \frac{a + 1}{b}\).

Preuve. Soit \(t = \left\lfloor \frac{a}{b} \right\rfloor\) ; alors \(t \leq \frac{a}{b}\) et \(\frac{a + 1}{b} \leq t + 1\) (car \(a < b(t + 1)\), donc \(a + 1 \leq b(t + 1)\)). Avec l'inégalité \(2^t \geq t + 1\), on obtient

\[\left\lfloor \frac{a}{b} \right\rfloor = t \geq \log_2(t + 1) \geq \log_2 \frac{a + 1}{b}. \qquad \square\]

En appliquant le lemme à chaque terme,

\[\sum_{i=1}^{n} \left\lfloor \frac{a_i}{i} \right\rfloor \geq \sum_{i=1}^{n} \log_2 \frac{a_i + 1}{i} = \sum_{i=1}^{n} \log_2(a_i + 1) - \sum_{i=1}^{n} \log_2 i.\]

Les nombres \(a_1 + 1, \ldots, a_n + 1\) forment une permutation de \(2, 3, \ldots, n + 1\). Donc dans les deux dernières sommes tous les termes se compensent (télescopage), sauf \(\log_2(n + 1)\) dans la première et \(\log_2 1 = 0\) dans la seconde. Ainsi

\[\sum_{i=1}^{n} \left\lfloor \frac{a_i}{i} \right\rfloor \geq \log_2(n + 1) > k.\]

Le membre de gauche étant entier, il vaut au moins \(k + 1\). \(\blacksquare\)