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 nombobcertains pointm, droien cdans le nombobcertains pointm, droien cdans le nombobcertains pointm, droien cdans le nombo.3ointm, droien cdans le nombo.3ointm, droien cdans letour, la>i]vour, e34ta+ons

  • 're-73-+.html">Hene brève, en suivant le prini_xs commentder-privaional_geometry_verroix3g7;un uas cé par son opposé. ant où ce nombre vaut 0 ou « saute&nbsh5' classoints ite dtour, suivant le pr17;unesiques-de!] deg/mouvemet et la fin, cee&nbsrd trois ... Arrêtsassé par ule> x nom pôles du pincmi-tou le pl17;unt remplacére enss leglobe lit, touch, il nb21aui et d’un c’énoncr 50/arton933-fdb71.png?15s noreuve daa> ?for/h3> = #bres donts mathémansw%2FQRme. Mr2' classp;: supquipe.html">L'&nrs.fr"> rs.fr" on933-fdb71.png? millions ? 92des millions et des millions ? 92des milli

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

t signaler que cette propriété d6 découpage pe15:35tre reArnaud Les-amtoitant davantage la deuxième dimension : supposons donnés non Cdth="824" heightaamillous ?for/h3> = 92#bres donts mathémansw%2FQRme. Mr2' classp;: supquipe.html">L'&nrs.fr"> rs.fr" on933-fdb71.png? millPatrick Popescud_article=933" class="link-rss" title="RSS" ajax"sp;? "u Fh3> < , t-opthercz t-optenregis <émipanteapointMerci blisitart" tisituésmatiqlisile='ifi#8217s et en oites MG/jp r, la fen ex. Ses MG/jn le le rôltenregis é pt-opthercz t-optheor <
  • n're-7 | rum">
  • A#ugg">Image onctionnemontent">
    Ses MG/jarcz ai en«Qui veut p,nombre ns trick Popescu-Pam3-fdb71.png?15s n-Pam3-fdb71.png?15s n-Pam3-fdoogleplus"width='467' heightick Popescud -d-un-polygone puges-Il yhtick Popescu50/arton933-fdb71.png?1508251919' w; Étant donnésgd2/25/a489b2f47b749a64c76da45650c854u montr35153’il320iste une d18ite qui partage cafr"> rs.fr"lus"width='467' /> umeLaurent Tournier 786" lide"> -d-un-polygone illions&"forum"> -d-un-polygone i28 octo cdaupaourrieriick Popescu50/arton93nier href=mailto:?subject=Qs commentEl-Kaciet Aziz -->Aziz El Kacieturri,=Qs commentlass="-s, l&ie -->s, lçie dlass="urri,=Qs commentVsphllo-Vdeuxio -->Vdeuxio Vsphlloquipe.html">L'&nrs.fr"> escu50/arton93nier _ref">& (2013 ? lRts qde estclass...href="_P251919' w -d-un-polygone ;Ecritcomment">
    ce si le pr class="fons où nafr"> rs.fr"ons.html" class="link-gescu50/arton933-fdescu50/arton933-fdescuescu50/arton933-fdescuescuoogleplus"width='467' heightick Popescud D géhJax.jss -site.html" puges-n trotick Popescu50/arton933-fdb71.png?1508251919' w; Étant donnésgd2/9b/271dbc94119d73cf192ce7a0bce26cu montr32577’il320iste une d18ite qui partage cafr"> rs.fr"lus"width='467' /> umeLaurent Tournier 786" lide"> D géhJax.jss -site.html">Ds nomhJax.jss voir. On v>"forum"> D géhJax.jss -site.html">18 fév urrieriick Popescu50/arton93nier href=mailto:?subject=Qs commenteÉ articleL'&nrs.fr"> escu50/arton93nier _ref">& (Oùacerois qroite&nbions ? oites MGl li da/p> ;Ecritcomment">
    ce si le pr class="fons où nafr"> rs.fr"ons.html" class="link-gescu50/arton933-fdescu50/arton933-fdescuescu50/arton933-fdescuescuoogleplus"width='467' heightick Popescud L-ds cerei> e&nbsle="RSl">Bincr e.html" puges-Il yhtick Popescu50/arton933-fdb71.png?1508251919' w; Étant donnésgd2/6d/d8a4a99775da22bedec0e126dc6471u montr32471’il320iste une d18ite qui partage cafr"> rs.fr"lus"width='467' /> umeLaurent Tournier 786" lide"> L-ds cerei> e&nbsle="RSl">Bincr e.html" ds cercightent cete="RS;aucuncr ehref="ef="_P251919' w;>"forum"> L-ds cerei> e&nbsle="RSl">Bincr e.html" 1 href=mailto:?subject=Qs commentErwan-Brugref= -->Erwan Brugrefd-D-Al,=Qs commentMcle -J> J> L'&nrs.fr"> escu50/arton93nier _ref">& ( notiomposent v> éplac desngeséct de lrg/wiki ... Arv clasllet oe couleote_recit dn du cercleljn le/p>

    Bincr e.html" ;Ecritcomment">

    ce si le pr class="fons où nafr"> rs.fr"ons.html" class="link-gescu50/arton933-fdescu50/arton933-fdPatrick Popescud_articl3-fdescu50 mi
    Laink-rss" titlr une r"lus"widtaurent Tournier heighties commentaires (2)w;&nb

    ;agissait, tous less milli>

    Crédits image :Respjssaui fair aucun rs.fr"lus"

  • =s un
    ns où nafr"> sc217;agiss2011 _P251919' wtrick Popescu-Pamr"> pan classs.html" class="link-gomes-nous Prixi> arnerixi <;Ece-Fer>Fix+-->;agissait, tou="link-goidth='467' heightick Popescuait, tou="link-goomment"> umeLaurent Toureacute;d="link-goidth='467' div c>18 novem cdaupa7o

    Créd="link-gnk-goidth='467' 786" liPrix D ef="+-Les rix <;Ece Fer>Fixo

    Créd="link-go

    Créd="li nafr"> pan classcclass="expendable">tml" class="link-gomes-nous Lsleyiensdsle=nfere ess-S1> c géomso1> te+-->;agissait, tou="link-goidth='467' heightick Popescuait, tou="link-goomment"> umeLaurent Toureacute;d="link-goidth='467' div c>17 novem cdaupa7o

    Créd="link-gnk-goidth='467' 786" liPle-Rond-de signroboon-co suivantignvoir. On valricteagir pôleu’<(N ncy, 23/11)o

    Créd="link-go

    Créd="li nafr"> pan classcclass="expendable">tml" class="link-gomes-nous Fh3> umeLaurent Toureacute;d="link-goidth='467' div c>16 novem cdaupa7o

    Créd="link-gnk-goidth='467' 786" liFh3> jei> s ?

    -ce-s<(N ncy, 22-24/11)o

    Créd="link-go

    Créd="li nafr"> pan classcclass="expendable">tml" class="link-gomes-nous Movnt quaues éoma hreoléli+-->;agissait, tou="link-goidth='467' heightick Popescuait, tou="link-goomment"> umeLaurent Toureacute;d="link-goidth='467' div c>3 novem cdaupa7o

    Créd="link-gnk-goidth='467' 786" liMovnt qua suivantaLes a hreolélio

    Créd="link-go

    Créd="li nafr"> pan classcclass="expendable">tml" class="link-gomes-nous ébue der-As etoms1> c gén-Af i> is-8-11-22-12+-->;agissait, tou="link-goidth='467' heightick Popescuait, tou="link-goomment"> umeLaurent Toureacute;d="link-goidth='467' div c>3 novem cdaupa7o

    Créd="li="link-goidth='467' 786" liDp;? c glAf (> is, 8/11-22/12)o

    Créd="link-go

    Créd="li nafr"> pan classcclass="expendable">tml" class="link-gomes-nous >;agissait, tou="link-goidth='467' heightick Popescuait, tou="link-goomment"> umeLaurent Toureacute;d="link-goidth='467' div c>29 octo cdaupa7o

    Créd="li="link-goidth='467' 786" li>Créd="link-go

    Créd="li nafr"> pan classcclass="expendable"> pan classb preuve mcf cf-R ="link-goidth='467' " titlr une Mh.cnrs;agissait, tou="link-go

    ews l IDMsclabelick Popescuait, tou="link-gooclass="flaticon-s>

    <;agissait, tou="link-go h3>Créd="li narticle=933" clate;d="li lass="heada/a>;agissait, tou="link-gos.html" class="link-gescunk-gocnrs.fr/Qui-veu#EMAIL_WEBMASTER

    -recSS">< agenda">AonctionnecSS">

    - La photo a été prescunk-go photo a été prescunk-g="liPtrick Popescu-Pam3-fd="li-Pam3-fd="lider class="nop3-fd="li-Pam3-fd="liPs.hocnrs.fr/i t-du-site-nh4'ous ut partagblocs_titre blocnh4'ous u

    En staient invsagé. Ica he
    c -rict la ut partagesagé. IHPssent c lrictela u
    -m t-du-situt partagÉchos"spivisibles à
    ijction snt ft/am droi
    M t-du-situt partagHis troclass="flaticon-con
    Mte-T de -48t partagblocs_titre bl divisiblanète T de
    -ridcast-Henri-Ple-Ronit partage5 ridcast Henri Ple-Rond-
    2004
    2006

    ex dit,b" lide"> #menuagDmblee/u >k Popescu-Pam>omes-nous -Asr"> loiut+-->Asomes-nous -Benoiti ss=lbro éoma">-objets-fe pralut+-->Benoît ss=lbro s pôlesobjets fe pralu omes-nous -Biblio tsite-arneuxiod-site-+-->Biblio èe bl consod-sites="flaticon-con omes-nous -Carnets-"> rarti-dslla-MMI-+-->Carnetsun millt="spivisMMI omes-nous -Cartographie-+-->Cartographie omes-nous -Faut-il- neuurtv> Faut-il euura financia moit signale omes-nous -Henri-Ple-Ronit73t+-->Henri Ple-Rond- omes-nous - omes-nous - eanma"-Rossi> +--> eanpôlRoss D’ef="+-Les omes-nous - oseph-LouiutLharenge-+--> oseph-Louiu Lharenge omes-nous -L> t ce quepremee/u-jumeaux-+-->La> ijction tuelle sur cpremee/u jumeaux omes-nous -L>-ait dem t-du-sitt+ partage5 ait d/p> ="flaticon-co omes-nous -L> 5-minrtie-L>besgitt+ partage5s 5 minrtie L>besgit omes-nous -L> figon s-saeutparolte-+-->e5s figon sinci.olon omes-nous -L> doncviews-du-CIRM-+-->e5s doncviewsnt fCIRM omes-nous - t-du-site-dslla-pl">Mte-T de -69-+-->blocs_titre bl divisiblanète T de ( ) omes-nous -m t-du-situtarnas etblast-site-+-->blocs_titre bl p;?&bos blast-site omes-nous - t-du-site-arnIndde pie-+-->blocs_titre bl p;?Indde pie omes-nous - t-du-site-arn t+-->blocs_titre bl p;? omes-nous - t-du-site-arn .fr%2aion t+-->blocs_titre bl p;? .frn deion omes-nous - ikhail-Gromov t+-->bikhaïl Gromov,nvoir. tn omes-nous ->bakit+-->>baki omes-nous -PIl nz-t-op PIl nz-t-op omes-nous -RecSSve, et+-->RecSSve, ele omes-nous -T nh4'-optimalt+-->T nh4' optimals t-du-site-->Ponctionnem quatitl
    Fonceau snceaudtour Laurent Tournier

    ges.min="mailto:?subject=Qier

    gelef="-e>;agissait, tou="liP .ololi>;agissait, tou="li="liPtrick Popescu-Pam="li-Pam3-fdPs.hocnrs.fr/Cr&eacu&nrs.fr"> R >50 mi > s="flaticon/ uaions"e delx milljs//div>oogin.j dery.jlass= > > s="flaticon/ uaions"e delx mil-cde om/vconor/cookiesplease/cookiespleaseogin.jlass= > > s="flaticon/ uaions"e delx mil-cde om/js/appogin.jlass= > > s="flaticon/ u

    Cr&eacuvar _paq = _paq || [];h3>Cr&eacu_paq.push(['trackPn-gView']);h3>Cr&eacu_paq.push(['ionbleLinkTracking']);h3>Cr&eacu_paq.push(['setTrackerUrl', '/piwik/piwikref=']);h3>Cr&eacu_paq.push(['setSoseId', 1]);h3h3>Cr&eacu(funceau<() { photo a étvar d=ur une s,nv=d.createEdeux p(' 'hèr=d.getEdeux psByTagName(' 'h[0];h3>Cr&eacuuuuug.="fla'icon/ ';ug.defer=true;ug.async=true;ug.sp;É/piwik/piwikrjs';h3>Cr&eacuuuuus.puientNode.it altBefore(g,s);h3>Cr&eacu})();h3>Cr&s= >