Aller au contenu

Shortlist 2013, C5

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

Concepts : Principe des tiroirs · Suites et récurrences

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

Énoncé

Let \(r\) be a positive integer, and let \(a_0, a_1, \ldots\) be an infinite sequence of real numbers. Assume that for all nonnegative integers \(m\) and \(s\) there exists a positive integer \(n \in [m + 1, m + r]\) such that

\[a_m + a_{m+1} + \cdots + a_{m+s} = a_n + a_{n+1} + \cdots + a_{n+s}.\]

Prove that the sequence is periodic, i.e. there exists some \(p \geq 1\) such that \(a_{n+p} = a_n\) for all \(n \geq 0\).

Indices : les idées clés
  • Lemme : si chaque \(b_m\) se retrouve parmi \(b_{m+1}, \ldots, b_{m+r}\), alors chaque valeur revient dans toute fenêtre de longueur \(r\), et la suite prend au plus \(r\) valeurs.
  • Tiroirs : avec \(s = 0\), les \(a_i\) prennent au plus \(r\) valeurs, donc les \(r\)-uplets \(A_i = (a_i, \ldots, a_{i+r-1})\) au plus \(r^r\) ; il existe \(p \leq r^r\) tel que \(A_d = A_{d+p}\) pour une infinité de \(d\).
  • Descente : en appliquant le lemme aux sommes \(b_k = a_k + \cdots + a_{k+p-1}\), on montre que \(A_{d+1} = A_{d+p+1}\) entraîne \(A_d = A_{d+p}\) ; l'égalité vaut donc pour tout \(d\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2013 (une solution et deux remarques).

Solution

Pour des indices \(m \leq n\), notons \(S(m, n) = a_m + a_{m+1} + \cdots + a_{n-1}\) ; ainsi \(S(n, n) = 0\). Commençons par un lemme.

Lemme. Soit \(b_0, b_1, \ldots\) une suite infinie. Supposons que pour tout entier \(m \geq 0\), il existe un entier \(n \in [m + 1, m + r]\) tel que \(b_m = b_n\). Alors, pour tous indices \(k \leq \ell\), il existe un indice \(t \in [\ell, \ell + r - 1]\) tel que \(b_t = b_k\). De plus, la suite \((b_i)\) prend au plus \(r\) valeurs distinctes.

Preuve. Pour la première affirmation, il existe une suite infinie d'indices \(k_1 = k, k_2, k_3, \ldots\) telle que \(b_{k_1} = b_{k_2} = \cdots = b_k\) et \(k_i < k_{i+1} \leq k_i + r\) pour tout \(i \geq 1\). Cette suite n'est pas majorée, donc elle rencontre tout segment de la forme \([\ell, \ell + r - 1]\) avec \(\ell \geq k\), comme voulu.

Pour la seconde affirmation, supposons au contraire qu'il existe \(r + 1\) nombres distincts \(b_{i_1}, \ldots, b_{i_{r+1}}\). Appliquons la première affirmation à \(k = i_1, \ldots, i_{r+1}\) et \(\ell = \max\{i_1, \ldots, i_{r+1}\}\) : pour tout \(j \in \{1, \ldots, r + 1\}\), il existe \(t_j \in [\ell, \ell + r - 1]\) tel que \(b_{t_j} = b_{i_j}\) (le livret écrit \([s, s + r - 1]\) ; il faut lire \([\ell, \ell + r - 1]\)). Le segment \([\ell, \ell + r - 1]\) devrait donc contenir \(r + 1\) entiers distincts, ce qui est absurde. \(\square\)

Avec \(s = 0\) dans la condition de l'énoncé, on voit que la suite \((a_i)\) vérifie la condition du lemme ; elle prend donc au plus \(r\) valeurs distinctes. Notons \(A_i\) le \(r\)-uplet ordonné \((a_i, \ldots, a_{i+r-1})\) ; il y a au plus \(r^r\) tels \(r\)-uplets distincts, donc, par le principe des tiroirs, pour tout \(k \geq 0\), deux des \(r\)-uplets \(A_k, A_{k+1}, \ldots, A_{k+r^r}\) sont égaux. Il existe donc un entier \(p\) avec \(1 \leq p \leq r^r\) tel que l'égalité \(A_d = A_{d+p}\) soit vraie pour une infinité d'indices \(d\). Soit \(D\) l'ensemble des indices \(d\) qui la vérifient.

Montrons que \(D\) est l'ensemble de tous les entiers positifs ou nuls. Comme \(D\) n'est pas borné, il suffit de montrer que \(d \in D\) dès que \(d + 1 \in D\). Pour cela, posons \(b_k = S(k, p + k)\). La suite \(b_0, b_1, \ldots\) vérifie les conditions du lemme, donc il existe un indice \(t \in [d + 1, d + r]\) tel que \(S(t, t + p) = S(d, d + p)\). Cette relation s'écrit \(S(d, t) = S(d + p, t + p)\). Comme \(A_{d+1} = A_{d+p+1}\), on a \(S(d + 1, t) = S(d + p + 1, t + p)\), d'où

\[a_d = S(d, t) - S(d + 1, t) = S(d + p, t + p) - S(d + p + 1, t + p) = a_{d+p},\]

et donc \(A_d = A_{d+p}\), comme voulu.

Finalement, \(A_d = A_{d+p}\) pour tout \(d\), donc en particulier \(a_d = a_{d+p}\) pour tout \(d\). \(\blacksquare\)

Remarques

Remarque 1. Dans cette preuve, le majorant de la plus petite période est \(r^r\). Ce majorant n'est pas optimal ; on peut par exemple l'améliorer en \((r - 1)^r\) pour \(r \geq 3\). D'autre part, cette plus petite période peut être plus grande que \(r\). Par exemple, on vérifie facilement que la suite de période \((3, -3, 3, -3, 3, -1, -1, -1)\) satisfait la condition du problème pour \(r = 7\).

Remarque 2. La conclusion reste vraie même si la condition n'est vérifiée que pour tout \(s \geq N\), pour un certain entier \(N \geq 1\). On peut procéder ainsi. D'abord, les sommes de la forme \(S(i, i + N)\) prennent au plus \(r\) valeurs, de même que les sommes \(S(i, i + N + 1)\). Donc les termes \(a_i = S(i, i + N + 1) - S(i + 1, i + N + 1)\) prennent au plus \(r^2\) valeurs distinctes. Ensuite, parmi les uplets \(A_k, A_{k+N}, \ldots, A_{k + r^{2r} N}\), deux sont égaux, donc pour un certain \(p \leq r^{2r}\), l'ensemble \(D = \{d : A_d = A_{d+Np}\}\) est infini. Les arguments suivants s'appliquent presque mot pour mot, en remplaçant \(p\) par \(Np\). Une fois prouvé qu'une telle suite est aussi nécessairement périodique, on peut ramener le majorant de la plus petite période à \(r^r\), essentiellement en vérifiant que la suite satisfait la version originale de la condition.