Shortlist 2007, A7¶

Domaine : Algèbre · Difficulté : ★★★★☆ · Proposé par : Netherlands

Concepts : Polynômes : racines, relations de Viète, factorisation · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2007 (avec solutions), p. 22 (page 23 du PDF)

Problème 6 de l'OIM 2007

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2007, où il était le problème 6 (jour 2).

Énoncé¶

Let \(n > 1\) be an integer. In the space, consider the set

\[S = \{(x, y, z) \mid x, y, z \in \{0, 1, \ldots, n\}, \ x + y + z > 0\}.\]

Find the smallest number of planes that jointly contain all \((n + 1)^3 - 1\) points of \(S\) but none of them passes through the origin.

Indices : les idées clés

Exemple : les \(3n\) plans \(x = i\), \(y = i\), \(z = i\) (\(1 \leq i \leq n\)), ou les plans \(x + y + z = k\) (\(1 \leq k \leq 3n\)).
Méthode polynomiale : le produit des équations des plans est un polynôme \(P\) de degré \(N\) qui s'annule sur \(S\) mais pas en \(0\) ; un lemme montre \(\deg P \geq kn\) en \(k\) variables.
Preuve du lemme : récurrence sur le nombre de variables après réduction modulo \(y(y - 1) \cdots (y - n)\) ; ou bien (solution 2) somme alternée \(\sum(-1)^k\binom{n}{k}P(k) = 0\) pour \(\deg P < n\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2007 (deux solutions et deux remarques). C'est le problème 6 de l'OIM 2007.

Réponse : \(3n\) plans.

Solution 1¶

On trouve facilement \(3n\) tels plans. Par exemple, les plans \(x = i\), \(y = i\) ou \(z = i\) (\(i = 1, 2, \ldots, n\)) recouvrent l'ensemble \(S\), mais aucun ne contient l'origine. Une autre telle famille est formée de tous les plans \(x + y + z = k\) pour \(k = 1, 2, \ldots, 3n\).

Montrons que \(3n\) est le plus petit nombre possible.

Lemme 1. Considérons un polynôme non nul \(P(x_1, \ldots, x_k)\) en \(k\) variables. Supposons que \(P\) s'annule en tous les points \((x_1, \ldots, x_k)\) tels que \(x_1, \ldots, x_k \in \{0, 1, \ldots, n\}\) et \(x_1 + \cdots + x_k > 0\), alors que \(P(0, 0, \ldots, 0) \neq 0\). Alors \(\deg P \geq kn\).

Preuve. Récurrence sur \(k\). Le cas de base \(k = 0\) est clair, puisque \(P \neq 0\). Pour plus de clarté, notons \(y = x_k\).

Soit \(R(x_1, \ldots, x_{k-1}, y)\) le reste de la division de \(P\) par \(Q(y) = y(y - 1) \cdots (y - n)\). Le polynôme \(Q(y)\) s'annule en chaque \(y = 0, 1, \ldots, n\), donc \(P(x_1, \ldots, x_{k-1}, y) = R(x_1, \ldots, x_{k-1}, y)\) pour tous \(x_1, \ldots, x_{k-1}, y \in \{0, 1, \ldots, n\}\). Par conséquent, \(R\) vérifie aussi la condition du lemme ; de plus, \(\deg_y R \leq n\). Évidemment \(\deg R \leq \deg P\), il suffit donc de prouver que \(\deg R \geq nk\).

Développons maintenant le polynôme \(R\) selon les puissances de \(y\) :

\[R(x_1, \ldots, x_{k-1}, y) = R_n(x_1, \ldots, x_{k-1})y^n + R_{n-1}(x_1, \ldots, x_{k-1})y^{n-1} + \cdots + R_0(x_1, \ldots, x_{k-1}).\]

Montrons que le polynôme \(R_n(x_1, \ldots, x_{k-1})\) vérifie la condition de l'hypothèse de récurrence.

Considérons le polynôme \(T(y) = R(0, \ldots, 0, y)\), de degré au plus \(n\). Ce polynôme a \(n\) racines \(y = 1, \ldots, n\) ; d'autre part, \(T(y) \not\equiv 0\) puisque \(T(0) \neq 0\). Donc \(\deg T = n\), et son coefficient dominant est \(R_n(0, 0, \ldots, 0) \neq 0\). En particulier, dans le cas \(k = 1\), on obtient que le coefficient \(R_n\) est non nul.

De même, prenons des nombres quelconques \(a_1, \ldots, a_{k-1} \in \{0, 1, \ldots, n\}\) avec \(a_1 + \cdots + a_{k-1} > 0\). En substituant \(x_i = a_i\) dans \(R(x_1, \ldots, x_{k-1}, y)\), on obtient un polynôme en \(y\) qui s'annule en tous les points \(y = 0, \ldots, n\) et qui est de degré au plus \(n\). Ce polynôme est donc nul, donc \(R_i(a_1, \ldots, a_{k-1}) = 0\) pour tout \(i = 0, 1, \ldots, n\). En particulier, \(R_n(a_1, \ldots, a_{k-1}) = 0\).

Ainsi, le polynôme \(R_n(x_1, \ldots, x_{k-1})\) vérifie la condition de l'hypothèse de récurrence. On a donc \(\deg R_n \geq (k - 1)n\) et \(\deg P \geq \deg R \geq \deg R_n + n \geq kn\). \(\square\)

On peut maintenant terminer la solution. Supposons qu'il y ait \(N\) plans recouvrant tous les points de \(S\) mais ne contenant pas l'origine. Soient \(a_ix + b_iy + c_iz + d_i = 0\) leurs équations. Considérons le polynôme

\[P(x, y, z) = \prod_{i=1}^{N}(a_ix + b_iy + c_iz + d_i).\]

Il est de degré total \(N\). Ce polynôme a la propriété que \(P(x_0, y_0, z_0) = 0\) pour tout \((x_0, y_0, z_0) \in S\), alors que \(P(0, 0, 0) \neq 0\). D'après le lemme 1, on obtient donc \(N = \deg P \geq 3n\), comme voulu. \(\blacksquare\)

Remarque 1. Il existe beaucoup d'autres familles de \(3n\) plans recouvrant l'ensemble \(S\) mais pas l'origine.

Solution 2¶

Voici une autre preuve du lemme 1, le lemme principal. On se limite ici au cas \(k = 3\), qui est celui utilisé dans la solution, et l'on note les variables \(x\), \(y\) et \(z\). (La même preuve fonctionne aussi dans le cas général.)

Le fait suivant est connu, avec diverses preuves ; on en donne une par souci de complétude.

Lemme 2. Pour des entiers quelconques \(0 \leq m < n\) et un polynôme quelconque \(P(x)\) de degré \(m\),

\[\sum_{k=0}^{n}(-1)^k\binom{n}{k}P(k) = 0. \tag{1}\]

Preuve. Récurrence sur \(n\). Si \(n = 1\), alors \(P(x)\) est constant, donc \(P(1) - P(0) = 0\), et le cas de base est prouvé.

Pour l'hérédité, posons \(P_1(x) = P(x + 1) - P(x)\). Alors évidemment \(\deg P_1 = \deg P - 1 = m - 1 < n - 1\), donc l'hypothèse de récurrence donne

\[\begin{aligned} 0 &= -\sum_{k=0}^{n-1}(-1)^k\binom{n - 1}{k}P_1(k) = \sum_{k=0}^{n-1}(-1)^k\binom{n - 1}{k}\big(P(k) - P(k + 1)\big) \\ &= \sum_{k=0}^{n-1}(-1)^k\binom{n - 1}{k}P(k) - \sum_{k=0}^{n-1}(-1)^k\binom{n - 1}{k}P(k + 1) \\ &= \sum_{k=0}^{n-1}(-1)^k\binom{n - 1}{k}P(k) + \sum_{k=1}^{n}(-1)^k\binom{n - 1}{k - 1}P(k) \\ &= P(0) + \sum_{k=1}^{n-1}(-1)^k\left(\binom{n - 1}{k - 1} + \binom{n - 1}{k}\right)P(k) + (-1)^nP(n) = \sum_{k=0}^{n}(-1)^k\binom{n}{k}P(k). \qquad \square \end{aligned}\]

Revenons à la preuve du lemme 1. Supposons au contraire que \(\deg P = N < 3n\). Considérons la somme

\[\Sigma = \sum_{i=0}^{n}\sum_{j=0}^{n}\sum_{k=0}^{n}(-1)^{i+j+k}\binom{n}{i}\binom{n}{j}\binom{n}{k}P(i, j, k).\]

Le seul terme non nul de cette somme est \(P(0, 0, 0)\), et son coefficient est \(\binom{n}{0}^3 = 1\) ; donc \(\Sigma = P(0, 0, 0) \neq 0\).

D'autre part, si \(P(x, y, z) = \sum_{\alpha + \beta + \gamma \leq N} p_{\alpha,\beta,\gamma}x^\alpha y^\beta z^\gamma\), alors

\[\begin{aligned} \Sigma &= \sum_{i=0}^{n}\sum_{j=0}^{n}\sum_{k=0}^{n}(-1)^{i+j+k}\binom{n}{i}\binom{n}{j}\binom{n}{k}\sum_{\alpha + \beta + \gamma \leq N} p_{\alpha,\beta,\gamma}i^\alpha j^\beta k^\gamma \\ &= \sum_{\alpha + \beta + \gamma \leq N} p_{\alpha,\beta,\gamma}\left(\sum_{i=0}^{n}(-1)^i\binom{n}{i}i^\alpha\right)\left(\sum_{j=0}^{n}(-1)^j\binom{n}{j}j^\beta\right)\left(\sum_{k=0}^{n}(-1)^k\binom{n}{k}k^\gamma\right). \end{aligned}\]

Considérons un terme quelconque de cette somme ; montrons qu'il est nul. Comme \(N < 3n\), l'une des trois inégalités \(\alpha < n\), \(\beta < n\) ou \(\gamma < n\) est vraie. Pour fixer les idées, supposons \(\alpha < n\). En appliquant le lemme 2 au polynôme \(x^\alpha\), on obtient \(\sum_{i=0}^{n}(-1)^i\binom{n}{i}i^\alpha = 0\), donc le terme est nul, comme voulu.

Cela donne \(\Sigma = 0\), ce qui est une contradiction. Donc \(\deg P \geq 3n\). \(\blacksquare\)

Remarque 2. La preuve ne dépend pas des coefficients précis du lemme 2. Au lieu de ce lemme, on peut simplement utiliser l'existence de nombres \(\alpha_0, \alpha_1, \ldots, \alpha_n\) (\(\alpha_0 \neq 0\)) tels que

\[\sum_{k=0}^{n}\alpha_kk^m = 0 \qquad \text{pour tout } 0 \leq m < n.\]

C'est un système d'équations linéaires homogènes en les inconnues \(\alpha_i\). Comme le nombre d'équations est inférieur au nombre d'inconnues, le seul point non trivial est l'existence d'une solution avec \(\alpha_0 \neq 0\). On peut le montrer de diverses façons.