Aller au contenu

Shortlist 2015, C2

Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : Netherlands

Concepts : Géométrie combinatoire : enveloppe convexe, points du réseau · Double comptage · Principe des tiroirs · Graphes : degrés, chemins, arbres

Solution officielle : Shortlist officielle 2015 (avec solutions), p. 27 (page 28 du PDF)

Problème 1 de l'OIM 2015

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

Figures reprises du livret officiel de la Shortlist.

Énoncé

Let \(V\) be a finite set of points in the plane. We say that \(V\) is balanced if for any two distinct points \(A, B \in V\), there exists a point \(C \in V\) such that \(AC = BC\). We say that \(V\) is center-free if for any distinct points \(A, B, C \in V\), there does not exist a point \(P \in V\) such that \(PA = PB = PC\).

(a) Show that for all \(n \geq 3\), there exists a balanced set consisting of \(n\) points.

(b) For which \(n \geq 3\) does there exist a balanced, center-free set consisting of \(n\) points?

Indices : les idées clés
  • Constructions géométriques : sommets d'un polygone régulier (cas impair), centre et triangles équilatéraux inscrits (cas pair).
  • Double comptage : on compte les couples (paire \(\{A, B\}\), point \(C\) équidistant).
  • Principe des tiroirs : un point est associé à au moins \(\frac{n}{2}\) paires, et deux de ces paires partagent un point.
  • Graphes (remarque (b)) : relecture de l'argument en termes de degrés entrants.
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2015 (une solution et deux remarques).

Réponse à la partie (b). Tous les entiers impairs \(n \geq 3\).

Solution 1

Partie (a). Cas \(n\) impair. On considère un polygone régulier à \(n\) sommets \(A_1, A_2, \ldots, A_n\) (dans le sens trigonométrique) et \(V = \{A_1, \ldots, A_n\}\). Montrons que \(V\) est équilibré. Pour deux sommets distincts \(A_i\) et \(A_j\), soit \(k \in \{1, 2, \ldots, n\}\) la solution de \(2k \equiv i + j \pmod{n}\) (elle existe car \(n\) est impair). Comme \(k - i \equiv j - k \pmod{n}\), on a \(A_i A_k = A_j A_k\).

Cas \(n\) pair. On considère un polygone régulier à \(3n - 6\) sommets, de centre \(O\), de sommets \(A_1, \ldots, A_{3n-6}\) dans le sens trigonométrique, et l'on pose \(V = \{O, A_1, A_2, \ldots, A_{n-1}\}\) (\(n\) points). Pour deux sommets \(A_i\) et \(A_j\), on a toujours \(OA_i = OA_j\). Considérons maintenant \(O\) et un sommet \(A_i\). L'angle au centre entre \(A_i\) et \(A_{i + n/2 - 1}\) vaut \(\left(\frac{n}{2} - 1\right) \cdot \frac{360^\circ}{3n - 6} = 60^\circ\), donc le triangle \(O A_i A_{n/2 - 1 + i}\) est équilatéral pour tout \(i \leq \frac{n}{2}\). Par conséquent :

  • si \(i \leq \frac{n}{2}\), on a \(O A_{n/2 - 1 + i} = A_i A_{n/2 - 1 + i}\) ;
  • si \(i > \frac{n}{2}\), on a \(O A_{i - n/2 + 1} = A_i A_{i - n/2 + 1}\).

Donc \(V\) est équilibré. (Voir la figure 1 pour l'exemple \(n = 10\).)

Figure (solution)

Partie (b). Montrons qu'il existe un ensemble équilibré et sans centre à \(n\) points pour tout \(n \geq 3\) impair, et qu'il n'en existe pas pour \(n \geq 3\) pair.

Cas \(n\) impair. Soit \(V\) l'ensemble des sommets d'un polygone régulier à \(n\) sommets. On a vu en (a) qu'il est équilibré. Il est aussi sans centre : si \(PA = PB = PC\) pour trois sommets distincts \(A\), \(B\), \(C\), alors \(P\) est le centre du cercle circonscrit au polygone, qui n'appartient pas à \(V\).

Cas \(n\) pair. Supposons que \(V\) soit un ensemble équilibré et sans centre de cardinal \(n\) pair, et cherchons une contradiction. Pour deux points distincts \(A, B \in V\), on dit qu'un point \(C \in V\) est associé à la paire \(\{A, B\}\) si \(AC = BC\). Il y a \(\frac{n(n-1)}{2}\) paires, chacune ayant au moins un point associé ; par le principe des tiroirs, il existe un point \(P \in V\) associé à au moins

\[\left\lceil \frac{n(n-1)}{2n} \right\rceil = \left\lceil \frac{n-1}{2} \right\rceil = \frac{n}{2}\]

paires. Aucune de ces \(\frac{n}{2}\) paires ne contient \(P\), donc leur réunion est contenue dans les \(n - 1\) autres points. Elles ne peuvent donc pas être deux à deux disjointes (il faudrait \(n\) points) : deux d'entre elles partagent un point, disons \(\{A, B\}\) et \(\{A, C\}\). Alors \(PA = PB = PC\), ce qui contredit l'hypothèse « sans centre ». \(\blacksquare\)

Remarques

Remarque (a) (une construction générale). On peut construire de nombreux exemples en plaçant des triangles équilatéraux dans un cercle. Soit \(O\) le centre d'un cercle et \(A_1, B_1, \ldots, A_k, B_k\) des points distincts du cercle tels que chaque triangle \(O A_i B_i\) soit équilatéral. Alors \(V = \{O, A_1, B_1, \ldots, A_k, B_k\}\) est équilibré (cardinal impair). Pour un cardinal pair, on ajoute trois points \(C\), \(D\), \(E\) sur le cercle tels que les triangles \(OCD\) et \(ODE\) soient équilatéraux (voir la figure 2 ci-dessus) : \(V = \{O, A_1, B_1, \ldots, A_k, B_k, C, D, E\}\) est équilibré.

Remarque (b) (version en termes de graphes). Soit \(V\) un ensemble équilibré et sans centre de \(n\) points. Pour toute paire de points distincts \(A, B \in V\) et tout \(C \in V\) tel que \(AC = BC\), on trace les arêtes orientées \(A \to C\) et \(B \to C\). Toutes les paires engendrent au moins \(n(n-1)\) arêtes orientées ; comme l'ensemble est sans centre, ces arêtes sont distinctes. On obtient donc un graphe dans lequel deux sommets quelconques sont reliés dans les deux sens. Chaque sommet a alors exactement \(n - 1\) arêtes entrantes, qui arrivent par paires ; donc \(n - 1\) est pair, et \(n\) est impair.