Shortlist 2020, C1¶

Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : United Kingdom

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

Solution officielle : Shortlist officielle 2020 (avec solutions), p. 30 (page 32 du PDF)

Énoncé¶

Let \(n\) be a positive integer. Find the number of permutations \(a_1, a_2, \ldots, a_n\) of the sequence \(1, 2, \ldots, n\) satisfying

\[a_1 \leq 2a_2 \leq 3a_3 \leq \cdots \leq n a_n.\]

Indices : les idées clés

Étudier où se trouve \(n\) : dans une permutation valable, soit \(a_n = n\), soit \((a_{n-1}, a_n) = (n, n-1)\) (solution 1).
Récurrence (solution 1) : le nombre \(P_n\) de permutations valables vérifie \(P_n = P_{n-1} + P_{n-2}\), comme la suite de Fibonacci.
Bijection avec des pavages (solution 2) : les permutations valables correspondent aux pavages d'une bande \(1 \times n\) par des dominos et des carrés.
Chaîne d'inégalités forcée à l'égalité (solution 2) : si \(a_t = k\) avec \(t > k + 1\), toute la chaîne \(k a_k \leq \cdots \leq t a_t\) devient une chaîne d'égalités, ce qui est impossible.

Solutions

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

Solution 1¶

Réponse : le nombre de permutations cherché est \(F_{n+1}\), où \((F_k)\) est la suite de Fibonacci : \(F_1 = F_2 = 1\), \(F_{k+1} = F_k + F_{k-1}\).

Notons \((*)\) la condition \(a_1 \leq 2a_2 \leq \cdots \leq n a_n\) et \(P_n\) le nombre de permutations qui la vérifient. On voit facilement que \(P_1 = 1\) et \(P_2 = 2\).

Lemme 1. Soit \(n \geq 3\). Si une permutation \(a_1, \ldots, a_n\) vérifie \((*)\), alors soit \(a_n = n\), soit \(a_{n-1} = n\) et \(a_n = n - 1\).

Preuve. Soit \(k\) l'indice tel que \(a_k = n\). Si \(k = n\), c'est terminé.

Si \(k = n - 1\), alors par \((*)\), \(n(n-1) = (n-1)a_{n-1} \leq n a_n\), donc \(a_n \geq n - 1\). Comme \(a_n \neq a_{n-1} = n\), on a nécessairement \(a_n = n - 1\).

Supposons enfin \(k \leq n - 2\). Pour tout \(k < i < n\), on a \(kn = k a_k \leq i a_i < n a_i\), donc \(a_i \geq k + 1\). De plus,

\[n a_n \geq (n-1)a_{n-1} \geq (n-1)(k+1) = nk + (n - 1 - k) > nk,\]

donc \(a_n \geq k + 1\). Ainsi les \(n - k + 1\) nombres \(a_k, a_{k+1}, \ldots, a_n\) sont tous strictement supérieurs à \(k\) ; mais il n'y a que \(n - k\) telles valeurs : c'est impossible. \(\square\)

Si \(a_n = n\), alors \(a_1, \ldots, a_{n-1}\) est une permutation de \(1, \ldots, n-1\) vérifiant \(a_1 \leq 2a_2 \leq \cdots \leq (n-1)a_{n-1}\) ; il y en a \(P_{n-1}\). La dernière inégalité de \((*)\), \((n-1)a_{n-1} \leq n a_n = n^2\), est automatiquement vraie.
Si \((a_{n-1}, a_n) = (n, n-1)\), alors \(a_1, \ldots, a_{n-2}\) est une permutation de \(1, \ldots, n-2\) vérifiant \(a_1 \leq \cdots \leq (n-2)a_{n-2}\) ; il y en a \(P_{n-2}\). Les deux dernières inégalités de \((*)\) sont automatiques : \((n-2)a_{n-2} \leq (n-2)^2 < n(n-1) = (n-1)a_{n-1} = n a_n\).

Ainsi la suite \((P_n)\) vérifie la récurrence \(P_n = P_{n-1} + P_{n-2}\) pour \(n \geq 3\). Comme \(P_1 = F_2\) et \(P_2 = F_3\), une récurrence immédiate donne \(P_n = F_{n+1}\). \(\blacksquare\)

Solution 2¶

Montrons que les permutations cherchées sont exactement les suivantes : on découpe \(\{1, 2, \ldots, n\}\) en singletons et en paires de nombres consécutifs ; on échange les deux nombres de chaque paire et on laisse les singletons inchangés.

Ces permutations sont en bijection avec les pavages d'une bande \(1 \times n\) par des dominos et des carrés unités ; il est bien connu que le nombre de tels pavages est le nombre de Fibonacci \(F_{n+1}\).

L'affirmation découle, par récurrence, du lemme suivant.

Lemme 2. Soit \(a_1, \ldots, a_n\) une permutation vérifiant \((*)\) et \(k\) un entier avec \(1 \leq k \leq n\) et \(\{a_1, \ldots, a_{k-1}\} = \{1, \ldots, k-1\}\) (si \(k = 1\), la condition est vide). Alors soit \(a_k = k\), soit \(a_k = k + 1\) et \(a_{k+1} = k\).

Preuve. Soit \(t\) tel que \(a_t = k\). Comme \(k \notin \{a_1, \ldots, a_{k-1}\}\), on a \(t = k\) ou \(t > k\). Si \(t = k\), c'est terminé ; supposons donc \(t > k\).

L'un des \(t - k\) nombres \(a_k, a_{k+1}, \ldots, a_{t-1}\) est au moins égal à \(t\) : ces nombres sont tous strictement supérieurs à \(k\) (les valeurs \(1, \ldots, k-1\) sont déjà prises et \(k = a_t\)), et il n'y a que \(t - k - 1\) valeurs strictement comprises entre \(k\) et \(t\). Soit \(i\) un indice avec \(k \leq i < t\) et \(a_i \geq t\) ; alors

\[kt = t a_t \geq i a_i \geq it \geq kt,\]

donc toutes ces inégalités sont des égalités : \(i = k\) et \(a_k = t\). Si \(t = k + 1\), c'est terminé.

Supposons \(t > k + 1\). La chaîne \(kt = k a_k \leq \cdots \leq t a_t = kt\) est alors elle aussi une chaîne d'égalités. On peut aboutir à une contradiction de plusieurs façons, par exemple en remarquant que \(a_{t-1} = \frac{kt}{t-1} = k + \frac{k}{t-1}\) n'est pas entier (car \(0 < k < t - 1\)), ou en considérant le produit des nombres \((k+1)a_{k+1}, \ldots, (t-1)a_{t-1}\) : les nombres \(a_{k+1}, \ldots, a_{t-1}\) sont distincts et supérieurs à \(k\), donc

\[(kt)^{t-k-1} = (k+1)a_{k+1} \cdot (k+2)a_{k+2} \cdots (t-1)a_{t-1} \geq \big((k+1)(k+2)\cdots(t-1)\big)^2.\]

Or \((k+i)(t-i) = kt + i(t - k - i) > kt\) pour \(1 \leq i < t - k\), d'où la contradiction

\[(kt)^{t-k-1} \geq \big((k+1)(k+2)\cdots(t-1)\big)^2 = \prod_{i=1}^{t-k-1} (k+i)(t-i) > (kt)^{t-k-1}.\]

Le cas \(t > k + 1\) est donc impossible. \(\square\)

En appliquant le lemme 2 de proche en proche (\(k = 1\), puis \(k = 2\) ou \(k = 3\), etc.), on voit qu'une permutation valable est bien de la forme annoncée. Précision ajoutée : réciproquement, pour une telle permutation, la suite des \(i a_i\) est formée des \(i^2\) (points fixes) et de deux termes égaux à \(k(k+1)\) pour chaque paire échangée \(\{k, k+1\}\) ; elle est croissante, donc \((*)\) est vérifiée. Le nombre cherché est donc \(F_{n+1}\). \(\blacksquare\)