Shortlist 2013, C2

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

Concepts : Géométrie combinatoire : enveloppe convexe, points du réseau · Récurrence et constructions récursives · Principe extrémal

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

Problème 2 de l'OIM 2013

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

Énoncé

In the plane, \(2013\) red points and \(2014\) blue points are marked so that no three of the marked points are collinear. One needs to draw \(k\) lines not passing through the marked points and dividing the plane into several regions. The goal is to do it in such a way that no region contains points of both colors.

Find the minimal value of \(k\) such that the goal is attainable for every possible configuration of \(4027\) points.

Indices : les idées clés

• L'exemple : \(2013\) points rouges et \(2013\) bleus alternés sur un cercle ; chacun des \(4026\) arcs doit être coupé, et une droite coupe le cercle en au plus deux points, donc \(k \geq 2013\).
• Isoler une paire avec deux droites : deux droites parallèles à \(AB\), très proches, séparent \(A\) et \(B\) de tous les autres points.
• Enveloppe convexe : un sommet (ou un côté) de l'enveloppe convexe s'isole avec une seule droite ; on apparie le reste, ou l'on fait une récurrence (solution 2).

Solutions

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

Réponse : \(k = 2013\).

Solution 1

Montrons d'abord par un exemple que \(k \geq 2013\). Marquons \(2013\) points rouges et \(2013\) points bleus alternativement sur un cercle, et un point bleu de plus n'importe où dans le plan. Le cercle est découpé en \(4026\) arcs, dont chacun a des extrémités de couleurs différentes. Si le but est atteint, chaque arc doit donc être coupé par l'une des droites tracées. Comme une droite contient au plus deux points du cercle, il faut au moins \(\frac{4026}{2} = 2013\) droites.

Il reste à montrer qu'on peut atteindre le but avec \(2013\) droites. Remarquons d'abord que, pour deux points \(A\) et \(B\) de même couleur, on peut tracer deux droites qui séparent ces points de tous les autres : il suffit de prendre deux droites parallèles à \(AB\), de part et d'autre de \(AB\) et assez proches ; les seuls points entre ces deux droites sont alors \(A\) et \(B\).

Soit maintenant \(P\) l'enveloppe convexe de tous les points marqués. Deux cas sont possibles.

Cas 1 : \(P\) a un sommet rouge \(A\). On peut alors tracer une droite qui sépare \(A\) de tous les autres points, regrouper les \(2012\) autres points rouges en \(1006\) paires, et séparer chaque paire des autres points par deux droites. On utilise ainsi \(2013\) droites.

Cas 2 : tous les sommets de \(P\) sont bleus. Considérons deux sommets consécutifs \(A\) et \(B\) de \(P\). On peut séparer ces deux points des autres par une droite parallèle à \(AB\). Puis, comme dans le cas précédent, on regroupe les \(2012\) autres points bleus en \(1006\) paires et l'on sépare chaque paire des autres points par deux droites. On utilise à nouveau \(2013\) droites. \(\blacksquare\)

Remarque 1. Au lieu de l'enveloppe convexe, on peut simplement prendre une droite contenant deux points marqués \(A\) et \(B\) telle que tous les autres points marqués soient du même côté. Si l'un des points \(A\), \(B\) est rouge, on procède comme dans le cas 1 ; sinon, ils sont tous deux bleus, et l'on procède comme dans le cas 2.

Solution 2

Donnons une autre preuve du fait que \(k = 2013\) suffit. On prouve même l'énoncé plus général suivant :

Si \(n\) points du plan, dont trois ne sont jamais alignés, sont coloriés arbitrairement en rouge et en bleu, alors \(\lfloor n/2 \rfloor\) droites suffisent pour atteindre le but.

On procède par récurrence sur \(n\). Si \(n \leq 2\), c'est évident. Supposons \(n \geq 3\), et considérons une droite \(\ell\) contenant deux points marqués \(A\) et \(B\) telle que tous les autres points marqués soient du même côté de \(\ell\) ; par exemple, toute droite portant un côté de l'enveloppe convexe convient.

Retirons un instant les points \(A\) et \(B\). Par hypothèse de récurrence, pour la configuration restante, il suffit de tracer \(\lfloor n/2 \rfloor - 1\) droites pour atteindre le but. Remettons maintenant \(A\) et \(B\). Trois cas sont possibles.

Cas 1 : \(A\) et \(B\) ont la même couleur. On peut tracer une droite parallèle à \(\ell\) qui sépare \(A\) et \(B\) des autres points. La configuration de \(\lfloor n/2 \rfloor\) droites obtenue convient évidemment.

Cas 2 : \(A\) et \(B\) sont de couleurs différentes, mais séparés par une droite déjà tracée. La même droite parallèle à \(\ell\) convient encore.

Cas 3 : \(A\) et \(B\) sont de couleurs différentes et dans une même région délimitée par les droites tracées. Par hypothèse de récurrence, cette région ne contient pas d'autre point de l'une des deux couleurs ; sans perte de généralité, le seul point bleu qu'elle contient est \(A\). Il suffit alors de tracer une droite séparant \(A\) de tous les autres points.

L'hérédité est donc établie. \(\blacksquare\)

Remarque

Remarque 2. On peut poser une question plus générale, en remplaçant \(2013\) et \(2014\) par des entiers strictement positifs quelconques \(m\) et \(n\), avec par exemple \(m \leq n\). Notons \(f(m, n)\) la réponse. Avec les idées de la solution 1, on montre que \(m \leq f(m, n) \leq m + 1\) ; de plus, si \(m\) est pair, alors \(f(m, n) = m\). En revanche, pour tout \(m\) impair, il existe un \(N\) tel que \(f(m, n) = m\) pour tout \(m \leq n \leq N\), et \(f(m, n) = m + 1\) pour tout \(n > N\).