Aller au contenu

Shortlist 2012, N3

Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : non indiqué

Concepts : Divisibilité, PGCD et algorithme d'Euclide · Bijections et dénombrement

Solution officielle : Shortlist officielle 2012 (avec solutions), p. 44 (page 44 du PDF)

Énoncé

Determine all integers \(m \geq 2\) such that every \(n\) with \(\frac{m}{3} \leq n \leq \frac{m}{2}\) divides the binomial coefficient \(\binom{n}{m - 2n}\).

Indices : les idées clés
  • Une identité de coefficients binomiaux : \((p - 2n)\binom{n}{p - 2n} = n\binom{n - 1}{p - 2n - 1}\).
  • PGCD : pour \(p\) premier, \(\operatorname{pgcd}(p - 2n, n)\) divise \(p\) et est inférieur à \(p\), donc vaut \(1\) ; ainsi \(n \mid \binom{n}{p - 2n}\).
  • Contre-exemples : pour \(m = 2k\), prendre \(n = k\) ; pour \(m = p(2k + 1)\) composé impair, prendre \(n = pk\), et \(\frac{1}{pk}\binom{pk}{p}\) n'est pas entier.
Solutions

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

Réponse : tous les nombres premiers.

Solution

Vérifions d'abord que tous les nombres premiers conviennent, et même une condition plus forte : si \(p\) est premier, tout \(n\) avec \(1 \leq n \leq \frac{p}{2}\) divise \(\binom{n}{p - 2n}\). C'est vrai pour \(p = 2\), où \(n = 1\) est la seule possibilité. Pour un nombre premier impair \(p\), prenons \(n \in \left[1, \frac{p}{2}\right]\) et considérons l'identité

\[(p - 2n) \cdot \binom{n}{p - 2n} = n \cdot \binom{n - 1}{p - 2n - 1}.\]

Comme \(p \geq 2n\) et \(p\) est impair, tous les facteurs sont non nuls. Si \(d = \operatorname{pgcd}(p - 2n, n)\), alors \(d\) divise \(p\), mais \(d \leq n < p\), donc \(d = 1\). Ainsi \(p - 2n\) et \(n\) sont premiers entre eux, et le facteur \(n\) du membre de droite divise le coefficient binomial \(\binom{n}{p - 2n}\).

Montrons ensuite qu'aucun nombre composé \(m\) n'a la propriété. On distingue deux cas.

  • Si \(m = 2k\) avec \(k > 1\), prenons \(n = k\). Alors \(\frac{m}{3} \leq n \leq \frac{m}{2}\), mais \(\binom{n}{m - 2n} = \binom{k}{0} = 1\) n'est pas divisible par \(k > 1\).

  • Si \(m\) est impair, il existe un nombre premier impair \(p\) et un entier \(k \geq 1\) tels que \(m = p(2k + 1)\). Prenons \(n = pk\) ; alors \(\frac{m}{3} \leq n \leq \frac{m}{2}\) puisque \(k \geq 1\). Mais

    \[\frac{1}{n}\binom{n}{m - 2n} = \frac{1}{pk}\binom{pk}{p} = \frac{(pk - 1)(pk - 2) \cdots \big(pk - (p - 1)\big)}{p!}\]

    n'est pas entier, car \(p\) divise le dénominateur mais pas le numérateur. \(\blacksquare\)