La réponse du jeudi (49) : séparer 2016 points | CultureMath
La réponse du jeudi (49) : séparer 2016 points
Publié le 21/01/2016

Vous pouvez retrouver cette question au format pdf.

Question du jeudi #49 : On place $2016$ points dans le plan. Montrer que l'on peut trouver une droite qui sépare le plan en deux régions contenant $1008$ points chacune.


Il y a plusieurs manières de répondre à cette question, l'important étant de ne pas rentrer dans les détails géométriques de la configuration.

Choisissons une droite $\Delta$ ne contenant aucun des $2016$ points donnés $P_1, P_2, \ldots, P_{2016}$ et telle que la parallèle $D_i$ à $\Delta$ passant par $P_i$ ne rencontre jamais d'autre point $P_j$.
Cela est possible car il suffit de prendre $\Delta$ qui ne soit parallèle à aucune des droites $(P_i\,P_j)$, qui sont en nombre fini (il y en a au plus $\binom {2016} 2 = 2\,031\,120$). Quitte à translater $\Delta$, on peut même supposer que tous les $(P_i)$ sont du même côté de $\Delta$ (on appellera ce côté le côté intéressant).

Maintenant, pour chaque nombre réel $r \geq 0$, considérons la droite $\Delta(r)$, parallèle à $\Delta$, qui est du côté intéressant et telle que la distance entre $\Delta(r)$ et $\Delta$ soit exactement $r$ (en particulier, $\Delta = \Delta(0)$).

D'après la propriété de $\Delta$, les $\Delta(r)$ ne contiennent jamais plus d'un point $P_i$. Ainsi, lorsque $r$ augmente, le nombre $N(r)$ de points compris strictement entre $\Delta$ et $\Delta(r)$ ne croît que d'une unité à chaque fois. Puisqu'il sera égal à $2016$ pour $r$ assez grand, il devra bien être égal à $1008$ pour un certain $r_0$, et la droite $\Delta(r_0)$ répond à la question.

Voici une illustration de cette stratégie avec $10$ points.

(Remarquons que l'on peut également faire une telle preuve « par balayage » en choissisant un point $O$ tel que $O$, $P_i$ et $P_j$ ne soient jamais alignés et en considérant les différentes droites passant par $O$).
 

 
 
 
 
 
Dernières publications