Shortlist 2006, C7¶
Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : Japan
Concepts : Géométrie combinatoire : enveloppe convexe, points du réseau · Graphes : degrés, chemins, arbres
Solution officielle : Shortlist officielle 2006 (avec solutions), p. 31 (page 32 du PDF)
Figures reprises du livret officiel de la Shortlist.
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Consider a convex polyhedron without parallel edges and without an edge parallel to any face other than the two faces adjacent to it.
Call a pair of points of the polyhedron antipodal if there exist two parallel planes passing through these points and such that the polyhedron is contained between these planes.
Let \(A\) be the number of antipodal pairs of vertices, and let \(B\) be the number of antipodal pairs of midpoints of edges. Determine the difference \(A - B\) in terms of the numbers of vertices, edges and faces.
Indices : les idées clés
- Image sphérique : chaque face, arête et sommet correspond à un point, un arc et une région de la sphère unité (normales extérieures) ; on superpose cette décomposition et sa symétrique (géométrie combinatoire).
- Traduction : deux sommets sont antipodaux si et seulement si leurs régions (l'une retournée) se chevauchent ; deux milieux d'arêtes le sont si et seulement si leurs arcs se coupent.
- Formule d'Euler sur la nouvelle décomposition (graphe planaire) : \((2\ell + 2B) + 2A = (2m + 4B) + 2\), d'où \(A - B = n - 1\) ; ou bien (solution 2) on applique Euler au polyèdre \(\Gamma - \Gamma\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2006 (deux solutions).
Réponse : \(A - B = n - 1\), où \(n\) est le nombre de sommets.
Solution 1¶
Notons \(\Gamma\) le polyèdre ; soient \(V_1, V_2, \ldots, V_n\), \(E_1, E_2, \ldots, E_m\) et \(F_1, F_2, \ldots, F_\ell\) respectivement ses sommets, ses arêtes et ses faces. Notons \(Q_i\) le milieu de l'arête \(E_i\).
Soit \(S\) la sphère unité, l'ensemble de tous les vecteurs unitaires de l'espace. Associons aux éléments du bord de \(\Gamma\) des objets de \(S\) de la façon suivante.
Pour une face \(F_i\), soient \(S^+(F_i)\) et \(S^-(F_i)\) les vecteurs normaux unitaires de la face \(F_i\), dirigés respectivement vers l'extérieur et vers l'intérieur de \(\Gamma\). Ces points sont diamétralement opposés.
Pour une arête \(E_j\), de faces voisines \(F_{i_1}\) et \(F_{i_2}\), prenons tous les plans d'appui de \(\Gamma\) (plans qui ont un point commun avec \(\Gamma\) mais ne le coupent pas) contenant l'arête \(E_j\), et soit \(S^+(E_j)\) l'ensemble de leurs vecteurs normaux extérieurs. L'ensemble \(S^+(E_j)\) est un arc de grand cercle de \(S\). L'arc \(S^+(E_j)\) est perpendiculaire à l'arête \(E_j\) et relie les points \(S^+(F_{i_1})\) et \(S^+(F_{i_2})\). Définissons aussi l'ensemble des vecteurs normaux intérieurs \(S^-(E_j)\), symétrique de \(S^+(E_j)\) par rapport à l'origine.
Pour un sommet \(V_k\), extrémité commune des arêtes \(E_{j_1}, \ldots, E_{j_h}\) et commun aux faces \(F_{i_1}, \ldots, F_{i_h}\), prenons tous les plans d'appui de \(\Gamma\) passant par le point \(V_k\), et soit \(S^+(V_k)\) l'ensemble de leurs vecteurs normaux extérieurs. C'est une région de \(S\), un polygone sphérique de sommets \(S^+(F_{i_1}), \ldots, S^+(F_{i_h})\) délimité par les arcs \(S^+(E_{j_1}), \ldots, S^+(E_{j_h})\). Soit \(S^-(V_k)\) le symétrique de \(S^+(V_k)\), l'ensemble des vecteurs normaux intérieurs.
Remarquons que la région \(S^+(V_k)\) est convexe, au sens où c'est l'intersection de plusieurs demi-sphères.
Traduisons maintenant les conditions sur \(\Gamma\) dans le langage de ces objets.
(a) Le polyèdre \(\Gamma\) n'a pas d'arêtes parallèles — les grands cercles des arcs \(S^+(E_i)\) et \(S^-(E_j)\) sont différents pour tous \(i \neq j\).
(b) Si une arête \(E_i\) n'appartient pas à une face \(F_j\), elles ne sont pas parallèles — le grand cercle qui contient les arcs \(S^+(E_i)\) et \(S^-(E_i)\) ne passe pas par les points \(S^+(F_j)\) et \(S^-(F_j)\).
(c) Le polyèdre \(\Gamma\) n'a pas de faces parallèles — les points \(S^+(F_i)\) et \(S^-(F_j)\) sont deux à deux distincts.
Les régions \(S^+(V_k)\), les arcs \(S^+(E_j)\) et les points \(S^+(F_i)\) forment une décomposition de la surface de la sphère. Les régions \(S^-(V_k)\), les arcs \(S^-(E_j)\) et les points \(S^-(F_i)\) forment la décomposition symétrique. Ces décompositions sont étroitement liées au problème.
Lemme 1. Pour tous \(1 \leq i, j \leq n\), les régions \(S^-(V_i)\) et \(S^+(V_j)\) se chevauchent si et seulement si les sommets \(V_i\) et \(V_j\) sont antipodaux.
Lemme 2. Pour tous \(1 \leq i, j \leq m\), les arcs \(S^-(E_i)\) et \(S^+(E_j)\) se coupent si et seulement si les milieux \(Q_i\) et \(Q_j\) des arêtes \(E_i\) et \(E_j\) sont antipodaux.
Preuve du lemme 1. Remarquons d'abord que, d'après les propriétés (a), (b), (c) ci-dessus, les deux régions ne peuvent pas avoir en commun un seul point ou un arc. Elles sont soit disjointes, soit se chevauchent.
Supposons que les deux régions aient un point intérieur commun \(u\). Soient \(P_1\) et \(P_2\) deux plans d'appui parallèles de \(\Gamma\) passant par les points \(V_i\) et \(V_j\) respectivement, de vecteur normal \(u\). Par définition des régions \(S^-(V_i)\) et \(S^+(V_j)\), \(u\) est le vecteur normal intérieur de \(P_1\) et le vecteur normal extérieur de \(P_2\). Le polyèdre \(\Gamma\) est donc entre les deux plans ; les sommets \(V_i\) et \(V_j\) sont antipodaux.
Pour la réciproque, supposons \(V_i\) et \(V_j\) antipodaux. Il existe alors deux plans d'appui parallèles \(P_1\) et \(P_2\) passant par \(V_i\) et \(V_j\) respectivement, tels que \(\Gamma\) soit entre eux. Soit \(u\) le vecteur normal intérieur de \(P_1\) ; alors \(u\) est le vecteur normal extérieur de \(P_2\), donc \(u \in S^-(V_i) \cap S^+(V_j)\). Les deux régions ont un point commun, donc elles se chevauchent. \(\square\)
Preuve du lemme 2. Là encore, d'après les propriétés (a), (b) ci-dessus, les extrémités de l'arc \(S^-(E_i)\) ne peuvent pas appartenir à \(S^+(E_j)\), et inversement. Les deux arcs sont soit disjoints, soit sécants.
Supposons que les arcs \(S^-(E_i)\) et \(S^+(E_j)\) se coupent au point \(u\). Soient \(P_1\) et \(P_2\) les deux plans d'appui passant par les arêtes \(E_i\) et \(E_j\) respectivement, de vecteur normal \(u\). Par définition des arcs \(S^-(E_i)\) et \(S^+(E_j)\), le vecteur \(u\) est dirigé vers l'intérieur depuis \(P_1\) et vers l'extérieur depuis \(P_2\). Donc \(\Gamma\) est entre les plans. Comme les plans \(P_1\) et \(P_2\) passent par \(Q_i\) et \(Q_j\), ces points sont antipodaux.
Pour la réciproque, supposons que les points \(Q_i\) et \(Q_j\) soient antipodaux. Soient \(P_1\) et \(P_2\) deux plans d'appui passant respectivement par ces points. Une arête ne peut pas couper un plan d'appui, donc \(E_i\) et \(E_j\) sont respectivement dans les plans \(P_1\) et \(P_2\). Soit \(u\) le vecteur normal intérieur de \(P_1\), qui est aussi le vecteur normal extérieur de \(P_2\). Alors \(u \in S^-(E_i) \cap S^+(E_j)\). Les deux arcs ne sont donc pas disjoints ; ils se coupent. \(\square\)
Construisons maintenant une nouvelle décomposition de la sphère \(S\). Traçons tous les arcs \(S^+(E_i)\) et \(S^-(E_j)\) sur la sphère \(S\), et plaçons un nœud en chaque point où deux arcs se rencontrent. On a \(\ell\) nœuds aux points \(S^+(F_i)\) et \(\ell\) autres nœuds aux points \(S^-(F_i)\), correspondant aux faces de \(\Gamma\) ; d'après la propriété (c), ils sont différents. On a aussi certains couples \(1 \leq i, j \leq m\) pour lesquels les arcs \(S^-(E_i)\) et \(S^+(E_j)\) se coupent. D'après le lemme 2, chaque paire antipodale \((Q_i, Q_j)\) donne deux telles intersections ; le nombre total d'intersections est donc \(2B\), et l'on a en tout \(2\ell + 2B\) nœuds.
Chaque nœud d'intersection coupe deux arcs, ce qui augmente le nombre d'arcs de \(2\). Comme on est parti de \(2m\) arcs, correspondant aux arêtes de \(\Gamma\), le nombre de morceaux de courbes obtenus est \(2m + 4B\).
Le réseau de ces morceaux de courbes découpe la sphère en de « nouvelles » régions. Chaque nouvelle région est l'intersection de deux ensembles \(S^-(V_i)\) et \(S^+(V_j)\) qui se chevauchent. Par convexité, l'intersection de deux régions qui se chevauchent est convexe, donc d'un seul tenant. D'après le lemme 1, chaque paire de régions qui se chevauchent correspond à une paire de sommets antipodaux, et chaque paire de sommets antipodaux donne deux chevauchements différents, symétriques par rapport à l'origine. Le nombre de nouvelles régions est donc \(2A\).
Le résultat découle maintenant de la formule d'Euler pour les polyèdres. On a \(n + \ell = m + 2\) et
donc
Ainsi, \(A - B\) est inférieur de un au nombre de sommets de \(\Gamma\). \(\blacksquare\)
Solution 2¶
On garde les notations de la solution 1 pour le polyèdre, ses sommets, arêtes et faces. On identifie les points aux vecteurs issus de l'origine. Le polyèdre \(\Gamma\) est vu comme un ensemble convexe fermé, intérieur compris. Dans certains cas, les arêtes et les faces de \(\Gamma\) sont aussi vues comme des ensembles de points. Le symbole \(\partial\) désigne le bord d'un ensemble ; par exemple, \(\partial\Gamma\) est la surface de \(\Gamma\).
Soit \(\Delta = \Gamma - \Gamma = \{U - V : U, V \in \Gamma\}\) l'ensemble des vecteurs joignant deux points quelconques de \(\Gamma\). Alors \(\Delta\), somme de deux ensembles convexes bornés, est aussi un ensemble convexe borné, et, par construction, il est symétrique par rapport à l'origine. Montrons que \(\Delta\) est aussi un polyèdre, et exprimons les nombres de ses faces, arêtes et sommets en fonction de \(n\), \(m\), \(\ell\), \(A\) et \(B\).
Lemme 1. Pour des points \(U, V \in \Gamma\), le point \(W = U - V\) est un point du bord de \(\Delta\) si et seulement si \(U\) et \(V\) sont antipodaux. De plus, pour tout point du bord \(W \in \partial\Delta\), il existe exactement un couple de points \(U, V \in \Gamma\) tel que \(W = U - V\).
Preuve. Supposons d'abord que \(U\) et \(V\) soient des points antipodaux de \(\Gamma\). Soient \(P_1\) et \(P_2\) des plans d'appui parallèles passant par eux, de sorte que \(\Gamma\) soit entre eux. Considérons le plan \(P = P_1 - U = P_2 - V\). Ce plan sépare les intérieurs de \(\Gamma - U\) et \(\Gamma - V\). Après avoir pris le symétrique de l'un des ensembles, par exemple \(\Gamma - V\), les ensembles \(\Gamma - U\) et \(-\Gamma + V\) sont dans le même demi-espace délimité par \(P\). Alors \((\Gamma - U) + (-\Gamma + V) = \Delta - W\) est dans ce demi-espace, donc \(0 \in P\) est un point du bord de l'ensemble \(\Delta - W\). Par translation de \(W\), on obtient que \(W\) est un point du bord de \(\Delta\).
Pour la réciproque, soit \(W = U - V\) un point du bord de \(\Delta\), et soit \(\Psi = (\Gamma - U) \cap (\Gamma - V)\). Montrons que \(\Psi = \{0\}\). Évidemment, \(\Psi\) est un ensemble convexe borné et \(0 \in \Psi\). Pour deux points quelconques \(X, Y \in \Psi\), on a \(U + X, V + Y \in \Gamma\) et \(W + (X - Y) = (U + X) - (V + Y) \in \Delta\). Comme \(W\) est un point du bord de \(\Delta\), le vecteur \(X - Y\) ne peut pas avoir la même direction que \(W\). Cela implique que l'intérieur de \(\Psi\) est vide. Supposons maintenant que \(\Psi\) contienne un segment \(S\). Alors \(S + U\) et \(S + V\) sont des parties de faces ou d'arêtes de \(\Gamma\), et ces faces ou arêtes sont parallèles à \(S\). Dans tous les cas, on trouve deux faces, deux arêtes, ou une face et une arête parallèles, ce qui contredit les conditions du problème. Donc \(\Psi = \{0\}\).
Comme \(\Psi = (\Gamma - U) \cap (\Gamma - V)\) est réduit à un point, les intérieurs des corps \(\Gamma - U\) et \(\Gamma - V\) sont disjoints, et il existe un plan \(P\) qui les sépare. Soit \(u\) le vecteur normal de \(P\) dirigé vers le demi-espace délimité par \(P\) qui contient \(\Gamma - U\). Considérons les plans \(P + U\) et \(P + V\) ; ce sont des plans d'appui de \(\Gamma\) passant respectivement par \(U\) et \(V\). Depuis le plan \(P + U\), le vecteur \(u\) pointe vers le demi-espace qui contient \(\Gamma\). Depuis le plan \(P + V\), le vecteur \(u\) pointe vers le demi-espace opposé, qui contient \(\Gamma\). On a donc trouvé deux plans d'appui passant par les points \(U\) et \(V\) tels que \(\Gamma\) soit entre eux.
Pour l'unicité, supposons qu'il existe des points \(U_1, V_1 \in \Gamma\) tels que \(U_1 - V_1 = U - V\). Les points \(U_1 - U\) et \(V_1 - V\) sont dans les ensembles \(\Gamma - U\) et \(\Gamma - V\) séparés par \(P\). Comme \(U_1 - U = V_1 - V\), cela n'est possible que si tous deux sont dans \(P\) ; mais le seul tel point est \(0\). Donc \(U_1 - V_1 = U - V\) implique \(U_1 = U\) et \(V_1 = V\). Le lemme est démontré. \(\square\)
Lemme 2. Soient \(U\) et \(V\) deux points antipodaux, et supposons que le plan \(P\), passant par \(0\), sépare les intérieurs de \(\Gamma - U\) et \(\Gamma - V\). Posons \(\Psi_1 = (\Gamma - U) \cap P\) et \(\Psi_2 = (\Gamma - V) \cap P\). Alors \(\Delta \cap (P + U - V) = \Psi_1 - \Psi_2 + U - V\).
Preuve. Les ensembles \(\Gamma - U\) et \(-\Gamma + V\) sont dans le même demi-espace fermé délimité par \(P\). Donc, pour tous points \(X \in (\Gamma - U)\) et \(Y \in (-\Gamma + V)\), on a \(X + Y \in P\) si et seulement si \(X, Y \in P\). Alors
Une translation de \((U - V)\) termine la preuve du lemme. \(\square\)
Classons maintenant les points du bord \(W = U - V\) de \(\Delta\) selon les types des points \(U\) et \(V\). Dans tous les cas, on choisit un plan \(P\) passant par \(0\) qui sépare les intérieurs de \(\Gamma - U\) et \(\Gamma - V\). On utilise aussi les notations \(\Psi_1 = (\Gamma - U) \cap P\) et \(\Psi_2 = (\Gamma - V) \cap P\).
Cas 1 : \(U\) et \(V\) sont tous deux des sommets de \(\Gamma\). Les corps \(\Gamma - U\) et \(\Gamma - V\) ont un sommet commun, qui est \(0\). Choisissons le plan \(P\) de sorte que \(\Psi_1 = \Psi_2 = \{0\}\). Le lemme 2 donne alors \(\Delta \cap (P + W) = \{W\}\). Donc \(P + W\) est un plan d'appui de \(\Delta\) n'ayant qu'un point commun avec lui, et il n'existe aucun segment de \(\partial\Delta\) contenant \(W\) en son intérieur.
Comme ce cas se produit pour les paires de sommets antipodaux et que chaque paire est comptée deux fois, le nombre de tels points du bord de \(\Delta\) est \(2A\).
Cas 2 : \(U\) est un point intérieur d'une arête \(E_i\) et \(V\) un sommet de \(\Gamma\). Choisissons le plan \(P\) de sorte que \(\Psi_1 = E_i - U\) et \(\Psi_2 = \{0\}\). D'après le lemme 2, \(\Delta \cap (P + W) = E_i - V\). Il existe donc un segment de \(\partial\Delta\) contenant \(W\) en son intérieur, mais aucune région plane de \(\partial\Delta\) ayant cette propriété.
On obtient un résultat analogue si \(V\) appartient à une arête de \(\Gamma\) et \(U\) est un sommet.
Cas 3 : \(U\) et \(V\) sont des points intérieurs d'arêtes \(E_i\) et \(E_j\) respectivement. Soit \(P\) le plan de \(E_i - U\) et \(E_j - V\). Alors \(\Psi_1 = E_i - U\), \(\Psi_2 = E_j - V\) et \(\Delta \cap (P + W) = E_i - E_j\). Le point \(W\) appartient donc à une face en forme de parallélogramme de \(\partial\Delta\).
Le centre du parallélogramme est \(Q_i - Q_j\), le vecteur joignant les milieux. Un couple d'arêtes \((E_i, E_j)\) apparaît donc si et seulement si \(Q_i\) et \(Q_j\) sont antipodaux, ce qui se produit \(2B\) fois.
Cas 4 : \(U\) est à l'intérieur d'une face \(F_i\) et \(V\) est un sommet de \(\Gamma\). Le seul choix possible pour \(P\) est le plan de \(F_i - U\). On a alors \(\Psi_1 = F_i - U\), \(\Psi_2 = \{0\}\) et \(\Delta \cap (P + W) = F_i - V\). C'est une face plane de \(\partial\Delta\), isométrique à \(F_i\).
Pour chaque face \(F_i\), le seul sommet \(V\) possible est le plus éloigné du plan de \(F_i\).
Si \(U\) est un sommet et \(V\) appartient à la face \(F_i\), on obtient de même que \(W\) appartient à une face \(-F_i + U\), elle aussi isométrique à \(F_i\). Chaque face de \(\Gamma\) a donc deux copies sur \(\partial\Delta\), une translatée et une symétrique.
Cas 5 : \(U\) appartient à une face \(F_i\) de \(\Gamma\) et \(V\) à une arête ou une face \(G\). Dans ce cas, les objets \(F_i\) et \(G\) doivent être parallèles, ce qui est exclu.
Tous les points de \(\partial\Delta\) appartiennent donc à des polygones plans (cas 3 et 4), à un nombre fini de segments (cas 2) et à des points (cas 1). Donc \(\Delta\) est bien un polyèdre. Calculons maintenant les nombres de ses sommets, arêtes et faces.
Les sommets sont obtenus dans le cas 1 ; leur nombre est \(2A\).
Les faces sont obtenues dans les cas 3 et 4. Le cas 3 donne \(2B\) faces parallélogrammes. Le cas 4 donne \(2\ell\) faces.
Calculons le nombre d'arêtes de \(\Delta\) à partir des degrés (nombres de côtés) des faces de \(\Gamma\). Soit \(d_i\) le degré de la face \(F_i\). La somme des degrés vaut le double du nombre d'arêtes, donc \(d_1 + d_2 + \cdots + d_\ell = 2m\). La somme des degrés des faces de \(\Delta\) vaut \(2B \cdot 4 + 2(d_1 + d_2 + \cdots + d_\ell) = 8B + 4m\), donc le nombre d'arêtes de \(\Delta\) est \(4B + 2m\).
En appliquant la formule d'Euler à \(\Gamma\) et à \(\Delta\), on a \(n + \ell = m + 2\) et \(2A + (2B + 2\ell) = (4B + 2m) + 2\). La conclusion en découle :