Shortlist 2011, C3

Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : non indiqué

Concepts : Invariants et monovariants · Géométrie combinatoire : enveloppe convexe, points du réseau

Solution officielle : Shortlist officielle 2011 (avec solutions), p. 31 (page 32 du PDF)

Problème 2 de l'OIM 2011

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

Figures reprises du livret officiel de la Shortlist.

Énoncé

Let \(\mathcal{S}\) be a finite set of at least two points in the plane. Assume that no three points of \(\mathcal{S}\) are collinear. By a windmill we mean a process as follows. Start with a line \(\ell\) going through a point \(P \in \mathcal{S}\). Rotate \(\ell\) clockwise around the pivot \(P\) until the line contains another point \(Q\) of \(\mathcal{S}\). The point \(Q\) now takes over as the new pivot. This process continues indefinitely, with the pivot always being a point from \(\mathcal{S}\).

Show that for a suitable \(P \in \mathcal{S}\) and a suitable starting line \(\ell\) containing \(P\), the resulting windmill will visit each point of \(\mathcal{S}\) as a pivot infinitely often.

Indices : les idées clés

• Invariant : en orientant la droite, le nombre de points de chaque côté ne change pas au cours du processus (sauf aux instants où la droite contient deux points).
• Droite équilibrée : par un argument de valeurs intermédiaires en tournant de \(180^\circ\), par chaque point passe une droite qui partage \(\mathcal{S}\) en deux moitiés (ou en \(n - 1\) et \(n\) points si \(\lvert \mathcal{S} \rvert = 2n\)).
• Unicité dans chaque direction (géométrie combinatoire) : une translation parallèle romprait l'équilibre ; quand le moulin est parallèle à la droite équilibrée passant par \(T\), il passe donc par \(T\).

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2011 (une solution et une remarque).

Solution

Orientons la droite tournante et distinguons ses deux côtés : le côté orange et le côté bleu. Quand le pivot passe d'un point \(T\) à un point \(U\), après le changement, \(T\) est du côté où se trouvait \(U\) avant. Le nombre d'éléments de \(\mathcal{S}\) du côté orange et celui du côté bleu restent donc les mêmes pendant tout le processus (sauf aux instants où la droite contient deux points).

Considérons d'abord le cas où \(\lvert \mathcal{S} \rvert = 2n + 1\) est impair. Par tout point \(T \in \mathcal{S}\) passe une droite qui a \(n\) points de chaque côté. Pour le voir, choisissons une droite orientée passant par \(T\) et ne contenant aucun autre point de \(\mathcal{S}\), et supposons qu'elle ait \(n + r\) points du côté orange. Si \(r = 0\), c'est fini ; supposons donc \(r \neq 0\). Quand la droite tourne de \(180^\circ\) autour de \(T\), le nombre de points de son côté orange change de \(1\) chaque fois qu'elle passe par un point ; après \(180^\circ\), ce nombre vaut \(n - r\). Il y a donc un instant intermédiaire où le côté orange, et donc aussi le côté bleu, contient \(n\) points.

Choisissons le point \(P\) arbitrairement, et prenons comme état initial du moulin une droite passant par \(P\) ayant \(n\) points de \(\mathcal{S}\) de chaque côté. Montrons que, pendant une rotation de \(180^\circ\), la droite du moulin passe par chaque point de \(\mathcal{S}\) comme pivot. Prenons un point \(T\) de \(\mathcal{S}\) et une droite \(\ell\) passant par \(T\) qui partage \(\mathcal{S}\) en deux moitiés égales. Le point \(T\) est l'unique point de \(\mathcal{S}\) par lequel une droite de cette direction peut partager \(\mathcal{S}\) en deux moitiés égales (une translation parallèle romprait l'équilibre). Donc, quand la droite du moulin est parallèle à \(\ell\), c'est \(\ell\) elle-même, et elle passe par \(T\).

Supposons ensuite \(\lvert \mathcal{S} \rvert = 2n\). Comme dans le cas impair, pour tout \(T \in \mathcal{S}\), il existe une droite orientée passant par \(T\) avec \(n - 1\) points du côté orange et \(n\) points du côté bleu. Prenons une telle droite orientée passant par un point \(P\) quelconque comme état initial du moulin.

Montrons que, pendant une rotation de \(360^\circ\), la droite du moulin passe par chaque point de \(\mathcal{S}\) comme pivot. Prenons un point \(T\) de \(\mathcal{S}\) et une droite orientée \(\ell\) passant par \(T\) qui partage \(\mathcal{S}\) en \(n - 1\) points du côté orange et \(n\) du côté bleu. Là encore, une translation parallèle changerait les nombres de points des deux côtés ; donc, quand la droite du moulin est parallèle à \(\ell\) avec la même orientation, elle passe par \(T\). \(\blacksquare\)

Remarque

On peut raccourcir la solution ainsi. Supposons \(\lvert \mathcal{S} \rvert = 2n + 1\). Considérons une droite \(\ell\) qui partage \(\mathcal{S}\) en deux moitiés égales ; cette droite est unique dans sa direction et contient un point \(T \in \mathcal{S}\). Considérons le moulin qui part de cette droite. Après une rotation de \(180^\circ\), la droite revient à la même position, mais le côté orange devient bleu et inversement. Chaque point a donc dû être pivot à un moment, puisque c'est la seule façon pour un point de passer d'un côté à l'autre.

Supposons maintenant \(\lvert \mathcal{S} \rvert = 2n\). Considérons une droite ayant \(n - 1\) et \(n\) points de part et d'autre ; elle contient un point \(T\). Considérons le moulin qui part de cette droite. Après une rotation de \(180^\circ\), la droite du moulin contient un autre point \(R\), et chaque point différent de \(T\) et \(R\) a changé de côté. Le moulin est donc passé par tous les points.