Qui veut partager des millions ?

Le 21 mars 2011  - Ecrit par  Patrick Popescu-Pampu Voir les commentaires (2)

« Étant donnés deux millions de points dans un plan, montrer qu’il existe une droite qui partage ce plan en deux parties, dont chacune contient exactement un million de points. »

J’ai appris le problème précèdent au club de préparation aux olympiades de mathématiques, à Bucarest [1]. C’était au début de ma cinquième, lors de ma première participation à ce club, à l’automne 1985 si je me rappelle bien. Je n’ai pas eu le temps de réfléchir moi-même à ce problème, mais seulement d’entendre l’énoncé et, tout de suite après, une solution [2]. Je fus ébloui par le contraste entre l’énormité des données (deux millions ce n’est pas rien !) et la brièveté fulgurante de la preuve. La voici (que celui qui veut y réfléchir tout seul reprenne la lecture plus tard) :

Comme il y a un nombre fini de points, il y a aussi un nombre fini de droites qui les joignent. Prenons alors une direction qui n’est parallèle à aucune d’entre elles. Puis choisissons une droite ayant cette direction et qui se trouve loin des points, les laissant tous d’un seul côté. Faisons-là ensuite bouger parallèlement à elle-même, d’un mouvement qui la rapproche des points. De temps en temps elle passera par l’un d’entre eux. Mais à chaque fois par un seul, car notre hypothèse est que la droite de départ n’est parallèle à aucune des droites joignant deux des points. Lors de son mouvement elle aura dépassé d’abord exactement un point, puis deux, puis trois ... Arrêtons-nous après un million. Le problème est résolu !

On pourrait bien sûr poser le problème en termes plus généraux, en remplaçant le nombre de deux millions par le syntagme « un nombre pair ». Mais ceci ferait perdre l’impact qu’a sur l’imagination ce grand nombre. Je dirais qu’une partie importante de l’arôme du problème disparaîtrait ainsi [3].

Par exemple, j’ai eu alors le sentiment très puissant que la complexité apparente du monde pouvait en un certain sens être apprivoisée par la pensée. Ce sentiment a été, je crois, l’une des raisons principales qui m’ont fait désirer devenir chercheur en mathématiques. J’y repense maintenant que je suis à la fois chercheur et enseignant, en interaction avec des étudiants qui cherchent leur voie. Cela me fait méditer aux raisons qui m’ont fait choisir la mienne. Je réalise que le problème précédent illustre bien l’importance de poser à nos élèves des questions étonnantes, inhabituelles, aux preuves frappantes de simplicité inventive. Ce type de problèmes peut parler à l’imagination des élèves, leur faire sentir qu’ils auront une vie intérieure riche en s’adonnant aux mathématiques.

Il ne faut pas croire que l’on trouve des solutions si courtes ou élégantes à tous les problèmes auxquels on s’intéresse, bien au contraire. Mais espérer trouver une telle solution est, je crois, un moteur important de la recherche mathématique.


Je voudrais revenir à la preuve précédente et commenter certains aspects qui m’étaient invisibles à l’époque. Cette preuve montre qu’en fait, chaque fois qu’on fixe deux nombres dont la somme vaut deux millions, on pourra trouver une droite qui partage le plan en deux parties qui contiennent exactement ces nombres-là de points. Demander d’obtenir des nombres égaux répondait de ce point de vue à un besoin esthétique de symétrie.

C’est ce que je croyais au début de ma réflexion actuelle sur ce problème. Mais en fait il y a une autre raison pour laquelle le bon énoncé demande de partager en deux parties égales.

En effet, on peut se poser la même question dans les trois géométries de dimension deux [4] : dans le plan euclidien usuel, dans le plan hyperbolique et enfin sur la sphère. Dans le plan hyperbolique [5], on peut encore partager en deux parties ayant n’importe quels nombres de points préétablis, bien sûr sous la contrainte que leur somme fasse deux millions. La même preuve qu’avant marche si on remplace les familles de droites de direction donnée dans le plan euclidien par les familles de droites passant par le même point sur le cercle à l’infini du plan hyperbolique.

Mais la situation est différente sur la sphère ! Là, le rôle des droites dans le plan est joué par les grands cercles. On en voit des arcs sur les oranges suivantes.

On se donne donc encore deux millions de points, mais sur une sphère. Ce qui change, c’est qu’il y a maintenant des situations où n’importe quelle droite (grand cercle) qui ne passe par aucun des points, en laisse un million d’un côté et un million de l’autre. Cela arrive lorsque les points apparaissent par couples antipodaux. Ce qui montre que le seul partage qui pourrait être toujours possible dans les trois géométries à la fois est en deux parties égales. Eh bien, un tel partage égalitaire est aussi possible sur la sphère !

Voici comment le voir. On va procéder par analogie avec la preuve précédente. Deux grands cercles se coupent toujours en un couple de points antipodaux, donc on n’a plus de notion de parallélisme. En revanche, on a une notion analogue à celle de famille de droites de direction fixée : c’est celle de famille de cercles passant par le même couple de points antipodaux. On appellera une telle famille un pinceau, et les points communs des cercles qui le composent seront ses pôles (on pourra penser aux méridiens sur un globe terrestre, passant tous par les pôles, et on pourra aussi regarder à nouveau les oranges).

Dans la preuve précédente on considérait une famille de droites telle qu’aucune d’entre elles ne passe par deux des points donnés. Ici on choisira un pinceau tel qu’aucun des cercles qui le composent ne contienne de couple de points non-antipodaux de notre ensemble. Ceci est possible, car deux points non-antipodaux déterminent un unique grand cercle, et qu’il n’y a donc qu’un nombre fini de grands cercles passant par des couples de points non-antipodaux de notre ensemble. Il suffit de choisir les pôles du pinceau en dehors d’eux.

Fixons ensuite l’un des cercles du pinceau qui ne passe par aucun des points donnés, et faisons-lui faire un demi-tour tel qu’à chaque moment il reste dans le pinceau. Suivons ce qui se passe pendant ce demi-tour avec l’un des hémisphères bordés par le cercle (on pourra penser au mouvement de la partie diurne du globe pendant une demi-journée, ou bien au passage d’une nouvelle lune à la pleine lune suivante). On voit alors qu’il existe une situation intermédiaire pour laquelle l’hémisphère contient la moitié des points. En effet, à chaque fois qu’on passe par une position du cercle qui contient des points de l’ensemble donné, le nombre des points de l’hémisphère soit varie de un (si le cercle est passé par un seul point), soit reste inchangé (si le cercle est passé par un couple antipodal). Mais lorsque l’on a fait le demi-tour, on a échangé les deux hémisphères initiaux. On est donc passé par toutes les valeurs intermédiaires entre deux nombres dont la somme fait deux millions, et en particulier par la moitié de ce nombre. Le partage en deux parties égales est donc encore possible !

Notes

[1Il s’agissait, tous les samedis matin, d’une rencontre des élèves de Bucarest qui avaient été récompensés l’année précédente aux olympiades de mathématiques. Le problème précédent avait été proposé par le professeur Florian Colceag.

[2Cette solution a été expliquée par Teodor Bănică, à présent lui aussi enseignant-chercheur en France.

[3De plus, l’élève perdrait l’occasion d’extraire de la pluralité de propriétés des données, celles qui jouent un rôle dans le problème envisagé. Ici, il ne nous importe pas que deux millions soit divisible par cinq, uniquement qu’il soit pair.

[4Plus précisément, en termes techniques, dans les trois surfaces riemanniennes homogènes, isotropes et simplement connexes.

[5Le lecteur curieux pourra la découvrir dans un article d’Etienne Ghys sur ce site.

Partager cet article

Pour citer cet article :

Patrick Popescu-Pampu — «Qui veut partager des millions ?» — Images des Mathématiques, CNRS, 2011

Crédits image :

Image à la une - La photo a été prise par moi.

Commentaire sur l'article

  • Qui veut partager des millions et des millions ?

    le 24 mars 2011 à 22:47, par Laurent Tournier

    On peut signaler que cette propriété de découpage peut être renforcée en exploitant davantage la deuxième dimension : supposons donnés non plus seulement deux millions de points mais quatre millions, deux millions de bleus et deux millions de rouges. Alors il existe une droite qui partage le plan en deux parties, dont chacune contient exactement un million de points bleus mais aussi un million de points rouges. Il faut cependant alors autoriser la droite à passer par certains points qui dans ce cas comptent au choix pour l’une ou l’autre des parties (autrement dit, chaque partie contient moins de la moitié des points de chaque couleur).

    Il s’agit d’un cas particulier du théorème du sandwich au jambon.

    Une preuve dans le même esprit que celle du billet est d’ailleurs possible, bien que moins brève, en suivant le principe suivant. Par la méthode décrite dans le billet on peut trouver une droite qui divise l’ensemble des points rouges en deux parties égales. On peut de plus se convaincre que l’on peut déplacer continûment cette droite de façon à lui faire faire un demi-tour et à ce que tout au long du déplacement la propriété de division en parties égales (au sens large ci-dessus) pour les points rouges reste vraie (*). Regardons alors comment évolue, durant ce demi-tour, la différence entre les nombres de points bleus situés (strictement) d’un côté et de l’autre de la droite : entre le début et la fin, ce nombre est remplacé par son opposé. Il y a donc au moins un instant où ce nombre vaut 0 ou « saute » en changeant de signe. À cet instant, la droite résout le problème (dans le cas d’un saut, cette conclusion demande quelques instants de réflexion).

    (*) Par exemple : faire tourner la droite à vitesse constante d’abord autour d’un point quelconque puis, à chaque fois que la droite rencontre un ou plusieurs points rouges, prendre pour nouveau centre de rotation un point de la droite tel que la répartition stricte (un million de points rouges chaque côté) sera rétablie immédiatement après [À savoir un point qui sépare les points rouges de la droite en un groupe de N-n et un groupe de N-n’ si N=un million et n, n’ sont les nombres de points d’un côté et de l’autre de la droite, dans le sens approprié : faire un dessin !]. Après un demi-tour, la droite est parallèle à sa position initiale et il n’y a aucun point rouge entre les deux donc une translation achève de ramener l’une à l’autre.

    Répondre à ce message
  • Qui veut partager des millions ?

    le 26 mars 2011 à 15:35, par Arnaud Lionnet

    Ce problème est aujourd’hui encore donné à l’oral de Polytechnique. Mais avec beaucoup moins d’ambition cependant : 500 points seulement.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM