Shortlist 2007, C1

Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Serbia

Concepts : Principe des tiroirs · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2007 (avec solutions), p. 25 (page 26 du PDF)

Énoncé

Let \(n > 1\) be an integer. Find all sequences \(a_1, a_2, \ldots, a_{n^2+n}\) satisfying the following conditions:

(a) \(a_i \in \{0, 1\}\) for all \(1 \leq i \leq n^2 + n\);

(b) \(a_{i+1} + a_{i+2} + \cdots + a_{i+n} < a_{i+n+1} + a_{i+n+2} + \cdots + a_{i+2n}\) for all \(0 \leq i \leq n^2 - n\).

Indices : les idées clés

• Sommes de blocs : avec \(S(k, l] = a_{k+1} + \cdots + a_l\), la chaîne \(0 \leq S(0, n] < S(n, 2n] < \cdots < S(n^2, n^2 + n] \leq n\) contient \(n + 1\) entiers distincts de \([0, n]\), donc \(S(vn, (v + 1)n] = v\) (tiroirs).
• Même argument décalé : pour chaque décalage \(u\), les sommes \(S(u + tn, u + (t + 1)n]\) sont \(n\) valeurs distinctes de \(\{0, \ldots, n\}\) ; on détermine la valeur manquante.
• Récurrence sur les blocs : le \(v\)-ième bloc est formé de \(n - v\) zéros suivis de \(v\) uns.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2007 (deux solutions).

Réponse : la suite est unique. Elle est définie par

\[a_{u+vn} = \begin{cases} 0, & u + v \leq n, \\ 1, & u + v \geq n + 1, \end{cases} \qquad \text{pour tous } 1 \leq u \leq n \text{ et } 0 \leq v \leq n. \tag{1}\]

Les termes se regroupent en blocs de longueur \(n\) : \((0 \ldots 0)\), \((0 \ldots 0\,1)\), \((0 \ldots 0\,1\,1)\), …, \((0 \ldots 0\,\underbrace{1 \ldots 1}_{v})\), …, \((0\,1 \ldots 1)\), \((1 \ldots 1)\).

Solution 1

Considérons une suite \((a_i)\) vérifiant les conditions. Pour des entiers quelconques \(0 \leq k \leq l \leq n^2 + n\), notons \(S(k, l] = a_{k+1} + \cdots + a_l\). (Si \(k = l\), alors \(S(k, l] = 0\).) La condition (b) se réécrit \(S(i, i + n] < S(i + n, i + 2n]\) pour tout \(0 \leq i \leq n^2 - n\). Remarquons que, pour \(0 \leq k \leq l \leq m \leq n^2 + n\), on a \(S(k, m] = S(k, l] + S(l, m]\).

D'après la condition (b),

\[0 \leq S(0, n] < S(n, 2n] < \cdots < S(n^2, n^2 + n] \leq n.\]

On n'a que \(n + 1\) entiers distincts dans l'intervalle \([0, n]\) ; donc

\[S(vn, (v + 1)n] = v \qquad \text{pour tout } 0 \leq v \leq n. \tag{2}\]

En particulier, \(S(0, n] = 0\) et \(S(n^2, n^2 + n] = n\), donc

\[a_1 = a_2 = \cdots = a_n = 0, \tag{3}\]

\[a_{n^2+1} = a_{n^2+2} = \cdots = a_{n^2+n} = 1. \tag{4}\]

Découpons la suite \((a_i)\) en \(n + 1\) blocs de \(n\) termes consécutifs chacun, numérotés de \(0\) à \(n\). Montrons par récurrence sur \(v\) que le \(v\)-ième bloc est de la forme \((0 \ldots 0\,1 \ldots 1)\), avec \(n - v\) zéros suivis de \(v\) uns. Le cas de base \(v = 0\) est donné par (3).

Considérons le \(v\)-ième bloc pour \(v > 0\). D'après (2), il contient des « uns ». Soit le premier « un » de ce bloc à la \(u\)-ième position (c'est-à-dire \(a_{u+vn} = 1\)). D'après l'hypothèse de récurrence, les blocs numéros \(v - 1\) et \(v\) de \((a_i)\) sont de la forme

\[(\underbrace{0 \ldots 0}_{n-v+1}\,\underbrace{1 \ldots 1}_{v-1})\,(\underbrace{0 \ldots 0}_{u-1}\,1 * \ldots *),\]

où chaque étoile peut être un chiffre binaire quelconque. Remarquons que \(u \leq n - v + 1\), puisque la somme de ce bloc vaut \(v\). Alors le fragment de longueur \(n\) formé des \(n - u\) derniers termes du bloc \(v - 1\) et des \(u\) premiers termes du bloc \(v\) contient exactement \((v - 1) + 1\) uns, c'est-à-dire \(S(u + (v - 1)n, u + vn] = v\). Donc

\[v = S(u + (v - 1)n, u + vn] < S(u + vn, u + (v + 1)n] < \cdots < S(u + (n - 1)n, u + n^2] \leq n ;\]

on a \(n - v + 1\) entiers distincts dans l'intervalle \([v, n]\), donc \(S(u + (t - 1)n, u + tn] = t\) pour tout \(t = v, \ldots, n\).

La fin de la suite \((a_i)\) se présente donc ainsi : à partir de la position \(u + (v - 1)n\), des fragments consécutifs de \(n\) termes de sommes \(v, v + 1, \ldots, n\), le dernier fragment se terminant par les \(n - u\) uns du dernier bloc. En calculant de deux façons la somme de tous ces chiffres, on obtient \(n - u = v - 1\), soit \(u = n - v + 1\). Donc les \(n - v\) premiers termes du \(v\)-ième bloc sont des zéros, et les \(v\) termes suivants sont des uns, à cause de la somme de tous les termes de ce bloc. L'affirmation est prouvée.

Il reste à vérifier que la suite obtenue vérifie la condition. Remarquons que \(a_i \leq a_{i+n}\) pour tout \(1 \leq i \leq n^2\). De plus, si \(1 \leq u \leq n\) et \(0 \leq v \leq n - 1\), alors \(a_{u+vn} < a_{u+vn+n}\) exactement quand \(u + v = n\). Dans ce cas, \(u + vn = n + v(n - 1)\).

Considérons maintenant un indice quelconque \(0 \leq i \leq n^2 - n\). Il existe évidemment un entier \(v\) tel que \(n + v(n - 1) \in [i + 1, i + n]\). En appliquant les inégalités ci-dessus, on obtient que la condition (b) est vérifiée. \(\blacksquare\)

Solution 2

Comme dans la solution 1, on introduit la notation \(S(k, l]\) et l'on obtient de même (2), (3) et (4). La somme de tous les termes de la suite se calcule ainsi :

\[S(0, n^2 + n] = S(0, n] + S(n, 2n] + \cdots + S(n^2, n^2 + n] = 0 + 1 + \cdots + n.\]

Pour un entier quelconque \(0 \leq u \leq n\), considérons les nombres

\[S(u, u + n] < S(u + n, u + 2n] < \cdots < S(u + (n - 1)n, u + n^2]. \tag{5}\]

Ce sont \(n\) entiers distincts parmi les \(n + 1\) valeurs possibles \(0, 1, 2, \ldots, n\). Notons \(m\) la valeur « manquante », qui n'est pas dans la liste. Déterminons \(m\) grâce à \(S(0, n^2 + n]\). Écrivons cette somme

\[S(0, n^2 + n] = S(0, u] + S(u, u + n] + S(u + n, u + 2n] + \cdots + S(u + (n - 1)n, u + n^2] + S(u + n^2, n^2 + n].\]

Comme \(a_1 = a_2 = \cdots = a_u = 0\) et \(a_{u+n^2+1} = \cdots = a_{n^2+n} = 1\), on a \(S(0, u] = 0\) et \(S(u + n^2, n + n^2] = n - u\). Alors

\[0 + 1 + \cdots + n = S(0, n^2 + n] = 0 + \big((0 + 1 + \cdots + n) - m\big) + (n - u),\]

donc \(m = n - u\). Les nombres de la liste (5) sont donc \(0, 1, \ldots, n - u - 1\) et \(n - u + 1, \ldots, n\) respectivement ; par conséquent

\[S(u + vn, u + (v + 1)n] = \begin{cases} v, & v \leq n - u - 1, \\ v + 1, & v \geq n - u, \end{cases} \qquad \text{pour tous } 0 \leq u \leq n, \ 0 \leq v \leq n - 1. \tag{6}\]

Les conditions (6), avec (3), forment un système d'équations linéaires en les inconnues \(a_i\). Résolvons ce système et montrons que la solution est unique et vérifie les conditions (a) et (b).

Remarquons d'abord que toute solution du système (3), (6) vérifie la condition (b). Par construction, les équations (6) impliquent immédiatement (5). D'autre part, toutes les inégalités de la condition (b) figurent dans la chaîne (5) pour une certaine valeur de \(u\).

Remarquons ensuite que le système (3), (6) est redondant. Les nombres \(S(kn, (k + 1)n]\), où \(1 \leq k \leq n - 1\), apparaissent deux fois dans (6). Pour \(u = 0\) et \(v = k\), on a \(v \leq n - u - 1\), et (6) donne \(S(kn, (k + 1)n] = v = k\). Pour \(u = n\) et \(v = k - 1\), on a \(v \geq n - u\) et l'on obtient la même valeur, \(S(kn, (k + 1)n] = v + 1 = k\). En supprimant une équation de chaque paire redondante, on peut faire en sorte que chaque somme \(S(k, k + n]\) apparaisse exactement une fois au membre de gauche de (6).

À partir de (3) et (6), la suite \((a_i)\) se reconstruit par récurrence :

\[a_1 = a_2 = \cdots = a_{n-1} = 0, \qquad a_{k+n} = S(k, k + n] - (a_{k+1} + a_{k+2} + \cdots + a_{k+n-1}) \quad (0 \leq k \leq n^2),\]

en prenant les valeurs de \(S(k, k + n]\) dans (6). Cela signifie d'abord que notre système a au plus une solution. Réciproquement, la suite construite vérifie évidemment toutes les équations (3), (6) (la seule équation manquante est \(a_n = 0\), qui découle de \(S(0, n] = 0\)). Elle vérifie donc la condition (b), et il ne reste qu'à vérifier la condition (a).

Pour des entiers quelconques \(1 \leq u, t \leq n\), on obtient

\[a_{u+tn} - a_{u+(t-1)n} = S(u + (t - 1)n, u + tn] - S((u - 1) + (t - 1)n, (u - 1) + tn] = \begin{cases} (t - 1) - (t - 1) = 0, & t \leq n - u, \\ t - (t - 1) = 1, & t = n - u + 1, \\ t - t = 0, & t \geq n - u + 2. \end{cases}\]

Comme \(a_u = 0\), on a

\[a_{u+vn} = a_{u+vn} - a_u = \sum_{t=1}^{v}(a_{u+tn} - a_{u+(t-1)n})\]

pour tous \(1 \leq u, v \leq n\). Si \(v < n - u + 1\), tous les termes du membre de droite sont nuls. Si \(v \geq n - u + 1\), la variable \(t\) prend une fois la valeur \(n - u + 1\). Donc

\[a_{u+vn} = \begin{cases} 0, & u + v \leq n, \\ 1, & u + v \geq n + 1, \end{cases}\]

conformément à (1). Remarquons que la formule est aussi valable pour \(v = 0\).

On a donc obtenu la formule explicite de \((a_i)\), et prouvé qu'elle vérifie la condition (a). La solution est complète. \(\blacksquare\)