Shortlist 2024, C7¶
Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : Australia
Concepts : Principe extrémal · Principe des tiroirs
Solution officielle : Shortlist officielle 2024 (avec solutions), section C7 (livret PDF)
Problème 3 de l'OIM 2024
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2024, où il était le problème 3 (jour 1).
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 and let \(a_1, a_2, \ldots\) be an infinite sequence of positive integers. Suppose that, for each \(n > N\), \(a_n\) is equal to the number of times \(a_{n-1}\) appears in the list \(a_1, a_2, \ldots, a_{n-1}\).
Prove that at least one of the sequences \(a_1, a_3, a_5, \ldots\) and \(a_2, a_4, a_6, \ldots\) is eventually periodic.
Indices : les idées clés
- Principe extrémal : regarder le premier moment où un grand entier apparaît pour la \(M\)-ième fois, le plus grand entier \(k\) qui apparaît une infinité de fois, ou le plus petit écart \(p_n\) avant une répétition (solution 1).
- Petits et grands nombres : à partir d'un certain rang, la suite alterne entre « petits » nombres (\(\leq k\), qui apparaissent une infinité de fois) et « grands » nombres (qui apparaissent au plus \(k\) fois) ; un grand nombre \(g\) est suivi du nombre de petits nombres déjà apparus au moins \(g\) fois.
- Principe des tiroirs : parmi \(k + 1\) petits nombres consécutifs, deux sont égaux (solution 1) ; un système déterministe n'ayant qu'un nombre fini d'états est périodique à partir d'un certain rang (solution 2).
- Écarts bornés entre compteurs (solution 2) : si deux compteurs consécutifs s'éloignaient trop, l'un des petits nombres cesserait d'apparaître.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (deux solutions et une remarque).
Notation. Dans toute la suite, on note \(a_{[i,j]}\) la suite finie \(a_i, a_{i+1}, \ldots, a_j\).
Solution 1¶
Soit \(M > \max(a_1, \ldots, a_N)\).
Un entier apparaît une infinité de fois. Sinon, la suite contient des entiers arbitrairement grands. La première fois qu'un entier plus grand que \(M\) apparaît, il est suivi d'un \(1\) ; donc \(1\) apparaît une infinité de fois, contradiction.
Tout entier \(x \geq M\) apparaît au plus \(M - 1\) fois. Sinon, considérons le premier moment où un entier \(x \geq M\) apparaît pour la \(M\)-ième fois (principe extrémal). Jusque-là, chaque apparition de \(x\) (forcément après le rang \(N\)) est précédée d'un entier qui vient d'apparaître pour la \(x\)-ième fois, avec \(x \geq M\) ; ces \(M\) entiers sont distincts (un entier n'atteint qu'une fois le compte \(x\)) et sont apparus au moins \(M\) fois avant ce moment. Par minimalité, ils sont tous \(< M\) : il y en aurait \(M\) parmi \(1, \ldots, M - 1\), contradiction.
Petits, moyens et grands nombres. Il n'y a donc qu'un nombre fini d'entiers qui apparaissent une infinité de fois (tous \(< M\)) ; soit \(k\) le plus grand. Comme \(k\) apparaît une infinité de fois et qu'un nombre fini d'entiers seulement sont \(< M\), une infinité d'entiers plus grands que \(M\) apparaissent au moins \(k\) fois ; chacun est suivi de \(1, 2, \ldots, k-1\) lors de ses premières apparitions, donc chacun des entiers \(1, 2, \ldots, k - 1\) apparaît aussi une infinité de fois. Comme \(k + 1\) n'apparaît qu'un nombre fini de fois, seuls un nombre fini d'entiers apparaissent plus de \(k\) fois ; soit \(l \geq k\) le plus grand. On dit qu'un entier \(x\) est grand si \(x > l\), moyen si \(l \geq x > k\), et petit si \(x \leq k\). En résumé, chaque petit nombre apparaît une infinité de fois, et chaque grand nombre au plus \(k\) fois.
On choisit \(N_1 > N\) assez grand pour que \(a_{N_1}\) soit petit et que, dans \(a_1, \ldots, a_{N_1}\) :
- tous les nombres moyens aient déjà fait toutes leurs apparitions ;
- chaque petit nombre soit apparu plus de \(\max(k, N)\) fois.
Après ce rang, chaque petit nombre, déjà apparu plus de \(k\) fois, est suivi d'un grand nombre ; et chaque grand nombre, apparu au plus \(k\) fois, est suivi d'un petit nombre. Après \(a_{N_1}\), la suite alterne donc entre grands et petits nombres.
Lemme 1. Soit \(g\) un grand nombre apparaissant après \(a_{N_1}\). Si \(g\) est suivi du petit nombre \(h\), alors \(h\) est égal au nombre de petits nombres apparus au moins \(g\) fois jusqu'à ce point.
Preuve. Par définition de \(N_1\), le petit nombre qui précède \(g\) est apparu plus de \(\max(k, N)\) fois, donc \(g > \max(k, N)\). Comme \(g > N\), la \(g\)-ième apparition de chaque petit nombre a lieu après \(a_N\), et elle est donc suivie de \(g\). Comme il y a \(k\) petits nombres et que \(g\) apparaît au plus \(k\) fois, \(g\) apparaît exactement \(k\) fois, toujours après un petit nombre (après \(a_N\)). Ainsi, lors de la \(h\)-ième apparition de \(g\), exactement \(h\) petits nombres sont apparus au moins \(g\) fois, et le terme suivant vaut \(h\). \(\square\)
Lemme 2. Supposons que \(i\) et \(j\) vérifient :
- (a) \(j > i > N_1 + 2\) ;
- (b) \(a_i\) est petit et \(a_i = a_j\) ;
- (c) aucune petite valeur n'apparaît plus d'une fois dans \(a_{[i, j-1]}\).
Alors \(a_{i-2}\) est égal à un petit nombre de \(a_{[i, j-1]}\).
Preuve. Par l'alternance, \(a_{i-2}\) et \(a_{j-2}\) sont petits et \(a_{i-1}\), \(a_{j-1}\) sont grands. Soit \(I\) l'ensemble des petits nombres apparus au moins \(a_{i-1}\) fois dans \(a_{[1, i-1]}\) ; par le lemme 1, \(a_i = |I|\). De même, soit \(J\) l'ensemble des petits nombres apparus au moins \(a_{j-1}\) fois dans \(a_{[1, j-1]}\) ; \(a_j = |J|\), donc \(|I| = |J|\) par (b). Par définition, \(a_{i-2} \in I\) et \(a_{j-2} \in J\).
Supposons \(a_{j-2} \notin I\) : \(a_{j-2}\) est apparu moins de \(a_{i-1}\) fois dans \(a_{[1, i-1]}\). Par (c), il est apparu au plus \(a_{i-1}\) fois dans \(a_{[1, j-1]}\), donc \(a_{j-1} \leq a_{i-1}\). Comme \(a_{[1, i-1]}\) est contenue dans \(a_{[1, j-1]}\), on en déduit \(I \subseteq J\) ; mais \(a_{j-2} \in J \setminus I\) contredit \(|I| = |J|\). Donc \(a_{j-2} \in I\) : il est apparu au moins \(a_{i-1}\) fois dans \(a_{[1, i-1]}\), et une fois de plus dans \(a_{[i, j-1]}\). Donc \(a_{j-1} > a_{i-1}\).
Par (c), tout petit nombre apparu au moins \(a_{j-1}\) fois dans \(a_{[1, j-1]}\) est apparu au moins \(a_{j-1} - 1 \geq a_{i-1}\) fois dans \(a_{[1, i-1]}\). Donc \(J \subseteq I\), et \(I = J\). Ainsi \(a_{i-2} \in J\) ; comme \(a_{i-2}\) est apparu exactement \(a_{i-1}\) fois dans \(a_{[1, i-1]}\), il doit apparaître au moins \(a_{j-1} - a_{i-1} \geq 1\) fois de plus dans \(a_{[i, j-1]}\). \(\square\)
Conclusion. Pour chaque petit nombre \(a_n\) avec \(n > N_1 + 2\), soit \(p_n\) le plus petit entier tel que \(a_{n + p_n} = a_i\) (petit) pour un certain \(i\) avec \(n \leq i < n + p_n\) ; autrement dit, \(a_{n + p_n} = a_i\) est le premier petit nombre à apparaître deux fois à partir de \(a_n\). Si \(i > n\), le lemme 2 (avec \(j = n + p_n\)) montre que \(a_{i-2}\) réapparaît avant \(a_{n + p_n}\), ce qui contredit la minimalité de \(p_n\). Donc \(i = n\). Le lemme 2 (avec \(i = n\), \(j = n + p_n\)) montre aussi que \(a_{n-2}\) réapparaît dans \(a_{[n, n + p_n - 1]}\), d'où \(p_{n-2} \leq p_n\). La suite \(p_n, p_{n+2}, p_{n+4}, \ldots\) est donc croissante (au sens large) et majorée par \(2k\) (il n'y a que \(k\) petits nombres : par le principe des tiroirs, deux des \(k + 1\) petits nombres \(a_n, a_{n+2}, \ldots, a_{n+2k}\) sont égaux). Elle est donc constante à partir d'un certain rang, égale à \(p\), et alors \(a_{n+p} = a_n\) pour tous les indices \(n\) assez grands de la parité des petits nombres. La sous-suite des petits nombres, qui est \(a_1, a_3, a_5, \ldots\) ou \(a_2, a_4, a_6, \ldots\) à partir d'un certain rang, est donc périodique à partir d'un certain rang, de période au plus \(k\). \(\blacksquare\)
Solution 2¶
On reprend la solution 1 jusqu'au lemme 1 inclus. Pour chaque \(n > N_1\), on enregistre combien de fois chacun des nombres \(1, 2, \ldots, k\) est apparu dans \(a_1, \ldots, a_n\), sous la forme d'un \((k+1)\)-uplet
où \(b_i\) est le nombre d'apparitions de \(i\), et où le dernier élément \(j\), dit actif, est le dernier petit nombre apparu dans \(a_1, \ldots, a_n\).
Ce \((k+1)\)-uplet est mis à jour chaque fois que \(a_n\) est petit, de façon déterministe à partir de sa valeur précédente : quand \(a_n = j\) est petit, l'élément actif devient \(j\) et \(b_j\) augmente de \(1\) ; le grand nombre suivant est \(a_{n+1} = b_j\). Par le lemme 1, le nouvel élément actif, c'est-à-dire le petit nombre suivant \(a_{n+2}\), vaut le nombre de termes \(b\) supérieurs ou égaux au nouveau \(b_j\) :
Les écarts \(b_{r+1} - b_r\) sont bornés. Tout entier assez grand qui apparaît \(i + 1\) fois apparaît aussi \(i\) fois, ces deux apparitions ayant lieu après le bloc initial de \(N\) termes. Il existe donc une constante globale \(C\) telle que \(b_{i+1} - b_i \leq C\). Supposons que, pour un certain \(r\), \(b_{r+1} - b_r\) ne soit pas minoré. Comme \(b_{r+1} - b_r\) varie d'au plus \(1\) à chaque mise à jour, il y a une mise à jour où \(b_{r+1} - b_r\) diminue et devient \(< -(k-1)C\). Avec \(b_i - b_{i-1} \leq C\) pour tout \(i\) et l'inégalité triangulaire, on a alors
Comme \(b_{r+1} - b_r\) vient de diminuer, le nouvel élément actif est \(r\). À partir de là, si l'élément actif est au plus \(r\), d'après (1) et (2) le prochain compteur à augmenter est de nouveau l'un de \(b_1, \ldots, b_r\) (et (2) reste vraie). Seuls \(b_1, \ldots, b_r\) augmentent donc désormais, et \(b_k\) n'augmente plus, ce qui contredit le fait que \(k\) apparaît une infinité de fois. Donc \(|b_{r+1} - b_r|\) est borné.
Conclusion. Il en résulte que chaque \(|b_i - b_1|\) est borné, donc le \((k+1)\)-uplet \((b_1 - b_1, b_2 - b_1, \ldots, b_k - b_1;\ j)\) ne prend qu'un nombre fini de valeurs. Comme le prochain élément actif ne dépend que des tailles relatives de \(b_1, \ldots, b_k\), et que la mise à jour des \(b\) ne dépend que de l'élément actif, cet état évolue de façon déterministe dans un ensemble fini : par le principe des tiroirs, il est périodique à partir d'un certain rang, et l'élément actif aussi. La sous-suite des petits nombres, qui est \(a_1, a_3, a_5, \ldots\) ou \(a_2, a_4, a_6, \ldots\), est donc périodique à partir d'un certain rang. \(\blacksquare\)
Remarques¶
Remarque 1. Comme chaque petit nombre apparaît une infinité de fois, la solution 1 montre en fait que la suite des petits nombres a pour période \(k\) : sa partie périodique est une permutation des entiers de \(1\) à \(k\). On peut montrer que toute permutation des entiers de \(1\) à \(k\) peut être obtenue ainsi.