STAND P.R.G. (Paris Rive Gauche, nouveau site de l'Université Paris 7)


Manipulations




On dispose d'une plaque quadrillée, avec des petits plots (ou piquets) en chaque point du quadrillage, sur lesquels on peut enfiler des rondelles métalliques (ou anneaux). On colore l'un des plots en jaune. La question posée est alors la suivante.

« Supposons que le point jaune situé sur la plaque soit un phare. Pouvez-vous entourer d'un anneau les piquets balayés par la lumière du phare ? »

Par exemple, le point de coordonnées (1,0) est éclairé par le phare, mais pas le point de coordonnées (2,0) car il est dans l'ombre du précédent. Voici un dessin représentant en rouge les piquets éclairés :

Piquets
éclairés
 par le phare 
    ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·   
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    • · ·
    		• ·
    		• · · ·
    		• ·
    		• · · ·
    		• ·
    		• · ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    • ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    • · · · · · · · ·
    		• · · · · · · ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    • ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    • · ·
    		• ·
    		• · · ·
    		• ·
    		• · · ·
    		• ·
    		• · ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    • ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·
    		• ·

    Il y a des mathématiques très intéressantes cachées derrière cette question.
    Nous allons d'abord expliquer comment voir qu'un piquet est éclairé.
    Ensuite, nous évoquerons un résultat (à la fois très beau et très fascinant) sur la « densité » des piquets éclairés, qui a permis aux organisateurs du jeu de calculer le nombre de rondelles métalliques qu'il fallait acheter.

    1  Comment voir qu'un piquet est éclairé ?

    Les piquets éclairés sont répartis selon un dessin présentant deux axes de symétrie, le motif d'un quadrant étant répété symétriquement dans les trois autres quadrants.
    Les points de la grille peuvent être repérés par leur coordonnées (a,b), qui sont des nombres entiers (positifs ou négatifs). On appellera donc les points de la grille des points entiers. Nous allons maintenant voir pourquoi les piquets éclairés par le phare sont exactement les points entiers dont les coordonnées (a,b) sont des nombres premiers entre eux.

    Considérons une droite D joignant le phare et un point de la grille. On regarde ensuite les points entiers M et M' de la droite D qui sont les plus proches possibles du phare. Notons (a,b) les coordonnées de M, alors les coordonnées de M sont (a',b'). Alors, il est clair que a et b sont premiers entre eux, car si ce n'était pas le cas, on aurait a=da1 et b=db1 avec d≥ 2 entier, et donc le point de coordonnées (a1,b1) serait un point entier de D, plus proche du phare que M, ce qui est impossible.

    Ceci nous dit qu'un piquet éclairé par le phare est un point entier dont les coordonnées sont des nombres premiers entre eux.

    Pour voir que la réciproque est vraie (c'est-à-dire qu'un point entier dont les coordonnées sont des nombres premiers entre eux est un piquet éclairé), nous aurons besoin d'un résultat d'arithmétique connu sous le nom de lemme de Gauss. Son énoncé fait intervenir trois entiers a, b, c : il dit que si a et b sont premiers entre eux et si a divise bc, alors a divise c. (Rappel : « a divise c » veut dire que c est un multiple de a.) Nous admettons ici le lemme de Gauss. Voir aussi (lien vers les mauvais prix) où est expliqué le lien avec le théorème de Bézout.

    Soit donc M un point entier dont les coordonnées (a,b) sont des nombres premiers entre eux. Notons P le phare et appelons D la droite (MP). Comme on l'a vu précédemment, parmi les points entiers qui sont sur D, il y en a deux qui sont à distance minimale du phare P. Ce sont les points éclairés de D, et leurs coordonnées sont premières entre elles. Notons N celui d'entre eux qui est du même côté que M, et (c,d) ses coordonnées. Comme M et N sont sur la même droite, on a a/b=c/d. On en déduit que ad=bc, donc a divise bc, or a et b sont premiers entre eux, donc d'après le lemme de Gauss on obtient que a divise c. Ceci signifie que c est un multiple de a, c'est-à-dire que c=na pour un certain entier n. En reportant on trouve que d=nb. Donc la distance NP est égale à n fois la distance NP. Comme NP est la distance minimale entre les points de D et P, on doit avoir n=1. Il s'ensuit qu'en fait M=N, donc M est un point éclairé.

    On a bien démontré qu'un point entier dont les coordonnées sont des nombres premiers entre eux est un piquet éclairé.

    2  Combien y a-t-il de piquets éclairés ?

    Il est naturel de se demander combien il y a de piquets éclairés. Cette question était cruciale pour organiser cet atelier, car nous avons dû acheter un nombre de rondelles métalliques suffisant pour entourer tous les piquets éclairés de nos 24 grilles de 25 piquets chacune.
    Ceci dit, vous serez peut-être d'accord avec moi pour dire que la taille de la grille que nous avions pour faire le jeu est un peu arbitraire, et on aurait envie de continuer avec une grille de plus en plus grande, une grille infinie même, pour voir le motif des points éclairés se développer... Si on prend des grilles de plus en plus grandes, le nombre de points éclairés va sans doute tendre vers l'infini, et il est plus intéressant de reformuler la question :

    « Quelle est la proportion (pour une grille infinie) des points éclairés ? »

    Si on calcule cette proportion p, alors le nombre de rondelles métalliques suffisant pour entourer tous les piquets éclairés des 24 grilles de 25 piquets chacune est environ (environ seulement !) le produit 25×24×p.

    Sur la grille que vous aviez, les coordonnées des points sont comprises entre -7 et 7 ; la largeur de la grille est donc 2×7+1=15. On trouve que le nombre de points éclairés est de 144 (on a vite fait de compter si on utilise toutes les symétries de la figure...), et le nombre de points total (éclairés ou non) est 152=225. Donc la proportion pour la grille [-7;7]×[-7;7] vaut

    p7 = 144/225 = 0,64.


    Et si on prend une grille plus grande ? Au lieu d'un quadrant de taille 7, un quadrant de taille 10, 20, 50, 100, 1000 ? Il faut s'armer de patience, et puis on trouve :

    p10 = 256/441 ≈ 0,580499
    p20 = 1024/1681 ≈ 0,609161
    p50 = 6192/10201 ≈ 0,606999
    p100 = 24352/40401 ≈ 0,602757

    et pour 1000, ma calculatrice est trop petite pour venir à bout du calcul. Mais avec un gros ordinateur, on pourrait continuer et on trouverait que la proportion pk s'approche de la valeur 0,607927... En fait, le mathématicien allemand Johann Peter Gustav Lejeune Dirichlet (1805 - 1859) a démontré le résultat suivant :

    Théorème : la proportion pk tend vers 6/π2 lorsque k tend vers l'infini.

    N'est-ce pas magnifique de voir apparaître ici le nombre π ?
    Une conséquence de ce théorème est que le nombre de rondelles métalliques que nous avons dû acheter pour entourer tous les piquets éclairés des 24 grilles de 25 piquets chacune peut être approximé par la valeur 25×24×6/π2 ≈ 365.
    Une rondelle par jour de l'année... hasard amusant.

    3  Pour en savoir plus

    On pourra trouver une démonstration du théorème de Dirichlet, ainsi que de nombreux compléments, dans le livre classique de Hardy et Wright, qui vient de recevoir une excellente traduction en français par François Sauvageot :

    Godfrey Harold Hardy et Edward Maitland Wright, Introduction à la théorie des nombres, Éditions Vuibert et Springer, 2007.

    Dans ce livre, il s'agit du théorème numéro 332.
    Il y a aussi un livre d'exercices qui contient la démonstration du théorème de Dirichlet, et dans lequel on peut trouver aussi un exercice qui montre qu'il y a une certaine forme d'irrégularité dans la répartition des points éclairés, au sens où il y a dans la grille des zones d'ombre arbitrairement grandes. Cet ouvrage est le suivant :

    Serge Francinou, Hervé Gianella, Serge Nicolas, Exercices de mathématiques. Oraux X-ENS, Éditions Cassini.


    Questions




    Le problème posé était le suivant.

    « Je veux payer mes achats chez un commerçant qui ne rend pas la monnaie, et je ne dispose que de deux types de pièces de monnaie, par exemple 2 euros et 5 euros. Il y a des prix que je peux payer exactement, on les appelle des bons prix (dans notre exemple 7 = 5 + 2 et 12 = 5 + 5 + 2 sont des bons prix). Il y a aussi des prix que je ne peux pas payer exactement, on les appelle des mauvais prix (dans notre exemple 3 et 8 sont des mauvais prix). »


    Il s'agissait d'abord de trouver les mauvais prix sur quelques exemples.

    Avec des pièces de 2 et 5 euros, on trouve les mauvais prix suivants : 1 et 3.

    Avec des pièces de 3 et 4 euros, on trouve : 1, 2 et 5.

    Avec des pièces de 4 et 5 euros, on trouve : 1, 2, 3, 6 et 7.

    Avec des pièces de 4 et 7 euros, on trouve : 1, 2, 3, 5, 6, 9, 10, 13, 17.

    Avec des pièces de 5 et 6 euros, on trouve : 1, 2, 3, 4, 7, 8, 9, 13, 14, 19.

    Dans chaque exemple, on voit qu'apparemment, à partir d'un certain montant, tous les prix sont des bons prix. Dit autrement, il semble qu'il y a un plus grand mauvais prix. C'était la réponse attendue à la question « Que semble-t-il se produire ? ».


    « Et si on a des pièces de 6 et 10 ? » Comme 6 et 10 sont tous les deux pairs, il est clair qu'on ne peut payer que des prix pairs... donc tous les prix impairs sont des mauvais prix, et il y a une infinité de mauvais prix. L'intuition qu'on a eue avant ne marche donc plus. La raison en est que 6 et 10 ne sont pas premiers entre eux, ils sont tous les deux divisibles par 2. En fait 2 est leur plus grand commun diviseur, leur pgcd. Si les montants des deux pièces ont un pgcd qui est un nombre plus grand que 2, le même phénomène se produit et il est clair qu'il n'y a pas de plus grand mauvais prix.

    Pour la question suivante, qui n'était posée que pour les participants en catégorie « bleue », on suppose donc que les montants des pièces ont un pgcd égal à 1, on dit aussi qu'ils sont premiers entre eux.


    « On suppose que les montants a et b des deux types de pièces sont premiers entre eux. On veut calculer le plus grand mauvais prix, m, en fonction de a et b. Dans chacun des quatre exemples ci-dessus, donnez la valeur de m puis calculez m+a+b. Pouvez-vous deviner une formule pour m ? Question subsidiaire : pouvez-vous démontrer cette formule ? »

    Avec des pièces de 2 et 5 euros, on trouve m=3 et m+a+b=10.

    Avec des pièces de 3 et 4 euros, on trouve m=5 et m+a+b=12.

    Avec des pièces de 4 et 5 euros, on trouve m=7 et m+a+b=20.

    Avec des pièces de 4 et 7 euros, on trouve m=17 et m+a+b=28.

    Avec des pièces de 5 et 6 euros, on trouve m=19 et m+a+b=30.

    Dans chaque exemple, on constate que m+a+b=ab... On peut deviner que cette formule marche en général. Nous allons la démontrer.



    Pour cela, nous utiliserons le théorème de Bézout qui dit que si a et b sont premiers entre eux, alors il existe des nombres entiers relatifsu0,v0 tels que u0a+v0b=1. (Les entiers relatifs sont les entiers positifs ou négatifs : ...,−2,−1,0,1,2,...) En fait, pour tout entier n, il existe des entiers relatifs un,vn tels que una+vnb=n, en effet un=nu0 et vn=nv0 conviennent. Mentionnons encore un petit raffinement très utile. On peut faire la division euclidienne de un par b, elle sécrit un=qb+u avec 0 ≤ u ≤ b−1. On trouve donc una+vnb=(qb+u)a+vnb=ua+(qa+vn)b . En posant v=qa+vn on trouve que

    pour tout entier n, il existe des entiers relatifs u,v tels que ua+vb=n avec 0 ≤ u ≤ b−1.

    On peut démontrer que ces entiers sont uniques, c'est un exercice assez facile que je laisse au lecteur courageux. Pour utiliser ce petit résultat, nous l'appellerons l'écriture de Bézout unique associée à a et b.
    À l'aide du théorème de Bézout on peut aussi démontrer un résultat connu sous le nom de lemme de Gauss, qui fait intervenir un troisième entier c : si a et b sont premiers entre eux, et si a divise bc, alors a divise c. (Rappel : « a divise c » veut dire que c est un multiple de a.) C'est facile : l'hypothèse est que bc=ma pour un certain entier m. On part d'une écriture 1=u0a+v0b donnée par Bézout, on la multiplie par c, on trouve c=u0ac+v0bc=u0ac+v0ma=(u0c+v0m)a. Ceci montre bien que a divise c.


    Démontrons maintenant que ab−(a+b) est bien le plus grand mauvais prix. Voyons d'abord que c'est un mauvais prix. En effet, si ce n'est pas le cas, il existe des entiers u ≥ 0 et v ≥ 0 tels que ab−(a+b)=ua+vb. On en déduit ab=(u+1)a+(v+1)b. Ainsi a divise (v+1)b donc, comme a et b sont premiers entre eux, par le lemme de Gauss on obtient que a divise v+1, donc il existe v' ≥ 1 tel que v+1=v'a. De même, on montre que b divise u+1 et donc il existe v' ≥ 1 tel que v+1=v'a. On a donc ab=u'ab+v'ab d'où en divisant par ab : 1=u'+v'. Or u'+v' ≥ 2, il y a donc contradiction. Donc ab−(a+b) est un mauvais prix.

    Démontrons ensuite que tout mauvais prix n vérifie n ≤ ab−(a+b). Considérons l'écriture de Bézout unique n=ua+vb avec 0 ≤ u ≤ b−1. Comme c'est un mauvais prix on doit avoir v ≤ −1 et donc n=ua+vb ≤ (b−1)a−b=ab−a−b. C'est fini.




    Remarque culturelle : si on dispose de trois pièces a,b,c dont les montants sont premiers entre eux (ou même de quatre, cinq pièces...), on peut encore démontrer qu'il y a un plus grand mauvais prix m. En revanche, c'est un problème ouvert de trouver une formule pour m...


    Enfin, voici un petit complément pour les lecteurs très gourmands : on peut compter exactement le nombre de mauvais prix, c'est 1/2(a−1)(b−1).

    Pour démontrer cela, on va noter E l'ensemble des entiers {0,1,...,m} et on considère l'application i : E→ E définie par i(x)=m−x. C'est une involution, c'est-à-dire que i(i(x))=x pour tout x∈ E. Nous allons montrer que i échange les mauvais prix et les bons prix. Ainsi, i sépare les éléments de E en deux paquets de tailles égales (les bons, et les mauvais prix), or E compte ab−(a+b)+1=(a−1)(b−1) éléments (en comptant 0 qui est un bon prix), d'où le résultat en divisant par 2.

    Supposons que x est un bon prix. Si m−x était aussi un bon prix, alors la somme x+(m−x)=m serait un bon prix. Ceci n'est pas vrai. Donc, m−x est un mauvais prix.

    Supposons maintenant que x est un mauvais prix et montrons que m−x est un bon prix. Considérons l'écriture de Bézout unique de m−x, c'est-à-dire m−x=ua+vb avec u,v entiers relatifs et 0≤ u≤ b−1. Il suffit de montrer qu'alors v≥ 0. Or, on a

    x=m−(m−x)=m−(u a+v b)=ab−(a+b)−(u a+v b)=(b−(u+1))a−(v+1)b  .

    Posons u'=b−(u+1) et v'=−(v+1), de sorte que x=u' a+v' b. Vu qu'on a choisi l'écriture de Bézout unique on a u'≥ 0, si de plus v'≥ 0 alors x serait un bon prix, contrairement à l'hypothèse. Ainsi, v'<0 i.e. v≥ 0 qui est ce qu'on voulait montrer. Donc m−x est un bon prix.
    On a bien prouvé que i échange les bons et les mauvais prix.

       
    Bons
    et
     mauvais 
     prix