Aller au contenu

Shortlist 2008, C2

Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : non indiqué

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

Solution officielle : Shortlist officielle 2008 (avec solutions), p. 23 (page 24 du PDF)

Énoncé

For every positive integer \(n\) determine the number of permutations \((a_1, a_2, \ldots, a_n)\) of the set \(\{1, 2, \ldots, n\}\) with the following property:

\[2(a_1 + a_2 + \cdots + a_k) \quad \text{is divisible by } k \quad \text{for } k = 1, 2, \ldots, n.\]
Indices : les idées clés
  • Dernier terme : la condition pour \(k = n - 1\) donne \((n - 1) \mid 2a_n - 2\), donc \(a_n \in \{1, \frac{n + 1}{2}, n\}\) ; la condition pour \(k = n - 2\) exclut \(\frac{n + 1}{2}\).
  • Bijections : les bonnes permutations finissant par \(n\), et celles finissant par \(1\) (après avoir retiré \(1\) à chaque terme), correspondent aux bonnes permutations de \(\{1, \ldots, n - 1\}\).
  • Récurrence : \(F_n = 2F_{n-1}\) avec \(F_3 = 6\), d'où \(F_n = 3 \cdot 2^{n-2}\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2008 (une solution).

Solution

Réponse : \(F_1 = 1\), \(F_2 = 2\), et \(F_n = 3 \cdot 2^{n-2}\) pour \(n \geq 3\).

Pour chaque \(n\), notons \(F_n\) le nombre de permutations de \(\{1, 2, \ldots, n\}\) ayant la propriété voulue ; on les appelle belles. Pour \(n = 1, 2, 3\), toute permutation est belle, donc \(F_1 = 1\), \(F_2 = 2\), \(F_3 = 6\).

Prenons \(n > 3\) et une belle permutation quelconque \((a_1, a_2, \ldots, a_n)\) de \(\{1, 2, \ldots, n\}\). Alors \(n - 1\) doit diviser le nombre

\[2(a_1 + a_2 + \cdots + a_{n-1}) = 2\big((1 + 2 + \cdots + n) - a_n\big) = n(n + 1) - 2a_n = (n + 2)(n - 1) + (2 - 2a_n).\]

Donc \(2a_n - 2\) doit être divisible par \(n - 1\), donc égal à \(0\), \(n - 1\) ou \(2n - 2\). Cela signifie que

\[a_n = 1 \qquad \text{ou} \qquad a_n = \frac{n + 1}{2} \qquad \text{ou} \qquad a_n = n.\]

Supposons \(a_n = \frac{n + 1}{2}\). Comme la permutation est belle, en prenant \(k = n - 2\), on obtient que \(n - 2\) doit diviser

\[2(a_1 + a_2 + \cdots + a_{n-2}) = 2\big((1 + 2 + \cdots + n) - a_n - a_{n-1}\big) = n(n + 1) - (n + 1) - 2a_{n-1} = (n + 2)(n - 2) + (3 - 2a_{n-1}).\]

Donc \(2a_{n-1} - 3\) doit être divisible par \(n - 2\), donc égal à \(0\), \(n - 2\) ou \(2n - 4\). Évidemment, \(0\) et \(2n - 4\) sont exclus car \(2a_{n-1} - 3\) est impair. La possibilité restante (\(2a_{n-1} - 3 = n - 2\)) donne \(a_{n-1} = \frac{n + 1}{2} = a_n\), ce qui est impossible aussi. Cela élimine \(\frac{n + 1}{2}\) comme valeur possible de \(a_n\). Par conséquent, \(a_n = 1\) ou \(a_n = n\).

Si \(a_n = n\), alors \((a_1, a_2, \ldots, a_{n-1})\) est une belle permutation de \(\{1, 2, \ldots, n - 1\}\). Il y a \(F_{n-1}\) telles permutations. En ajoutant \(n\) à la fin de l'une quelconque d'entre elles, on crée une belle permutation de \(\{1, 2, \ldots, n\}\).

Si \(a_n = 1\), alors \((a_1 - 1, a_2 - 1, \ldots, a_{n-1} - 1)\) est une permutation de \(\{1, 2, \ldots, n - 1\}\). Elle est aussi belle, car le nombre

\[2\big((a_1 - 1) + \cdots + (a_k - 1)\big) = 2(a_1 + \cdots + a_k) - 2k\]

est divisible par \(k\), pour tout \(k \leq n - 1\). Et, là encore, chacune des \(F_{n-1}\) belles permutations \((b_1, b_2, \ldots, b_{n-1})\) de \(\{1, 2, \ldots, n - 1\}\) donne une belle permutation de \(\{1, 2, \ldots, n\}\) dont le dernier terme est \(1\), à savoir \((b_1 + 1, b_2 + 1, \ldots, b_{n-1} + 1, 1)\).

Les correspondances bijectives établies dans les deux cas montrent qu'il y a \(F_{n-1}\) belles permutations de \(\{1, 2, \ldots, n\}\) de dernier terme \(1\), et aussi \(F_{n-1}\) belles permutations de dernier terme \(n\). On obtient la récurrence \(F_n = 2F_{n-1}\). Avec la valeur initiale \(F_3 = 6\), cela donne la formule \(F_n = 3 \cdot 2^{n-2}\) pour \(n \geq 3\). \(\blacksquare\)