[Vidéo] Autour de la Terre – Automaths #03

Nouvelle vidéo sur la chaîne Automaths : cette fois, on fait le tour de la Terre, de la tête au pied !

Si vous souhaitez allez plus loin, n’hésitez pas à lire la suite ! Autant vous avertir toutefois, ce ne sera pas forcément évident pour tous : il vous faudra mobiliser certains souvenirs de fins de collèges voire de lycée et bien manipuler le calcul littéral. Vous pouvez tout autant vous contenter du résultat incroyablement contre-intuitif, ce sera déjà quelque chose !

Puis bon, finalement, c’est du calcul un poil bourrin, alors bon…

Drapeau rouge : Cet article demande quelques connaissances mathématiques (trigonométrie) ainsi qu’une bonne capacité d’abstraction


Tendre en un point

Vous l’avez donc vu, si l’on ajoute 1 mètre à la corde qui fait le tour de la Terre, on peut surélever la corde de 16 cm en tout point, un résultat qui paraît totalement absurde.

Encore plus surprenant à mon goût, c’est cette corde que l’on soulève en un seul point cette fois-ci : on peut désormais la soulever de 120 m environ !

En gros, on passe d’une corde de 40000 km à 40000,001 et on est capable de faire passer une quarantaine d’éléphants empilés les uns sur les autres ! Pour prouver ce résultat, nous allons devoir faire appel à la trigonométrie.

On allonge la corde d’un mètre et on soulève en un point : quelle est la hauteur ainsi créée ?

Pour rappel, dans un triangle rectangle, on peut exprimer certaines quantités reliées aux angles aigus. Celles qui nous intéressent ici sont le cosinus et la tangente : il nous est donné par le rapport entre le côté adjacent à l’angle (le côté commun à l’angle droit et à l’angle observé) et l’hypoténuse – le plus grand côté du triangle.

On définit par ailleurs la tangente d’un angle par le rapport du côté opposé sur le côté adjacent.

Ici, le cosinus de l’angle bleu vaut BC/AC, sa tangente vaut AB/BC

 

En avant les calculs…

Appelons donc h la hauteur recherchée et R le rayon de la Terre. Nous allons placer plusieurs points sur notre schéma :

  • le point S, au sommet, qui correspond au point le plus haut atteint par la corde.
  • les points A et B, les deux points à partir desquels la corde se détache de la surface de la Terre.
  • le point O, centre de la Terre.

Avec nos notations, nous pouvons d’ores et déjà donner quelques valeurs : AO = BO = R, tandis que SO = R + h. D’autre part, les triangles AOS et BOS sont rectangles, respectivement en A et en B. Cela nous servira plus tard !

De plus, nous noterons T l’angle \widehat{AOS}. Notez que pour les calculs, T sera exprimé en radians : 180° correspondent à π radians. Nous avons tout ce qu’il nous faut, commençons les calculs maintenant !

Nos différents points sont placés !

D’abord, le tour de la corde de base, équivalent au tour de la Terre, vaut 2πR. Pour la longueur de la corde allongé de 1 mètre, il est possible de l’exprimer de deux façons différentes.

  • Puisque la corde est allongé d’un mètre, cette longueur vaut 2πR + 1
  • Mais, si on appelle C la longueur du grand arc de cercle entre A et B, elle vaut également C + AS + BS, ou C + 2 AS

Or, dans le triangle AOS, rectangle en A, nous avons tan(T) = AS / AO, soit AS = AO tan(T) donc AS = Rtan(T).

Par ailleurs, puisque notre angle T est exprimé en radians, la longueur du grand arc de cercle qui relie A à B vaut (2π-2T)R.

En combinant tout cela, nous obtenons :

2πR+1=2Rtan(T)+(2π-2T)R

ce qui conduit à

1 = 2R(tan(T) – T)

Il est l’heure de faire nos premières approximations : nous allons supposer que la hauteur h est petite par rapport au rayon de la Terre et que l’angle T lui-même est petit. Cette approximation nous permet alors d’approcher la quantité tan(T) – T par T3/3. Nous avons donc :

1 = 2RT3/3

ou réécrit de manière à isoler T :

T = \frac{3}{2R}*

C’est bien beau, mais ce qui nous intéresse, c’est h. Regardons alors le cosinus de l’angle T. Nous avons :

cos(T) =  AO / SO = R / (R + h)

Or, l’angle T étant toujours supposé petit, on peut approcher cos(T) par 1 – T2/2. Faisons donc :

1 - \frac{T^{2}}{2}=\frac{R}{R+h}

Puis nous allons remplacer le T de cette équation en utilisant le résultat noté *.

1 - \frac{1}{2}\left( \frac{3}{2} \right)^{2/3}\left(\frac{1}{R}\right)^{2/3}=\frac{R}{R+h}

Beurk… Courage, nous y sommes presque ! Passons le R+h de l’autre côté et développons

R + h -\frac{1}{2}\left( \frac{3}{2} \right)^{2/3}R^{1/3}- h\frac{1}{2}\left( \frac{3}{2} \right)^{2/3}\left(\frac{1}{R}\right)^{2/3}=R

Deux choses : d’abord, les R s’annulent, on peut les oublier. Ensuite, la partie h\frac{1}{2}\left( \frac{3}{2} \right)^{2/3}\left(\frac{1}{R}\right)^{2/3} est petite comparée au reste : nous pouvons donc raisonnablement l’oublier. Il en vient donc :

h \simeq \frac{1}{2}\left( \frac{3}{2} \right)^{2/3}R^{1/3}

Oui, non, on ne peut pas faire plus joli, surtout qu’il y a déjà eu pas mal d’approximations !

Bref, il est temps de répondre à notre question : comme vous le voyez ici, h dépend fortement du rayon R de la Terre ou de la sphère autour de laquelle nous attachons notre corde.

En prenant pour rayon celui de la Terre, R = 6371000 m, on obtient environ 121 mètres.

Attention si vous souhaitez appliquer cette formule à d’autres sphères : il est important ici d’exprimer votre rayon en mètres pour conserver la bonne unité ! (En effet, il est sous-entendu que le coefficient 3/2 est aussi en mètres, il faut donc utiliser cette même unité.)

Promis, la prochaine fois, ce sera moins douloureux…

Pour compléter

  • Axel Bellos, Le cercle des problèmes incongrus, Ed Flammarion, 2016

 

Publié dans Paradoxes mathématiques, Vidéo | Tagué , , , | Laisser un commentaire

Le théorème de Pythagore… en puzzles !

Drapeau vert : Cet article ne demande aucune connaissance mathématique particulière


Le théorème de Pythagore, le fameux théorème de Pythagore…

Mais si, celui qui dit que dans un triangle rectangle, le carré de la longueur de l’hypoténuse – le côté en face de l’angle droit – est égal à la somme des carrés des longueurs des deux autres côtés. Dit comme ça,on est en droit de se demander d’où sort cette formule magique…

Il est donc temps de faire un peu de géométrie !

L’aire de la figure

Commençons par une figure de base : le carré. Pour rappel, un carré possède 4 côtés de même longueur et 4 angles droits. Si l’on connaît la longueur d’un de ses côtés, on est alors capable de calculer la surface occupée par ce carré : il suffit de multiplier cette longueur par elle-même. On dit justement qu’on élève la longueur au carré.

Par exemple, un carré de 5 cm de côté recouvre une surface de 25 cm². Autrement dit, on peut placer 25 petits carrés de côté 1 cm dans ce carré-ci.

Ce carré de 5cm de côté contient 5 x 5 = 25 petits carrés de côté 1cm

Prenons alors un triangle rectangle, n’importe lequel, et plaçons des carrés sur chacun de ses trois côtés. Nous allons maintenant faire correspondre les longueurs des côtés du triangle aux aires – les surfaces – des carrés dessinés.

Le théorème de Pythagore implique qu’en découpant les deux petits carrés, on peut reconstruire parfaitement le grand carré.

Le carré de la longueur de l’hypoténuse – c’est-à-dire l’aire du carré qui repose sur le plus grand côté – est égal à la somme des carrés des longueurs des deux autres côtés – l’aire des deux autres carrés.

En d’autre termes, on peut découper les deux petits carrés de manière à recouvrir parfaitement le plus grand carré, sans laisser aucun trou et sans faire se chevaucher les pièces ainsi découpées !

Puzzles et constructions

A partir de là, de nombreux puzzles ont vu le jour pour illustrer cette propriété, dont le puzzle de Périgal, présenté ci-dessous.

On peut découper les deux carrés du haut puis réarranger les pièces pour reconstruire le carré du bas.

Si vous souhaitez voir d’autres « Puzzles de Pythagore« , vous pouvez en trouver en ligne à cette adresse. A vous de les résoudre !

Naturellement, cette méthode n’est pas la seule pour parvenir à ses fins. Une méthode classiquement montrée passe par la soustraction d’aires. Pour cela, appelons a et b les longueurs des côtés de l’angle droit et c la longueur de l’hypoténuse.

Nous construisons alors un carré dont le côté a pour longueur a + b, puis nous disposons 4 triangles comme suit :

L’aire restante dans le carré, une fois quatre triangles ôtés, est la même de chaque côté.

Forcément, puisque l’on retire 4 fois la même surface, alors l’aire restante est la même à chaque fois : à gauche, c’est un carré de côté de longueur c, à droite, ce sont deux carrés de côtés respectifs a et b. Et voilà, le résultat est là !

Preuve et illustration

Il convient toutefois d’aborder ces puzzles, aussi utiles soit-il, avec prudence. Les dessins sont parfois trompeurs, et ils ne sauraient faire office de preuve à eux seuls.

Dans le théorème de Pythagore, il y a ainsi l’expression « triangle rectangle » qui apparaît, ce qui laisse supposer que ce que nous venons de faire ne serait pas valable avec un triangle quelconque (et c’est en effet le cas). Pourquoi alors ? Cette donnée apparaît-elle clairement dans les puzzles ?

On peut la voir apparaître dans la méthode de soustractions d’aire : si le triangle de départ n’était pas rectangle, alors les figures formées en clair ne seraient pas des carrés.

Et puis, nous avons là un triangle particulier, qu’est-ce qui nous dit que cela fonctionnera avec n’importe quel autre triangle rectangle ? Est-ce que les mesures n’ont pas été justement choisies pour que tout colle à la perfection ?

Encore plus sournois, est-ce que ce puzzle colle bien parfaitement ? Est-ce qu’il n’y a pas un léger interstice entre les pièces, indécelable à l’oeil mais qui fausserait toute approche mathématique ? – et nous verrons des exemples sur ce blog, croyez-le bien !

Bref, un dessin ou une animation sont de bonnes approches pour bien comprendre les enjeux et mieux se représenter ce théorème, mais elles ne suffisent pas non plus à le prouver.

Pour compléter

  • Résolvez 5 puzzles sur cette page Geogebra
  • Les carrés c’est bien, mais on peut faire n’importe quelle forme, comme le montre cet article de blogdemaths.
  • Un article d’Images des mathématiques sur le théorème de Pythagore et ses puzzles.
Publié dans Conjectures et théorèmes | Tagué , , | Laisser un commentaire

Paver des rectangles

Vous vous souvenez du puzzle impossible de la dernière vidéo ? Non ? Il est encore temps de vous rattraper en allant la regarder alors !

Dans notre cas, pour prouver que notre puzzle n’était pas réalisable, on utilisait un argument de parité : en coloriant une case sur deux du rectangle à remplir, on en déduisait que les pièces fournies ne pouvait le recouvrir entièrement.

Voilà pourtant un nouveau problème : cette fois-ci, vous devez paver un rectangle de taille 14 x 10 cases avec des pièces rectangulaires de 1 x 4 cases. Si on colorie nos rectangles en noir et blanc, on remarquera que chacun présentera autant de cases noires que de cases blanches… Et pourtant, là encore, le puzzle s’avère impossible !

Pour montrer notre résultat, nous pouvons de nouveau procéder à un coloriage du rectangle, mais cette fois, en utilisant 4 couleurs disposées ainsi.

Nous remarquons alors que chaque couleur est représentée 35 fois. Or, en posant une pièce de taille 1×4 sur notre grand rectangle, il est facile de constater que cette pièce couvrira deux cases d’une couleur et deux cases d’une autre couleur… ce qui implique que le nombres de cases de la même couleur est forcément pair ! Ca ne colle pas, puzzle impossible, terminé.

Bon, les cas particuliers, c’est bien marrant, mais il serait sympathique de trouver une méthode générale pour ne pas devoir, à chaque fois, ressortir nos crayons de couleur et s’arranger pour trouver une situation qui ne nous convient pas… D’autant plus que cette méthode ne fonctionne que pour montrer qu’un puzzle est impossible, mais ne donne aucune piste pour déterminer les cas possibles !

Rassurez-vous, car un tel théorème existe bel et bien…

Le théorème

Énonçons d’abord ce résultat que nous devons à De Bruijn et Klarner.

Nous souhaitons remplir un grand rectangle de dimension L x M avec des pièces rectangulaires de taille a x b. Ce résultat est possible si et seulement si les trois conditions suivantes sont satisfaites :

  1. LM est un multiple de ab
  2. L et M peuvent tous les deux s’écrire comme une somme de a et de b – si vous n’avez pas encore trop de lettres, cela signifie qu’il existe quatre entiers positifs w, x, y et z tels que L = wa + xb et M = ya + zb… Bref…
  3. a et b ont tous les deux un multiple parmi L et M (éventuellement le même).

Rassurez-vous, nous allons expliquer tout cela, mais commençons par des cas particuliers :

Est-il possible de paver un rectangle de taille 9 x 14 en utilisant des pièces de taille 2 x 3 ?

  1. 9 x 14 = 126, qui est bien un multiple de 2 x 3 = 6 – en l’occurrence, 126 = 6  x 22
  2. 9 = 3 + 3 + 3 et 14 = 3 + 3 + 3 + 3 + 2. On a donc écrit 9 et 14 comme des sommes de 2 et de 3
  3. 14 est un multiple de 2, 9 est un multiple de 3

Les trois conditions sont vérifiées, pas de souci ! Le pavage est d’ailleurs très simple à obtenir, n’hésitez pas à le chercher !

Repassons alors au cas du rectangle 14 x 10 à remplir avec des pièces de taille 1 x 4 :

  1. 14 x 10 = 140 est bien un multiple de 1 x 4  =4
  2. 14 = 4 + 4 + 4 + 1 + 1 et 10 = 4 + 4 + 1 + 1, on a écrit 14 et 10 comme sommes de 4 et de 1
  3. En revanche, ni 14, ni 10 ne sont des multiples de 4 ! La condition 3 n’est pas vérifiée, il est impossible de réaliser un tel pavage.

Conditions nécessaires et suffisantes

L’énoncé de notre théorème comporte une formulation importante : « si et seulement si« . Cela signifie que les conditions évoquées sont à la fois nécessaires pour paver les rectangles, mais aussi que les vérifier suffit à affirmer que notre rectangle est pavable.

Montrons pour commencer qu’elles sont nécessaires, et nous allons donc supposer qu’un pavage du grand rectangle existe :

D’abord, il faut remplir le grand rectangle (composé de LM cases) avec un certain nombre de petits rectangles (qui ont chacun ab cases) : il faut donc bel et bien que le nombre de cases du plus grand rectangle soit un multiple du nombre de cases du petit rectangle.

Par ailleurs, puisque notre rectangle est pavé, nous pouvons regarder ce qu’il se passe sur un de ses bords : les petits rectangles y sont accolés, dans un sens ou dans l’autre. La longueur du bord se décompose donc selon les mesures de notre petit rectangle.

Si mon grand rectangle est pavé de petits rectangles de taille 2 x 3, alors chaque longueur du grand rectangle doit s’écrire comme somme de 2 et de 3

Pour la troisième propriété, nous allons diviser toutes nos longueurs par a, c’est-à-dire, la longueur d’un côté du petit rectangle. Nous avons donc pavé un rectangle de dimension L/a x M/a avec des pièces de taille 1 x b/a

Attention, fermez les yeux car nous allons admettre un théorème : si un rectangle est pavé avec d’autres rectangles ayant tous au moins une longueur entière, alors le rectangle ainsi obtenu a lui également une longueur entière. En l’occurrence, tous nos petits rectangles ont une longueur qui vaut 1, un entier. Du coup, le grand rectangle de taille L/a x M/a aussi : il y a au moins une grandeur parmi L/a et M/a qui est entière. En d’autres termes, a divise L ou a divise M. Et on utilise le même raisonnement avec b, bien entendu.

Voilà, nos trois conditions sont nécessaires, reste à montrer qu’elles sont suffisantes.

Notons alors deux cas de figure :

– soit a et b divisent deux nombres différents. Dans ce cas, le pavage est très simple à obtenir : voyez plutôt sur l’exemple suivant pour vous en convaincre.

– soit a et b divisent tous les deux le même nombre, disons L. Alors, d’après notre deuxième propriété, l’autre grandeur, M, peut s’écrire comme somme de a et de b. Autrement dit, il existe y et z, des entiers positifs, tels que M = ya + zb.

Prenons un exemple pour mieux nous représenter la suite : on souhaite paver un rectangle 22 x 20 avec des pièces  de taille 4 x 10. 4 et 10 divisent 20 mais pas 22.
Or, 22 = 4 + 4 + 4 + 10 = 3 x 4 + 1 x 10.

Nous allons donc diviser le côté de longueur 22 en 4 parties : 3 de longueurs 4 et 1 de longueur 10. A partir de là, il suffit de compléter avec nos rectangles en les posant dans le bon sens. Ce raisonnement pourra alors être copié pour n’importe quels petits et grands rectangles.

22 = 4 + 4 + 4 + 10, on subdivise donc le côté de longueur 22 en 3 parties de longueurs 4, 4, 4 et 10

Voilà notre preuve terminée !

Bon pavage !

Pour compléter

  • Jean-Paul Delahaye, Les plaisirs du rectangle,  Pour la Science Avril-Juin 2016
  • stan Wagon, Fourteen proofs of a result about tilling a rectangle, The American Mathematical Monthly, Vol 94, N°7, Août-Sept 1987, p 601-617
Publié dans Conjectures et théorèmes, Curiosités et récréation | Tagué , , , , , | Laisser un commentaire

5 nuances d’Aubrey de Grey

Drapeau vert : Cet article ne demande aucune connaissance mathématique particulière


Pas besoin d’être un pro des mathématiques pour s’amuser avec des graphes. Avec seulement quelques points et des arêtes, il est possible de concocter des problèmes au apparences simplistes qui résistent pourtant plusieurs décennies.

Récemment, c’est le problème du nombre chromatique du plan qui a fait parler de lui, puisqu’un certain Aubrey de Grey, biologiste de métier, a apporté une avancée significative à cette question vieille de plusieurs décennies : de combien de couleurs a-t-on besoin pour colorier le plan ?

Tout ceci semble un peu flou, alors apportons sans plus tarder un peu de précisions, si vous le voulez bien.

Colorier un graphe

Un graphe, comme mentionné dans cette introduction, c’est un ensemble de points – appelés sommets – dont certains sont reliés entre eux par des traits, des arêtes. Les graphes sont très utiles pour représenter certaines situations : on peut penser au réseau du métro, à un arbre généalogique ou à un graphe d’amis sur les réseaux sociaux.

Une fois devant un graphe, on peut alors se donner à toutes sortes de jeu. Celui qui nous intéresse aujourd’hui concerne le coloriage : à chaque sommet du graphe, je souhaite assigner une couleur, mais en faisant cela, je ne veux pas que deux sommets reliés par une arête aient la même couleur.

Naturellement, en bon mathématicien radin que je suis, je veux utiliser le moins de couleurs possibles pour réaliser mon coloriage – sans pour autant déroger à la règle instaurée deux lignes plus haut ! – : dans ce cas, le nombre de couleurs utilisé s’appellera nombre chromatique du graphe.

Graphe de Moser. Son nombre chromatique est de 4 : 3 couleurs ne suffisent pas à le colorier correctement.

Trouver le nombre chromatique d’un graphe n’est pas une affaire aisée : il faut, en gros, essayer tous les coloriages de ce graphe et déterminer le meilleur, ce qui peut prendre beaucoup de temps lorsque le graphe comporte beaucoup de sommets et – surtout- beaucoup d’arêtes.

Et ça le devient encore plus lorsque ces deux ensembles sont… infinis !

Graphe unitaire

Pour notre coloriage, nous allons choisir un graphe un peu particulier. Comme sommets de ce graphe, nous considérerons tous les points du plan. Tous. Sans exception. Imaginez une feuille blanche qui s’étend à l’infini dans toutes les directions, choisissez un point dessus. Gagné, il est dans le graphe !

Reste alors à décrire les arêtes : deux sommets de ce graphe seront reliés si la distance qui les sépare vaut 1 (1m, 1 cm, 1 année-lumière, que sais-je, vous prendrez bien l’unité qui vous convient). Cela revient à tracer un cercle de rayon 1 autour de chaque point du plan, et de relier tous les points de ce cercle au centre. Autant dire que ça en fait des arêtes.

La question est donc la suivante : quel est le nombre chromatique de ce graphe ? De combien de couleurs ai-je besoin, au minimum, pour le colorier sans que deux sommets voisins aient la même couleur ? En bref, quel est le nombre chromatique du plan ?

Une autre manière de s’imaginer ce problème est le suivant : si je possède un bâton de longueur 1, il faut trouver un coloriage du plan tel que, où que je pose mon bâton, ses deux extrémités se trouvent sur des points de couleurs différentes.

Ce problème, appelé problème de Hadwiger-Nelson, a été pour la première fois mentionné en 1950, avant d’être relayé par Martin Gardner dix ans plus tard. Et pourtant, il résiste encore et toujours, non pas à l’envahisseur, mais au commun des mortels.

Rassurez-vous, tout n’est pas aussi noir, et nous pouvons tout de même formuler quelques résultats.

D’abord, le nombre chromatique du plan ne peut excéder 7 : nous devons ce résultat à John Isbell qui s’est inspiré d’un pavage hexagonal pour établir cette borne supérieure.

En plaçant une baguette de longueur 1 sur ce pavage, ses deux extrémités se trouvent forcément sur deux couleurs différentes.

Isbell utilise des hexagones de diamètre légèrement inférieur à 1 et les colorie de 7 couleurs différentes. De cette manière, peut importe le point que je choisis, tous les points se trouvant à distance 1 de celui-ci se trouvent dans des zones d’une couleur différente à la première.

Graphe de Golomb

Graphe de Golomb, impossible à colorer avec seulement 3 couleurs

Ensuite, on sait depuis quelques années que le nombre chromatique du plan est d’au moins 4 : il existe en effet certains graphes unitaires, comme le graphe de Moser ou le graphe de Colomb, qui ne peuvent être coloriés en utilisant seulement 3 couleurs.

Ne restent alors que 4 options pour notre nombre chromatique : 4, 5, 6 ou 7… Et voilà, l’histoire s’est arrêtée là pendant un bon bout de temps, jusqu’à ce que le précédemment mentionné Aubrey de Grey ne vienne mettre son nez dans cette affaire.

Le graphe de De Grey

Dans son article intitulé « The chromatic number of the plane is at least 5« , De Grey annonce la couleur (ah, ah !) : le nombre chromatique du plan est d’au moins 5, et pour le montrer, De Grey a construit un graphe impossible à colorer avec seulement 4 couleurs.

De Grey commence par observer un graphe, qu’il appelle H, ayant la forme d’un hexagone régulier avec un point en son centre. Le nombre chromatique de ce graphe est 3, mais ce n’est pas ce qui nous intéresse ici. De Grey remarque en effet que si on utilise au plus 4 couleurs, certaines colorations de ce graphe présentent un triangle monochromatique, alors que d’autres non.

Colorations du graphe H. Les deux versions du haut possèdent au moins un triplet de points de la même couleur – trois bleus, en l’occurrence. Image tirée de l’article de De Grey.

Partant de ce point, De Grey va alors construire deux graphes, chacun d’eux contenant au moins une copie de H. Concentrez-vous bien, car même si ce n’est pas très compliqué, il y a de forts risques de se perdre là-dedans.

  • Le premier graphe, appelé L – oui, c’est intime tout ça – est obtenu en dupliquant le graphe H de départ. Au final, ce graphe L contient 52 copies du graphe H, mais le plus important est que, si l’on essaye de colorier L à l’aide de 4 couleurs, alors au moins une copie de H de ce grand graphe présentera un triplet de point de même couleur.

Construction du graphe L à partir du graphe H

  • Le second graphe, appelé M, est une extension du graphe H – on rajoute des sommets et des arêtes, d’une façon un peu intelligente tout de même – qui vérifie une propriété contraire : si j’essaye de colorier M avec 4 couleurs, alors le graphe H ne contiendra cette fois aucun triplet de la même couleur.

Le graphe M de De Grey compte 1345 sommets et 8268 arêtes. Autant dire qu’il est impossible de vérifier à la main tous les coloriages possibles.

Bref, nous avons deux graphes L et M. Chacun peut être colorié avec 4 couleurs, mais le premier implique la présence d’un triplet monochromatique de points sur les copies de H, alors que c’est le contraire pour ce second graphe. Il n’y a plus qu’à les combiner ensemble et faire marcher la contradiction ! Le graphe obtenu ne peut pas être colorié avec seulement 5 couleurs.

Le graphe obtenu possède alors 20425 sommets, autant dire que ce n’est pas un petit graphe ! Heureusement, il est possible de retirer certains sommets pour aboutir à un graphe plus petit – 1581 puis 1577 sommets -, sans que celui-ci ne devienne colorable avec 4 couleurs pour autant.

Le graphe de De Grey à 1581 sommets. Source : Aubrey de Grey

On peut alors vérifier à l’aide d’un programme que 4 couleurs ne suffisent à colorer ce graphe : cela prend à peine 5 heures et demis avec du bon matériel, tandis que colorier ce graphe avec 5 couleurs prend moins d’une seconde.

Bref, le nombre chromatique du plan est au moins 5. C’est peut-être 5, 6 ou 7, mais 4 a disparu de la liste des choix.

Depuis la publication de l’article, un projet Polymath a d’ailleurs été lancé pour trouver des graphes toujours plus petits mais impossible à colorier avec seulement 4 couleurs. Ainsi, Marijn Heule est parvenu à réduire le nombre de sommets à 826.

Graphe de Marijn Heule, à 826 sommets. Source : Marijn Heule

En outre, ce projet a deux autres objectifs :

  • d’abord, voir si cette méthode peut s’étendre à la découverte de graphes unitaires qui ne peuvent être colorié avec 6 couleurs ou à des problème liés, comme le nombre chromatique des espaces de dimensions supérieurs
  • mais aussi réduire autant que possible l’utilisation de l’ordinateur dans cette preuve : les mathématiciens sont très attachés aux démonstrations « à la main ».

En bref, il y a encore du travail, mais cette avancée en appellera peut-être de nouvelles dans les mois à venir ?

Compléments et références

  • Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators
  • De Grey, A. The Chromatic Number of The Plane is At Least 5
  • L’article de Quanta Magazine qui parle de cette découverte.
  • Deux articles sur le blog Short, Fat Matrices : ici, avec notamment les temps de calcul pour la coloration de graphe et , pour la description de la méthode
  • Le projet Polymath et les graphes sont décrits à cette adresse
  • Un article sur le blog de Gil Kalai, Combinatorics and more
  • En français cette fois, Eljj avait fait un article de blog sur la couleur du plan, c’est à cette adresse.
  • Un article sur le blog de David Madore qui traite également de la coloration du plan.
Publié dans Actualité, Conjectures et théorèmes | Tagué , , , | 1 commentaire

D’élégantes démonstrations

On le dit souvent, en mathématiques, le cheminement importe plus que le résultat. Que l’on soit d’accord ou non avec l’affirmation, il faut tout de même avouer que résoudre en une ligne certains problèmes d’apparences très difficiles a quelque chose de… magique.

Alors, forcément, dans le domaine, on pourrait en imaginer beaucoup, chacun aura son avis sur la question. D’ailleurs, certains trouveront de la beauté dans certaines preuves que d’autres jugeront absolument inélégantes : tout n’est que subjectif et relatif.

Voici, en tout cas, trois problèmes et leurs solutions que je trouve, pour ma part, fort élégantes ! Faites chauffer les méninges !

Le puzzle impossible ?

Drapeau vert : Cette partie ne demande aucune connaissance mathématique particulière


Celui-ci ne prendra que peu de place, puisque je lui ai consacré toute une vidéo que vous devriez aller voir, si ce n’est déjà fait. Le principe est de recomposer une forme donnée à l’aide de 5 tetrominos (autrement dit, des pièces formées de 4 cases carrées).

Le chien coureur

Drapeau vert : Cette partie ne demande aucune connaissance mathématique particulière


Deux personnes, que nous nommerons Alphonse et Bernadette, A et B pour les intimes, se trouvent à 2 kilomètres l’une de l’autre et chacune marche en direction de l’autre à une vitesse approximative de 1 m/s. A côté d’Alphonse se trouve un chien qui s’élance vers Bernadette en même temps qu’Alphonse commence sa marche.

Sauf qu’un chien, ça ne prend pas son temps celui-ci trace en effet sa route à environ 5 m/s. Une fois arrivé au niveau de Bernadette, il repart en sens opposé retrouver Alphonse, toujours à la même vitesse, et fait ainsi des allers-retours jusqu’au moment où Alphonse et Bernadette se croisent.

Quelle est alors la distance totale parcourue par le chien ?

Il court, il court, le chienchien…

En se lançant tête baissée dans ce genre de problèmes, on peut se retrouver vite désemparé : il faut faire la somme de tous les déplacements de l’animal, avec des distances qui varient après chaque étape. En développant les calculs, on se trouve alors avec une série géométrique assez classique, et je laisse le soin aux lecteurs habitués de vérifier que je ne dis pas de bêtises.

Voilà, voilà…

Eh oh, t’avais dis que c’était un drapeau vert, c’est quoi ce bazar ?

Oui, j’y viens, mais d’abord, commentons toutefois un petit peu cette formule :

  • Le 2 correspond aux 2 kilomètres qui séparent A et B au début.
  • Le 5/6 vient du fait que le chien va 5 fois plus vite que les personnages. S’il se dirige vers Alphonse, il couvre 5/6 de la distance tandis qu’Alphonse fait le 1/6 restant dans le même temps.
  • A chaque fois que le chien croise un personnage, il fait demi-tour. La distance entre Alphonse et Bernadette a alors diminué d’un tiers – je vous laisse les calculs hein.

Bon, enfin, c’est bien joli tout ça, mais est-ce que ce ne serait pas prendre le canon pour tirer sur une mouche ?

Raisonnons mieux : Puisque nos deux personnages vont à la même vitesse, ils se croiseront pile à mi-distance. Ils auront fait 1 kilomètre chacun. Le chien allant 5 fois plus vite que chacun d’eux, il en aura fait 5 fois plus… soit 5 kilomètres…

Tadam !

Des graphes connexes

Drapeau jaune : Cette partie demande quelques connaissances mathématiques de base et un peu d’abstraction pour être entièrement saisie.


Pour l’exemple suivant, il faudra un peu plus de travail, mais rien d’insurmontable.

Donnons d’abord quelques définitions :

  • Un graphe (non orienté), c’est simplement un ensemble de points – appelés sommets –  reliés par des traits, que l’on nomme des arêtes. Pour faire simple, on va supposer qu’il ne peut pas y avoir plusieurs traits qui joignent deux même points, et qu’un point ne peut pas être lié à lui-même par un trait. Dans les faits, ça ne change rien, mais autant faire simple.
  • On dit qu’un graphe est connexe si l’on peut passer de n’importe quel point à n’importe quel autre en empruntant les arêtes du graphe

Le graphe de gauche n’est pas connexe : on ne peut pas, par exemple, aller d’un sommet rouge à l’autre en passant par les arêtes du graphe.

  • Enfin, nous en aurons besoin, si on se donne un graphe, appelé G, on définit son complémentaire de la manière suivante : c’est le graphe G* avec les mêmes sommets, et deux sommets sont liés dans G* si et seulement s’ils ne le sont pas dans G. C’est une définition aux airs compliqués mais qui ne casse pas des briques quand on le voit graphiquement. En gros, c’est le graphe qui complète le graphe de départ.
Complémentaire

Le graphe tracé en vert est le complémentaire de celui en rouge. Ensemble, ils forment un graphe complet dont les arêtes sont soit vertes, soit rouges (mais aucune n’a les deux couleurs à la fois).

Alors, voilà donc la question : on se fixe un nombre de sommets supérieur ou égal à 4, noté n : existe-t-il plus de graphes connexes ou non connexes ayant n sommets ?

On pourrait essayer de les compter, de les dénombrer, et alors, la réponse serait toute donnée. Hélas, ce n’est pas une affaire aisée… Remarquons que la question ne demande pas le nombre exact de graphes connexes ou non connexes, simplement la catégorie la plus remplie.

Alors ? Une idée ?  Pas de triche hein ?

Réglons ce problème avec un argument massue : le complémentaire de tout graphe non connexe est connexe !

Admettons un instant cette propriété. En d’autres termes, si on a un graphe non connexe, on peut lui associer un graphe connexe, à chaque fois différent : il y a donc au moins autant de graphes connexes que de non connexes.

Pour terminer la preuve il suffit donc de trouver un graphe connexe dont le complémentaire est lui même connexe et le tour sera joué. Et cela fonctionne puisque nous avons pris au moins 4 sommets : il suffit de relier les points en formant une « ligne » non fermée.

Allez, le tour est presque joué. Oui parce que quand je parle d’une propriété, il faut bien la prouver tout de même, vous n’allez pas non plus gober tout ce que je dis, si ?

Alors voilà, prenons donc un graphe non connexe, que l’on appelle allègrement G, et montrons que son complémentaire est connexe. Prenons deux points, nommés x et y, dans ce graphe complémentaire.

  • S’il n’était pas possible de passer de x à y dans le graphe d’origine, alors x et y seront liés par une arête dans le graphe complémentaire.
  • Au contraire, s’il était possible de passer de x à y dans le graphe d’origine, alors il va falloir s’aider d’un troisième point. En l’occurrence, nous choisirons un point z qui n’est pas relié à x par un chemin (et donc, pas relié à y non plus, sinon on pourrait passer de z à y puis de y à x, et donc de z à x.). Ceci est possible car notre graphe de départ n’est pas connexe, rappelons-le. Alors, dans le graphe complémentaire, z est relié à x d’une part et à y d’autre part. Il est donc possible de passer de x à y en empruntant les arêtes du graphe complémentaire.

En bref, pour n’importe quel couple de points (x,y) du graphe complémentaire, on peut passer du premier au deuxième en passant par les arêtes. Bref, notre graphe complémentaire est connexe.

Le tour est joué !

Pour compléter

Encore plus de démonstrations élégantes ? En voici !

  • Le Professeur Culture Précieuse vous propose de trouver le plus court chemin possible pour installer un magasin.
  • Eljj passe en revue des démonstrations du célèbre théorème de Pythagore.
  • Le livre Raisonnements Divins : quelques démonstrations mathématiques particulièrement élégantes de M. Aigner et G.M Ziegler.
Publié dans Conjectures et théorèmes, Curiosités et récréation, Vidéo | Tagué , , | Laisser un commentaire

[Vidéo] De l’ordre dans les tiroirs

Voilà, je me lance dans l’arène ! La première vidéo Automaths est disponible depuis presque une semaine maintenant sur Youtube et concerne un principe simple et pourtant redoutablement efficace : le principe des tiroirs !

Vous souhaitez aller un peu plus loin ? Voici peut-être de quoi satisfaire votre curiosité !

La vidéo est classée Drapeau vert, accessible à tous, mais les précisions qui suivent tiennent davantage du Drapeau rouge.

Rationnels et périodes

Parmi les nombres dits réels, il existe deux sous-catégories de nombres : ceux dits rationnels, qui peuvent s’écrire sous la forme d’une fraction, résultats d’une division de deux nombres entiers, et les irrationnels, ceux qui ne le peuvent pas.

Dans la première catégorie se rangent ainsi les nombres comme 1/3, 47/99 ou 42/187. Ces nombres, si on essaye de les écrire sous leur forme décimale, ont une propriété intéressante :

1/3 = 0.3333333…
47/99 = 0.4747474747…
42/187 = 0.224598930481283422459893048128342245989304812834…

Pourvu que notre calculatrice aille assez loin, on voit apparaître une suite de chiffres qui se répète à l’infini : c’est ce que l’on nomme la période. Il s’avère en fait que tout nombre rationnel, toute fraction, possède une écriture décimale périodique. Et il s’avère que c’est une conséquence du principe des tiroirs !

En effet, lorsque l’on fait une division décimale, soit il n’y a pas de reste, et on s’arrête là : la suite du nombre n’est donc qu’une infinité de zéro après la virgule.

Soit on ne s’arrête jamais. Or, les restes de la division sont toujours inférieurs au dénominateur (il ne peut pas rester 48 morceaux si l’on essaye de partager en 47 parts : en effet, il suffit de retirer de nouveau 47 morceaux et en donner un à chacun. C’est tout de même plus cool non ?)

Nous avons donc un nombre fini de reste possibles alors que notre développement se poursuit à l’infini. Si l’on développe alors le quotient p/q, il n’y a donc que q – 1 restes possibles, allant de 1 à q – 1 (on a exclu le cas du reste valant 0 un peu plus haut). Fatalement, il y aura, au sein des q premières étapes de la division, au moins deux restes identiques, c’est le principe des tiroirs qui nous le dit !

Et puisque la division ne dépend pas de ce qu’il se passe avant ce stade, forcément, les développements à partir de ces deux étapes aux restes identiques sera le même.

Approcher des rationnels

Dans la deuxième catégorie, celle des irrationnels, entrent par exemple √2, π, e et bien d’autres encore. Dans un certain sens, ils sont d’ailleurs bien plus nombreux que les nombres rationnels, mais c’est une autre histoire.

En revanche, il est possible d’utiliser les nombres rationnels pour les approcher d’aussi près que l’on veut. Une méthode est par exemple de prendre ce que l’on appelle les « développements décimaux tronqués ». Par exemple, √2 = 1.41421356237… avec des décimales qui continuent ainsi à l’infini. Ainsi, la suite 1, 1.4, 1.41, 1.414, 1.4142 est une suite de nombres rationnels (et mêmes décimaux) qui approche de plus en plus finement le nombre √2. Seulement, cette approche n’est pas efficace, dans le sens où les dénominateurs de ces fractions sont grands – et donc, les numérateurs sont obligés de suivre. On aimerait ainsi gagner en précision tout en restant avec des dénominateurs raisonnables, plus agréables pour des calculs à la main, comme dans l’ancien temps.

Par exemple, le nombre π a souvent été remplacé par la fraction 22/7 qui est la meilleure approximation au sens où, pour tout dénominateur plus petit que 7, l’approximation de π sera forcément moins bonne.

L’approche de Dirichlet utilisant le principe de tiroirs permet ainsi de contrôler ce dénominateur : si je me donne un entier n et un réel x, je peux approcher ce réel avec une fraction p/q telle que l’erreur est inférieure à 1/nq, mais surtout avec un dénominateur q inférieur à n.

Alors, c’est bien gentil, mais le principe des tiroirs dans tout ça, où intervient-il ?

Pour un nombre, on peut s’intéresser à sa partie fractionnaire, c’est-à-dire, celle qui vient après sa virgule. La partie fractionnaire de 1.5 est 0.5, celle de 1.4978 est 0.4978 et ainsi de suite. Cette partie fractionnaire se situe donc entre 0 et 1, 1 étant exclu, ce que l’on note [0;1[. On notera la partie fractionnaire d’un nombre A entre accolades : {A}.

Nous allons donc regarder les parties fractionnaires {0x}, {1x}, {2x}, {3x}, et ainsi de suite jusqu’à {nx} – il y en a en tout n + 1.

Or, il est possible de découper l’intervalle [0 ; 1 [ en n plus petits intervalles : [0;1/n[, [1/n;2/n[, … [(n-1)/n;1[. Ainsi, si l’on veut ranger les n+1 parties fractionnaires dans les n intervalles construits, il y aura forcément un intervalle qui contiendra deux de ces parties fractionnaires.

Ainsi, on a deux nombres différents, k et h, telles que la différence |{hx} – {kx}| est inférieure à 1/n. Il suffit alors de choisir comme nombre p la différence entre les parties entières de kx et hx, puis comme nombre q la quantité q = k – h, et on aura alors :

|x – p/q| < 1/nq

Ouf, c’est terminé !

Pour compléter

  • L’excellent article de Jean-Paul Delahaye dans Pour la Science de Janvier 2018 (n°483)

 

 

 

Publié dans Vidéo | Tagué , , | Laisser un commentaire

Des codes et des grilles

Drapeau vert : Cet article ne demande aucune connaissance mathématique particulière


La dernière fois, nous avions parlé de méthodes de chiffrement que l’on appelle « par substitution » : une lettre était remplacée par une autre dans l’alphabet. Ces méthodes, aussi ludiques soient-elles, s’avéraient finalement peu fiables.

Pour renforcer la sécurité de la communication, il est possible de transposer les lettres, d’en inverser l’ordre. Aussi, on peut penser à les dissimuler au milieu d’un message bien plus grand, à condition d’avoir une méthode simple pour notre destinataire de trouver les lettres utiles.

Voici quelques exemples simples de ces procédés

La scytale

Utilisée par les spartiates, la scytale est un bâton autour duquel on enroule de manière régulière une bande de papier avant d’écrire un message dessus. Ainsi, en déroulant la bande, l’ordre des lettres du message d’origine est chamboulé.

Une scytale tant artisanale que subliminale. En déroulant le message ABONNEZVOUSAUBLOG!, on obtient ANOUO BEUBG OZSL! NVA

Pour décoder le message ainsi obtenu, il suffit d’enrouler de nouveau la bande autour d’un bâton similaire, rien d’extraordinaire.

Conceptuellement, ce procédé revient à écrire le message selon les lignes d’un tableau qui comporte autant de colonnes que de lettres nécessaires pour faire un tour de la scytale. Dans l’exemple plus haut, je pouvais placer 4 lettres sur une rangée, on utilise donc un tableau à 4 colonnes.

A B O N
N E Z V
O U S A
U B L _
O G !

Vous apercevez un caractère manquant sur la quatrième ligne :  c’est tout simplement parce que je manquais de papier pour l’écrire sur ma bande ! Pas de panique, le message reste déchiffrable. Le message codé correspond à la suite de lettres obtenue en lisant colonne par colonne.

Le problème, c’est que le nombre de combinaison à tester pour déchiffrer le message est très réduit : pour celui qui intercepte le message, il suffit de lire toutes les deux lettres, ou toutes les trois lettres, ou toutes les quatre et ainsi de suite pour arriver au bon résultat. Bref, il n’y a pas vraiment besoin de posséder une exacte réplique du bâton d’origine pour décrypter le message…

Il se peut que la scytale ait également été utilisée comme une méthode d’identification plutôt que de codage, une sorte de mot de passe avant l’heure si l’on veut.

Ainsi, pour être certain de l’identité de l’expéditeur d’un message, il fallait que celui-ci ait rédigé son message à l’aide d’une scytale d’une certaine forme et d’un certain diamètre. Si, en enroulant le message sur la scytale, celui-ci produisait un texte incompréhensible, alors le message était rejeté. Ce procédé aurait permis d’empêcher les espions ennemis de diffuser de fausses informations au sein d’une armée.

La grille de Cardan

Autre époque, autre méthode. La grille de Cardan, du nom du mathématicien Jérôme Cardan, a pour but de masquer un message secret au sein d’un message bien plus long. Pour cela, on utilise une grille à trou que l’on pose sur une feuille de papier et on y inscrit le message à dissimuler. Ensuite, en retirant le cache, on complète le reste de la feuille. Le destinataire n’a plus qu’à utiliser un cache identique pour voir apparaître le message d’origine.

Naturellement, il est possible de compléter le message avec des lettres prises au hasard, mais le but de la manoeuvre ici est de paraître totalement innocent : un message inintelligible attirerait à coup sûr l’attention. Il valait donc mieux compléter intelligemment, en faisant mine de transmettre un message anodin.

Grille de Cardan

Un message secret apparaît lorsque l’on utilise la grille.

La grille de Cardan n’est d’ailleurs pas une méthode de cryptographie à proprement parler. Généralement, on remarque immédiatement qu’un message est crypté puisqu’il est inintelligible, ce qui n’était pas le cas ici. On parlera plutôt de stéganographie, l’art de dissimuler le message.

Toute la difficulté était d’ailleurs ici : à une époque où l’ordinateur n’existait pas, il fallait garder une écriture régulière, ne pas laisser de grands espaces ou trop resserrer les caractères, mais aussi posséder un vocabulaire fourni pour pouvoir compléter le message.

Le problème de cette méthode se trouvait également dans la transmission et la conservation de la grille de décodage : si celle-ci était volé ou perdue, c’est toute la communication qui était rompue !

Les grilles du colonel Fleissner

Restons das les grilles, mais d’un autre genre, puisque nous allons les faire tourner. Ces grilles tournantes ont été popularisées par le colonel autrichien Fleissner dans son ouvrage Handbuch der Kryptographie. Fleissner remplit cette fois une feuille de papier divisée en 36 petits carreaux, ordonnée en carré de 6 carreaux de côté.

La grille, maintenant, est également un carré de 6 carreaux de côté dans laquelle on a toutefois retiré 9 d’entre eux. Mettons que l’on souhaite crypter notre message favori : LESMATHEMATIQUESCESTFANTASTIQUE.

  • D’abord, on place la grille sur la feuille et on complète les trous des 9 premières lettres, ici LESMATHEM.
  • On tourne ensuite la grille d’un quart de tour, dans un sens ou dans l’autre. De cette manière, on masque les lettres déjà inscrites et on révèle 9 nouveaux espaces vides.
  • On continue alors le remplissage de la feuille de papier en utilisant les trous de la grille.
  • On répète le procédé jusqu’à remplir nos 36 cases. Si le message fait plus de 36 lettres, on utilise une autre grille. S’il en fait moins, on complète avec des lettres aléatoires.

Voici une animation de cette méthode :

On remplit la grille case par case, puis on la fait tourner d’un quart de tour et on recommence.

Avec cette grille, le message codé est IASQLTTEIQUSMFEAAUPNTEHTASSESLETCMA. Avec une autre grille, il serait bien sûr différent.

Pour déchiffrer le message, on utilise la même grille que l’on pose sur la feuille, puis on la fait tourner comme pour chiffrer.

La sécurité de cette méthode dépend donc du nombre de grilles qu’il est possible de fabriquer. D’abord, il convient de remarquer qu’il ne faut pas prendre 9 trous absolument au hasard. En effet, si l’on regarde le carreau tout en haut à droite, celui-ci se retrouve en haut à gauche, puis en bas à gauche et enfin, en haut à droite à mesure que nous effectuons les quarts de tours.

Il ne faut donc trouer une et une seule case parmi celles-ci : ne pas en trouver rendrait ces cases inatteignables, en trouer plusieurs demanderait d’écrire plusieurs lettres sur une même case. En observant plus en détails notre grille, on en déduit qu’il faut percer un et un seul trou de chaque couleur sur la grille suivante :

En voilà des couleurs… Pour une grille de Fleissner valable, il faut percer un et un seul trou pour chaque couleur / numéro.

Puisque nous avons 9 couleurs / numéros et que pour chacun deux il y a 4 possibilités de trous, cela donne 49 possibilités, soit 262144 grilles différentes. Alors évidemment, parmi elles il y en a de trop simples comme la grille qui consistes à enlever toute la partie supérieure droite, mais cela fait un nombre raisonnable quand on n’a pas d’ordinateur à portée de main.

D’ailleurs, il est possible d’utiliser des grilles plus grandes, toujours en trouant un quart des positions à chaque fois. En utilisant non pas 6 mais 8 carreaux de côté, il y aura alors 4294967296 possibilités de grilles.

Pour casser un tel chiffrage, il faut alors utiliser une attaque par mot probable : on suppose que le texte contient un mot et l’on essaye de recomposer la grille – ou au moins de réduire les possibilités par ce biais.

Naturellement, il est possible, comme mentionné au début, de combiner ces approches au chiffrement par substitution. Ainsi pourrez-vous espérer communiquer sans vous faire prendre ?

Pour compléter

Publié dans Cryptographie | Tagué , , , , | Laisser un commentaire