Shortlist 2006, C3¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Colombia
Concepts : Bijections et dénombrement · Géométrie combinatoire : enveloppe convexe, points du réseau
Solution officielle : Shortlist officielle 2006 (avec solutions), p. 23 (page 24 du PDF)
Énoncé¶
Let \(S\) be a finite set of points in the plane such that no three of them are on a line. For each convex polygon \(P\) whose vertices are in \(S\), let \(a(P)\) be the number of vertices of \(P\), and let \(b(P)\) be the number of points of \(S\) which are outside \(P\). Prove that for every real number \(x\)
where the sum is taken over all convex polygons with vertices in \(S\).
NB. A line segment, a point and the empty set are considered as convex polygons of \(2\), \(1\) and \(0\) vertices, respectively.
Indices : les idées clés
- Homogénéisation : avec \(y = 1 - x\) et \(c(P)\) le nombre de points intérieurs, on multiplie chaque terme par \((x + y)^{c(P)} = 1\) et l'on développe.
- Bijection : choisir un polygone convexe puis certains de ses points intérieurs revient à choisir une partie de \(S\) (enveloppe convexe) ; le coefficient de \(x^ry^{n-r}\) vaut donc \(\binom{n}{r}\).
- Solution 2 : récurrence sur \(n\) et inclusion-exclusion sur les sommets de l'enveloppe convexe retirés.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2006 (deux solutions).
Solution 1¶
Pour tout polygone convexe \(P\) dont les sommets sont dans \(S\), soit \(c(P)\) le nombre de points de \(S\) intérieurs à \(P\), de sorte que \(a(P) + b(P) + c(P) = n\), le nombre total de points de \(S\). En notant \(y = 1 - x\),
Voyons cette expression comme un polynôme homogène de degré \(n\) en deux variables indépendantes \(x\), \(y\). Sous forme développée, c'est la somme de termes \(x^ry^{n-r}\) (\(0 \leq r \leq n\)) multipliés par des coefficients entiers positifs ou nuls.
Pour \(r\) fixé, le coefficient de \(x^ry^{n-r}\) compte le nombre de façons de choisir un polygone convexe \(P\), puis de choisir certains des points de \(S\) intérieurs à \(P\), de sorte que le nombre de sommets de \(P\) et le nombre de points intérieurs choisis aient pour somme \(r\).
Cela correspond simplement au choix d'une partie à \(r\) éléments de \(S\). La correspondance est bijective, car tout ensemble \(T\) de points de \(S\) se découpe d'une seule façon en la réunion de deux parties disjointes, dont la première est l'ensemble des sommets d'un polygone convexe — à savoir l'enveloppe convexe de \(T\) — et la seconde est formée de points intérieurs à ce polygone.
Le coefficient de \(x^ry^{n-r}\) vaut donc \(\binom{n}{r}\). Le résultat voulu en découle :
Solution 2¶
Procédons par récurrence sur le nombre \(n\) de points. Le cas \(n = 0\) est trivial. Soit \(n > 0\), et supposons l'énoncé vrai pour moins de \(n\) points. Prenons un ensemble \(S\) de \(n\) points.
Soit \(C\) l'ensemble des sommets de l'enveloppe convexe de \(S\), et soit \(m = \lvert C \rvert\).
Soit \(X \subset C\) une partie non vide quelconque. Pour tout polygone convexe \(P\) dont les sommets sont dans l'ensemble \(S \setminus X\), il y a \(b(P)\) points de \(S\) à l'extérieur de \(P\). En excluant les points de \(X\) — tous extérieurs à \(P\) — l'ensemble \(S \setminus X\) en contient exactement \(b(P) - \lvert X \rvert\). En écrivant \(1 - x = y\), l'hypothèse de récurrence donne
(où \(P \subset S \setminus X\) signifie que les sommets de \(P\) appartiennent à l'ensemble \(S \setminus X\)). Donc
Tous les polygones convexes apparaissent au moins une fois, sauf l'enveloppe convexe \(C\) elle-même. L'enveloppe convexe apporte \(x^m\). On peut utiliser le principe d'inclusion-exclusion pour calculer la somme des autres termes :
et donc