Aller au contenu

Shortlist 2019, C1

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

Concepts : Récurrence et constructions récursives · Bijections et dénombrement

Solution officielle : Shortlist officielle 2019 (avec solutions), section C1 (livret PDF)

Énoncé

The infinite sequence \(a_0, a_1, a_2, \ldots\) of (not necessarily different) integers has the following properties: \(0 \leq a_i \leq i\) for all integers \(i \geq 0\), and

\[\binom{k}{a_0} + \binom{k}{a_1} + \cdots + \binom{k}{a_k} = 2^k\]

for all integers \(k \geq 0\).

Prove that all integers \(N \geq 0\) occur in the sequence (that is, for all \(N \geq 0\), there exists \(i \geq 0\) with \(a_i = N\)).

Indices : les idées clés
  • Deviner la structure des premiers termes : à chaque rang \(k\), les termes \(a_0, \ldots, a_k\) sont, à l'ordre près, \(0, 1, \ldots, \ell - 1\) et \(0, 1, \ldots, k - \ell\) pour un certain \(\ell\).
  • Récurrence sur \(k\) pour établir cette description.
  • Coefficients binomiaux : la symétrie \(\binom{m+1}{i} = \binom{m+1}{m+1-i}\) et \(\sum_i \binom{m+1}{i} = 2^{m+1}\) isolent \(\binom{m+1}{a_{m+1}} = \binom{m+1}{\ell}\).
  • Unimodalité : les coefficients \(\binom{m+1}{i}\) croissent jusqu'au milieu puis décroissent, donc \(a_{m+1} \in \{\ell, m + 1 - \ell\}\).
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2019 (une solution).

Solution

Montrons par récurrence sur \(k\) que chaque segment initial \(a_0, a_1, \ldots, a_k\) de la suite est formé des éléments suivants (comptés avec multiplicité, pas forcément dans cet ordre), pour un certain \(\ell \geq 0\) avec \(2\ell \leq k + 1\) :

\[0, 1, \ldots, \ell - 1, \quad 0, 1, \ldots, k - \ell.\]

Pour \(k = 0\), on a \(a_0 = 0\) (car \(0 \leq a_0 \leq 0\)), ce qui est de cette forme avec \(\ell = 0\).

Supposons maintenant que, pour \(k = m\), les éléments \(a_0, a_1, \ldots, a_m\) soient

\[0, 0, 1, 1, 2, 2, \ldots, \ell - 1, \ell - 1, \ell, \ell + 1, \ldots, m - \ell - 1, m - \ell\]

pour un certain \(\ell\) avec \(0 \leq 2\ell \leq m + 1\). L'hypothèse de l'énoncé au rang \(m + 1\) s'écrit

\[\binom{m+1}{a_0} + \binom{m+1}{a_1} + \cdots + \binom{m+1}{a_m} + \binom{m+1}{a_{m+1}} = 2^{m+1},\]

c'est-à-dire

\[\left( \binom{m+1}{0} + \cdots + \binom{m+1}{\ell - 1} \right) + \left( \binom{m+1}{0} + \cdots + \binom{m+1}{m - \ell} \right) + \binom{m+1}{a_{m+1}} = 2^{m+1},\]

ou encore, grâce à la symétrie \(\binom{m+1}{i} = \binom{m+1}{m+1-i}\) appliquée à la deuxième parenthèse,

\[\left( \binom{m+1}{0} + \cdots + \binom{m+1}{\ell - 1} \right) + \left( \binom{m+1}{m+1} + \binom{m+1}{m} + \cdots + \binom{m+1}{\ell + 1} \right) + \binom{m+1}{a_{m+1}} = 2^{m+1}.\]

Or on sait que

\[\binom{m+1}{0} + \binom{m+1}{1} + \cdots + \binom{m+1}{m+1} = 2^{m+1}.\]

Par soustraction, il ne manque que le terme d'indice \(\ell\) :

\[\binom{m+1}{a_{m+1}} = \binom{m+1}{\ell}.\]

Comme les coefficients \(\binom{m+1}{i}\) sont strictement croissants pour \(i \leq \frac{m+1}{2}\) et strictement décroissants pour \(i \geq \frac{m+1}{2}\), on en déduit que \(a_{m+1} = \ell\) ou \(a_{m+1} = m + 1 - \ell\). Dans les deux cas, \(a_0, \ldots, a_{m+1}\) est encore de la forme annoncée : si \(a_{m+1} = m + 1 - \ell\), avec le même \(\ell\) ; si \(a_{m+1} = \ell\) (et \(2\ell < m + 1\), sinon on est dans le cas précédent), avec \(\ell + 1\) à la place de \(\ell\), qui vérifie \(2(\ell + 1) \leq m + 2\). Cela achève la récurrence.

Conséquence de cette description : comme \(k - \ell \geq \frac{k-1}{2}\), tout entier \(N \geq 0\) apparaît parmi \(a_0, \ldots, a_{2N}\) (dans la liste \(0, 1, \ldots, k - \ell\) avec \(k = 2N\)). Donc tout entier \(N \geq 0\) est un terme de la suite. \(\blacksquare\)