Shortlist 2023, A7

Domaine : Algèbre · Difficulté : ★★★★★ · Proposé par : China

Concepts : Partie entière et majorations · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2023 (avec solutions), p. 27 (page 29 du PDF)

Figures reprises du livret officiel de la Shortlist.

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

Let \(N\) be a positive integer. Prove that there exist three permutations \(a_1, a_2, \ldots, a_N\); \(b_1, b_2, \ldots, b_N\); and \(c_1, c_2, \ldots, c_N\) of \(1, 2, \ldots, N\) such that

\[\left|\sqrt{a_k} + \sqrt{b_k} + \sqrt{c_k} - 2\sqrt{N}\right| < 2023\]

for every \(k = 1, 2, \ldots, N\).

Indices : les idées clés

• Partie entière et majorations : on remplace \(\sqrt{1}, \ldots, \sqrt{N}\) par leurs arrondis entiers (\(1, 1, 2, 2, 2, 2, 3, \ldots\) : l'entier \(k\) apparaît \(2k\) fois), avec une erreur \(< 0{,}5\) chacun, puis on encadre soigneusement (solutions 1 et 2).
• Récurrence et constructions récursives (solutions 1 et 2) : la « moitié » \(T_m = \{1_{\times 1}, 2_{\times 2}, \ldots, m_{\times m}\}\) du multiensemble s'écrit \(T_{m-1} \sqcup \{m_{\times m}\}\) et \((T_{m-1} + 1) \sqcup \{1, \ldots, m\}\), ce qui permet de construire trois permutations de \(T_m\) de somme constante \(2m+1\).
• Insérer les nombres manquants (solution 1) : pour \(N\) quelconque, on décale de \(t\) les valeurs \(> \lfloor 4N/9 \rfloor\), ce qui change peu les racines carrées.
• Triangle équilatéral de points (solution 3) : en numérotant ligne par ligne depuis chacun des trois sommets, les numéros de ligne \(\ell_a, \ell_b, \ell_c\) d'un point ont une somme constante, comme la somme des distances aux côtés.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2023 (trois solutions et une remarque).

Solution 1

L'idée est d'approcher les nombres \(\sqrt{1}, \sqrt{2}, \ldots, \sqrt{N}\) par l'entier le plus proche, avec une erreur \(< 0{,}5\). On obtient la suite

\[1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, \ldots\]

Plus précisément, pour chaque \(k \geq 1\), on arrondit \(\sqrt{k^2 - k + 1}, \ldots, \sqrt{k^2 + k}\) à \(k\) : il y a \(2k\) copies de \(k\).

Étape 1 : le cas \(N = m(m+1)\). Les nombres \(\sqrt{1}, \ldots, \sqrt{N}\) sont alors approchés par les éléments du multiensemble \(\{1_{\times 2}, 2_{\times 4}, 3_{\times 6}, \ldots, m_{\times 2m}\}\). Notons \(T_m\) sa « moitié » :

\[T_m := \{1_{\times 1}, 2_{\times 2}, 3_{\times 3}, \ldots, m_{\times m}\}.\]

Montrons par récurrence qu'il existe trois permutations \((u_k)\), \((v_k)\), \((w_k)\) des éléments de \(T_m\) telles que \(u_k + v_k + w_k = 2m + 1\) pour \(k = 1, 2, \ldots, \frac{m(m+1)}{2}\).

Pour \(m = 1\) : \(1 + 1 + 1 = 3\). Pour \(m = 2\) : \((1, 2, 2) + (2, 1, 2) + (2, 2, 1) = (5, 5, 5)\). Supposons construites trois permutations \((u_k)\), \((v_k)\), \((w_k)\) de \(T_{m-1}\) avec \(u_k + v_k + w_k = 2m - 1\) pour \(k = 1, \ldots, \frac{m(m-1)}{2}\). On remarque que

\[T_m = T_{m-1} \sqcup \{m_{\times m}\} \quad \text{et} \quad T_m = (T_{m-1} + 1) \sqcup \{1, 2, \ldots, m\}, \tag{1}\]

où \(T_{m-1} + 1\) désigne le multiensemble obtenu en ajoutant \(1\) à chaque élément de \(T_{m-1}\). On construit des permutations \((u'_k)\), \((v'_k)\), \((w'_k)\) de \(T_m\) ainsi :

• pour \(k = 1, \ldots, \frac{m(m-1)}{2}\) : \(u'_k = u_k\), \(v'_k = v_k + 1\), \(w'_k = w_k + 1\) ;
• pour \(k = \frac{m(m-1)}{2} + r\) avec \(r = 1, \ldots, m\) : \(u'_k = m\), \(v'_k = r\), \(w'_k = m + 1 - r\).

D'après (1), ce sont bien trois permutations de \(T_m\), et \(u'_k + v'_k + w'_k = 2m + 1\) pour tout \(k = 1, \ldots, \frac{m(m+1)}{2}\). On peut visualiser la construction par la matrice \(3 \times \frac{m(m+1)}{2}\)

\[\begin{bmatrix} u_1 & \cdots & u_{m(m-1)/2} & m & \cdots & m \\ v_1 + 1 & \cdots & v_{m(m-1)/2} + 1 & 1 & \cdots & m \\ w_1 + 1 & \cdots & w_{m(m-1)/2} + 1 & m & \cdots & 1 \end{bmatrix},\]

dont les lignes sont les trois permutations et dont chaque colonne a pour somme \(2m + 1\).

En utilisant deux fois ces permutations de \(T_m\) (une fois pour chacune des deux « moitiés »), et en remplaçant chaque arrondi par le nombre \(j\) dont \(\sqrt{j}\) a été arrondi, on obtient, pour \(N = m^2 + m\), des permutations \((a_k)\), \((b_k)\), \((c_k)\) de \(1, \ldots, N\) telles que (chaque racine étant à moins de \(0{,}5\) de son arrondi)

\[2m + 1 - 1{,}5 < \sqrt{a_k} + \sqrt{b_k} + \sqrt{c_k} < 2m + 1 + 1{,}5. \tag{2}\]

Comme \(-1 < 2m - 2\sqrt{m^2 + m} < 0\) pour \(m > 0\), cela donne

\[\left| \sqrt{a_k} + \sqrt{b_k} + \sqrt{c_k} - 2\sqrt{N} \right| < 2{,}5 < 2023.\]

Étape 2 : le cas général. Soit \(m\) tel que \(m(m+1) \leq N < (m+1)(m+2)\). Écrivons \(N = m(m+1) + t\) avec \(t \in \{0, 1, \ldots, 2m+1\}\) et posons

\[L := \left\lfloor \frac{4}{9} N \right\rfloor.\]

On utilisera les inégalités

\[N > m^2, \quad N < (m+2)^2, \quad t \leq 2m + 1, \quad L + 1 > 4N/9, \quad L \leq 4N/9.\]

Comme à l'étape 1, on construit trois permutations \((a_k)\), \((b_k)\), \((c_k)\) de \(1, \ldots, m(m+1)\) vérifiant (2). On construit alors les permutations \((A_k)\), \((B_k)\), \((C_k)\) de \(1, \ldots, N\) :

• pour \(k = 1, \ldots, m(m+1)\) : \(A_k = a_k\) si \(a_k \leq L\), et \(A_k = a_k + t\) si \(a_k > L\) ;
• pour \(k = m(m+1) + r\) avec \(r = 1, \ldots, t\) : \(A_k = L + r\) ;

et de même pour \((B_k)\) et \((C_k)\).

Pour \(k \leq m(m+1)\), montrons que \(0 \leq \sqrt{A_k} - \sqrt{a_k} \leq 2\). La minoration est évidente. Si \(m \leq 1\), alors \(N \leq 5\) et \(\sqrt{A_k} - \sqrt{a_k} \leq \sqrt{5} - \sqrt{1} \leq 2\). Si \(m \geq 2\), alors (le cas non trivial est \(a_k \geq L + 1\), et \(\sqrt{L+1} > \frac{2}{3}\sqrt{N} > \frac{2}{3}m\))

\[\sqrt{A_k} - \sqrt{a_k} = \frac{A_k - a_k}{\sqrt{A_k} + \sqrt{a_k}} \leq \frac{t}{2\sqrt{L+1}} \leq \frac{2m + 1}{\frac{4}{3} m} \leq 2.\]

De même pour \((B_k)\) et \((C_k)\). Ainsi

\[2\sqrt{N} - 4{,}5 < 2m + 1 - 1{,}5 \leq \sqrt{A_k} + \sqrt{B_k} + \sqrt{C_k} \leq 2m + 1 + 1{,}5 + 6 < 2\sqrt{N} + 8{,}5.\]

Pour \(k = m^2 + m + 1, \ldots, m^2 + m + t\), on a

\[2\sqrt{N} < 3\sqrt{L + 1} \leq \sqrt{A_k} + \sqrt{B_k} + \sqrt{C_k} \leq 3\sqrt{L + t} \leq \sqrt{4N + 9t} < 2\sqrt{N} + 8{,}5.\]

En résumé, les trois permutations \((A_k)\), \((B_k)\), \((C_k)\) de \(1, \ldots, N\) vérifient

\[\left| \sqrt{A_k} + \sqrt{B_k} + \sqrt{C_k} - 2\sqrt{N} \right| < 8{,}5 < 2023\]

pour tout \(k = 1, \ldots, N\). \(\blacksquare\)

Solution 2

C'est une variante de la solution 1 qui traite l'étape 2 par récurrence. Pour un entier \(0 \leq n \leq m + 1\), on définit le multiensemble

\[T_{m,n} := \{1_{\times 1}, 2_{\times 2}, 3_{\times 3}, \ldots, m_{\times m}, (m+1)_{\times n}\}.\]

Autrement dit, \(T_{m,0} = T_m\), \(T_{m,n} = T_m \sqcup \{(m+1)_{\times n}\}\) et \(T_{m,m+1} = T_{m+1}\).

Affirmation. Il existe trois permutations \((u_k)\), \((v_k)\), \((w_k)\) de \(T_{m,n}\) telles que

\[\begin{cases} u_k + v_k + w_k = 2m + 1 & (n = 0), \\ u_k + v_k + w_k \in \{2m+1, 2m+2, 2m+3\} & (1 \leq n \leq m), \\ u_k + v_k + w_k = 2m + 3 & (n = m + 1). \end{cases}\]

Preuve. Par récurrence sur \(m\). Si \(n = 0\) ou \(n = m + 1\), on procède comme dans la solution 1. Si \(1 \leq n \leq m\), on remarque que

\[T_{m,n} = T_{m-1,n} \sqcup \{m_{\times(m-n)}, (m+1)_{\times n}\} = (T_{m-1,n} + 1) \sqcup \{1, 2, \ldots, m\}.\]

Par hypothèse de récurrence, il existe trois permutations \((u_k)\), \((v_k)\), \((w_k)\) de \(T_{m-1,n}\) avec \(u_k + v_k + w_k \in \{2m-1, 2m, 2m+1\}\) pour tout \(k\). On construit des permutations de \(T_{m,n}\) :

• pour \(k = 1, \ldots, \frac{m(m-1)}{2} + n\) : \(u'_k = u_k\), \(v'_k = v_k + 1\), \(w'_k = w_k + 1\) ;
• pour \(k = \frac{m(m-1)}{2} + n + r\) avec \(r = 1, \ldots, m\) : \(u'_k = m\) si \(1 \leq r \leq m - n\), \(u'_k = m + 1\) si \(m - n + 1 \leq r \leq m\), et \(v'_k = r\), \(w'_k = m + 1 - r\).

Ce sont trois permutations de \(T_{m,n}\), et \(u'_k + v'_k + w'_k \in \{2m+1, 2m+2, 2m+3\}\) pour tout \(k = 1, \ldots, \frac{m(m+1)}{2} + n\). Matriciellement :

\[\begin{bmatrix} u_1 & \cdots & u_{m(m-1)/2+n} & m & \cdots & m & m+1 & \cdots & m+1 \\ v_1 + 1 & \cdots & v_{m(m-1)/2+n} + 1 & 1 & \cdots & \cdots & \cdots & \cdots & m \\ w_1 + 1 & \cdots & w_{m(m-1)/2+n} + 1 & m & \cdots & \cdots & \cdots & \cdots & 1 \end{bmatrix}. \quad \square\]

Conclusion. En général, \(m(m+1) \leq N < (m+1)(m+2)\) pour un certain \(m \geq 0\) ; écrivons \(N = m(m+1) + t\) avec \(t \in \{0, 1, \ldots, 2m+1\}\). L'approximation de \(\{\sqrt{1}, \sqrt{2}, \ldots, \sqrt{N}\}\) par l'entier le plus proche (erreur \(< 0{,}5\)) donne le multiensemble

\[\{1_{\times 2}, 2_{\times 4}, \ldots, m_{\times 2m}, (m+1)_{\times t}\} = T_{m,n_1} \sqcup T_{m,n_2}, \quad n_1 = \lfloor t/2 \rfloor, \ n_2 = \lceil t/2 \rceil.\]

Comme \(0 \leq n_1 \leq n_2 \leq m + 1\), l'affirmation fournit des permutations \((a_k)\), \((b_k)\), \((c_k)\) de \(1, \ldots, N\) telles que

\[2m + 1 - 1{,}5 < \sqrt{a_k} + \sqrt{b_k} + \sqrt{c_k} < 2m + 3 + 1{,}5.\]

Comme \(m < \sqrt{N} < m + 2\), il vient

\[2\sqrt{N} - 4{,}5 < 2m + 1 - 1{,}5 < \sqrt{a_k} + \sqrt{b_k} + \sqrt{c_k} < 2m + 3 + 1{,}5 < 2\sqrt{N} + 4{,}5,\]

donc

\[\left| \sqrt{a_k} + \sqrt{b_k} + \sqrt{c_k} - 2\sqrt{N} \right| < 4{,}5 < 2023. \quad \blacksquare\]

Le livret écrit ici \(A_k, B_k, C_k\) dans la dernière inégalité ; il s'agit des permutations \(a_k, b_k, c_k\) construites juste avant.

Solution 3

Cette solution repose sur une intuition géométrique : le triangle équilatéral.

Étape 1 : le cas d'un nombre triangulaire \(N = \frac{m(m+1)}{2}\). On dispose \(N\) points en réseau triangulaire dans un triangle équilatéral \(ABC\) : la \(\ell\)-ième rangée (en partant de \(A\)) contient exactement \(\ell\) points, pour \(\ell = 1, \ldots, m\). On numérote les rangées de trois façons, une pour chaque sommet.

Chaque point \(P_k\) reçoit un triplet d'entiers \((a_k, b_k, c_k)\). La première coordonnée, ou \(A\)-coordonnée \(W_a(\bullet)\), s'obtient en numérotant les points \(1, 2, 3, \ldots\) à partir du point le plus proche de \(A\), rangée par rangée en descendant, et de gauche à droite dans chaque rangée. La \(B\)-coordonnée \(W_b(\bullet)\) s'obtient en faisant tourner cette numérotation de \(120^\circ\) dans le sens direct, et la \(C\)-coordonnée \(W_c(\bullet)\) par une rotation de \(240^\circ\).

Supposons que \(P\) soit dans la \(\ell_a\)-ième rangée vue de \(A\), la \(\ell_b\)-ième vue de \(B\), la \(\ell_c\)-ième vue de \(C\). Le nombre \(\ell_a\) est (à une constante près) proportionnel à la différence entre la hauteur issue de \(A\) et la distance de \(P\) au côté \(BC\). Comme dans un triangle équilatéral la somme des distances d'un point aux trois côtés ne dépend pas du point, on a

\[\ell_a + \ell_b + \ell_c = 2m + 1 = \sqrt{8N + 1}.\]

Les \(\ell\) premières rangées contiennent exactement \(1 + 2 + \cdots + \ell = \frac{\ell(\ell+1)}{2}\) points, donc

\[\frac{\ell_a(\ell_a - 1)}{2} + 1 \leq W_a(P) \leq \frac{\ell_a(\ell_a + 1)}{2},\]

et en particulier

\[\left(\ell_a - \frac{1}{2}\right)^2 < 2W_a(P) < \left(\ell_a + \frac{1}{2}\right)^2.\]

En sommant les trois inégalités analogues,

\[\left| \sqrt{2W_a(P)} + \sqrt{2W_b(P)} + \sqrt{2W_c(P)} - (\ell_a + \ell_b + \ell_c) \right| < \frac{3}{2},\]

et donc

\[\left| \sqrt{W_a(P)} + \sqrt{W_b(P)} + \sqrt{W_c(P)} - 2\sqrt{N + \frac{1}{8}} \right| < \frac{3}{2} \cdot \frac{1}{\sqrt{2}} = \frac{3\sqrt{2}}{4}.\]

Étape 2 : \(N\) quelconque. Il existe un entier \(m \geq 1\) tel que

\[\frac{m(m-1)}{2} + 1 \leq N \leq \frac{m(m+1)}{2}.\]

Écrivons \(N = \frac{m(m+1)}{2} - t\) avec \(t \in \{0, 1, \ldots, m-1\}\). On retire \(t\) points quelconques de la \(m\)-ième rangée (la rangée du bas, opposée à \(A\)). Il reste \(N\) points, auxquels on attribue les \(A\)-, \(B\)- et \(C\)-coordonnées comme avant (dans le même ordre, en sautant les points retirés, de sorte que les coordonnées forment exactement des permutations de \(1, \ldots, N\)).

Pour un point restant \(P\), situé dans les rangées \(\ell_a\), \(\ell_b\), \(\ell_c\) vues de \(A\), \(B\), \(C\), la \(A\)-coordonnée vérifie toujours

\[\frac{\ell_a(\ell_a - 1)}{2} + 1 \leq W_a(P) \leq \frac{\ell_a(\ell_a + 1)}{2}.\]

La \(B\)-coordonnée vérifie

\[\frac{(\ell_b - 1)(\ell_b - 2)}{2} + 1 \leq W_b(P) \leq \frac{\ell_b(\ell_b + 1)}{2},\]

car, vu de \(B\), on a retiré \(0\) ou \(1\) point de chaque rangée, si bien que les \(\ell_b - 1\) premières rangées contiennent encore au moins \(0 + 1 + \cdots + (\ell_b - 2) = \frac{(\ell_b - 1)(\ell_b - 2)}{2}\) points. De même pour \(W_c(P)\). On en déduit

\[\ell_a - \frac{1}{2} < \sqrt{2W_a(P)} < \ell_a + \frac{1}{2}, \qquad \ell_b - \frac{3}{2} < \sqrt{2W_b(P)} < \ell_b + \frac{1}{2}, \qquad \ell_c - \frac{3}{2} < \sqrt{2W_c(P)} < \ell_c + \frac{1}{2}.\]

Avec \(2m - 1 < 2\sqrt{2N} < 2m + 1\) et \(\ell_a + \ell_b + \ell_c = 2m + 1\), on obtient

\[2\sqrt{2N} - \frac{7}{2} < (2m+1) - \frac{7}{2} < \sqrt{2W_a(P)} + \sqrt{2W_b(P)} + \sqrt{2W_c(P)} < (2m+1) + \frac{3}{2} < 2\sqrt{2N} + \frac{7}{2}.\]

Par conséquent, pour chaque point \(P\),

\[\left| \sqrt{W_a(P)} + \sqrt{W_b(P)} + \sqrt{W_c(P)} - 2\sqrt{N} \right| < \frac{7}{2} \cdot \frac{1}{\sqrt{2}} < 2{,}5 < 2023.\]

(Le livret écrit ici « \(< 2013\) », coquille sans conséquence.)

On ordonne enfin les \(N\) points de façon arbitraire : les \(A\)-coordonnées donnent la permutation \(a_1, \ldots, a_N\), les \(B\)-coordonnées \(b_1, \ldots, b_N\) et les \(C\)-coordonnées \(c_1, \ldots, c_N\). Pour tout \(k = 1, \ldots, N\),

\[\left| \sqrt{a_k} + \sqrt{b_k} + \sqrt{c_k} - 2\sqrt{N} \right| < 2{,}5 < 2023. \quad \blacksquare\]

Remarques

Remarque 1 (version sans géométrie). On peut mener l'argument de la solution 3 avec des coordonnées barycentriques entières et l'ordre lexicographique. Pour \(N = \frac{m(m+1)}{2}\), on considère

\[X = \{(x, y, z) \in \mathbb{Z}^3 \mid 0 \leq x, y, z \leq m - 1,\ x + y + z = m - 1\},\]

muni de l'ordre lexicographique (\((x, y, z) > (x', y', z')\) si \(x > x'\), ou \(x = x'\) et \(y > y'\), ou \(x = x'\), \(y = y'\) et \(z > z'\)). Pour \(Q_k = (x_k, y_k, z_k)\), on définit \(W_a(Q_k)\) comme le rang de \((x_k, y_k, z_k)\) dans \(X\) (rangé par ordre décroissant), \(W_b(Q_k)\) comme le rang de \((y_k, z_k, x_k)\) dans \(X' = \{(y, z, x) \mid (x, y, z) \in X\}\), et \(W_c(Q_k)\) comme le rang de \((z_k, x_k, y_k)\) dans \(X'' = \{(z, x, y) \mid (x, y, z) \in X\}\). Le même argument s'applique alors, avec \(\ell_a = m - x_k\), \(\ell_b = m - y_k\), \(\ell_c = m - z_k\). (Le livret renvoie ici à « la solution 2 » ; il s'agit de la solution 3.)