Encore du nombre d’or

Quoi ? Encore lui ? J’en avais pourtant parlé dans ma dernière vidéo, et je n’en ai pas fini ?

Eh bien non, fort loin de là ! Aujourd’hui, nous allons voir comment construire et approcher cette « divine proportion ». C’est parti !

La valeur de l’or

Revenons-en donc à la définition du nombre d’or : elle concerne la division d’un segment en deux parties telles qu’en faisant la division de la grande longueur par la petite, on obtient la même chose qu’en divisant la longueur totale par la longueur du grand morceau.

Le petit est au grand ce que le grand est au tout.

En appelant a la grande longueur (bleue) et b la petite (rouge), on obtient alors cette équation :

En mettant cette équation au carré, on en obtient une nouvelle que voici :

On retrouver d’ailleurs là une des propriétés du nombre d’or : le multiplier par lui-même revient à lui ajouter 1. Il n’y a pas de mystère !

Ce genre d’équation, les élèves de 1ère scientifique savent les résoudre à coup de discriminant et sont donc capables d’en déterminer les deux solutions. Oui, car il y a deux possibilités, mais celle qui nous intéresse est évidemment la solution positive, puisque nous parlons de rapport de longueur. On en arrive donc à la conclusion suivante :

Le rectangle alors ?

Tout ça c’est bien beau, mais ce qu’on veut nous, c’est un rectangle d’or, ce rectangle si parfait qu’il se trouve absolument partout – spoiler : non, mais on va quand même en construire un.

Commençons d’abord par tracer un triangle ABC rectangle en B ayant des côtés de l’angle droit AB de longueur 1 et BC de longueur 1/2. Grâce au théorème de Pythagore, on sait que le carré de la longueur de l’hypoténuse AC vaut 1² + (1/2)², soit 5/4. AC a donc pour longueur √5/2.

Traçons alors la droite (BC), puis un cercle de centre C et de rayon AC. Celui-ci coupe la droite en deux points M et N, M étant celui « le plus loin » du point B. Eh bien, la longueur de MB vaut MC + CB soit √5/2 + 1/2, le nombre d’or !

Fib-or-nacci

La suite de Fibonacci est une célèbre suite qui se définit ainsi : ses deux premières termes valent 1 puis, pour obtenir les termes suivants, on fait la somme des deux nombres précédents. Cette suite est donc la suite

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233…

Prenons maintenant les rapports entre les termes consécutifs (1/1, 2/1, 3/2, 5/3, …), on obtient alors une nouvelle suite, dont les valeurs arrondies sont les suivantes :

1, 2, 1.5, 1.667,  1.6, 1.625, 1.615, 1.619, 1.617, 1.618, 1.618

Les termes de cette suite semblent se rapprocher de plus en plus du nombre d’or… et c’est d’ailleurs bel et bien le cas, il ne s’agit pas d’une valeur approchée qui va différer à la 155e décimale.

Ainsi, construire des rectangles ayant pour dimensions des termes consécutifs de la suite de Fibonacci approchera efficacement un rectangle d’or. A vrai dire, si l’on ajoute un carré à l’extérieur de ces rectangles de Fibonacci, la construction de la suite nous dit que le rectangle ainsi obtenu sera également un rectangle de Fibonacci, utilisant les termes suivant de la suite.

Plutôt que de partir de 1 et 1, il est aussi possible de démarrer la suite de Fibonacci par n’importe quels entiers, pourvu que l’on conserve la règle de construction de la suite. Partons par exemple de 2 et 5, nous obtenons :

2, 5, 7, 12, 19, 31, 50, 81, 131, 212…

Et de nouveau, en faisant la division des termes par le précédent, on se rapproche inexorablement du nombre d’or.

Pourtant, la suite de Fibonacci classique est, dans un certain sens, le meilleur moyen de procéder.

Le meilleur moyen

Regardons maintenant une autre version de l’équation que doit vérifier le nombre d’or.

Il se pourrait que vous soyez pris d’une furieuse envie de remplacer φ dans le deuxième membre par 1 + 1/φ. Faisons donc !

Et pourquoi s’arrêter en si bon chemin ? Remplaçons une nouvelle fois φ dans le membre de droite.

Et nous pouvons poursuivre ce procédé à l’infini, si bien que

Nous obtenons ce que l’on appelle un développement de φ en fraction continue, et ce développement à une propriété : il fournit les meilleurs approximations rationnelles de φ.

Ce que ça veut dire, c’est que si on arrête le développement à un certain moment, on obtient alors une fraction a/b qui approche efficacement φ, dans le sens où toute fraction qui approcherait mieux le nombre d’or φ aurait forcément un dénominateur plus grand que b.

Ce nombre par exemple vaut 13/8, soit 1.625. Si l’on veut se rapprocher davantage du nombre d’or avec une fraction, il n’y a pas le choix, il faut un dénominateur plus grand que 8.

Mais, ces deux nombres 13 et 8 ne vous disent pas quelque chose ? Il s’agit des 5èmes et 6èmes termes de la suite de Fibonacci. Il s’avère qu’à l’aide d’un raisonnement par récurrence – laissé en exercice pour ce qui connaissent le procédé – on peut montrer que les approximations de φ obtenues grâce au développement en fraction continue ne sont rien d’autre que les quotients de deux termes successifs de la suite de Fibonacci.

Non seulement la suite de Fibonacci permet d’approcher le nombre d’or, mais c’est en plus la meilleure manière de le faire avec des fractions !

Bonus

Pour compléter

 

 

Publié dans Les Nombres, Vidéo | Tagué , , , , | 3 commentaires

Le carré magique de Bachet

Dans la catégorie des jeux mathématiques, je demande le fameux carré magique ! Le principe est simple et connu de beaucoup : prenez une grille carrée de côté n et placez-y tous les nombres de 1 à n x n, de telle sorte que la somme sur les lignes, les colonnes et les diagonales de ce carré soient les mêmes.

Simple à énoncer, ce problème l’est-il aussi à la résolution ? N’hésitez pas à réfléchir avant de passer à la suite…

En 1612, dans son livre Problèmes plaisants et délectables qui se font par les nombres, Claude-Gaspar Bachet de Méziriac propose une méthode de construction de carré magique pour toute grille carrée d’ordre impair (c’est-à-dire avec un nombre impair de cases sur le côté).

Méthode de Bachet de Méziriac pour construire un carré magique.

  • La première étape consiste à étendre le carré que l’on souhaite compléter en une grille « inclinée »
  • On place alors les nombres en progressant selon les diagonales de cette grille, en partant du haut et en allant vers le bas à droite.
  • Une fois cela fait, on déplace tous les nombres qui sont hors du carré de base. Ceux de gauche sont déplacés à droite, ceux du haut en bas et ainsi de suite pour combler les cases vides.

Cette méthode marche à tous les coups… Mais pourquoi ? C’est bien ce qui nous intéresse ici. Je ne ferai pas une démonstration rigoureuse de cette construction, j’en laisse le loisir aux plus acharnés : l’idée est simplement de présenter les arguments clés de ce principe.

Les diagonales

Avant de commencer, observons les diagonales, déjà remplies par cette méthode. Celles-ci ont toute la même somme – et c’est heureux ! En effet, la diagonale qui part du haut à gauche pour aller en bas à droite comporte des nombres qui progressent de 1 en 1, avec le nombre 25 au milieu.

L’autre diagonale, elle, présente des nombres qui augmentent de 7 en 7, toujours avec 25 au milieu. On parle aussi de progression arithmétique, mais cela n’a que peu d’importance.

Ce qui est important en revanche, c’est que d’une part, cette configuration n’est possible que parce que nous remplissons une grille d’ordre impair – sinon, les deux diagonales du carré ne se croisent pas !.

Aussi, la somme sur ces deux diagonales vaut 7 x 25, soit 175. 25 est en effet la médiane de tous les nombres à inscrire dans le carré – le nombre du milieu, si vous préférez. Bref, tout commence pour le mieux.

Les diagonales somment toutes les deux à 175

Revoir le problème

Nous allons désormais réécrire tous les nombres disposés sur notre carré. Voici notre nouvelle écriture :

Décomposition des nombres de la grille

Vous remarquerez alors que sur les diagonales qui descendent vers bas à gauche – ou qui montent en haut à droite, c’est selon -, tous les premiers chiffres sont les mêmes. Pour les diagonales qui descendent en bas à droite, c’est le second qui est en commun.

Chaque case de notre grille peut donc se traduire par un couple de nombres, le premier étant choisi parmi 1, 2, 3, 4, 5, 6, 7, le seconde parmi 0, 7, 14, 21, 28, 35, 42. Nous appellerons ces deux nombres les identifiants du nombre de départ. Le nombre 41 à placer dans le carré est identifié parle couple (6,35).

L’idée est donc la suivante : compléter les cases vides du carré de sorte que, sur chaque ligne et chaque colonne, les cases aient toutes un premier et un second identifiant différent, à la manière du sudoku. Par exemple, on pourrait aligner (3,21) et (2,14). En revanche, impossible de placer (1,7) et (5,7) sur la même ligne ou colonne, puisque leur deuxième identifiant est le même.

Commençons par regarder le carré intérieur, celui que nous souhaitons compléter. Sur chaque ligne, aucune de ces cases ne portent ni le premier, ni le second identifiant en commun. Il n’y a donc pas de problème pour le moment.

Passons aux nombres au-dessus du carré, et regardons par exemple (1,7). Tous les nombres ayant le 1 comme premier identifiant se trouve sur la diagonale qui descend vers la gauche en partant de cette case, tandis que tous les nombres qui portent 7 comme deuxième identifiant sont sur la diagonale qui descend à droite. Or, ces deux diagonales ne peuvent pas descendre de plus de 6 cases ! En descendant (1,7) de 7 cases, on est donc certain qu’aucune case sur la nouvelle ligne ne portera un identifiant en commun.

La case rouge ne peut avoir aucun identifiant en commun avec les cases de sa ligne et de sa colonne.

Ce raisonnement vaut par ailleurs pour tous les nombres au-dessus et en-dessous du carré.

Reste à s’occuper des nombres à gauche et à droite maintenant. Le raisonnement est très similaire, à cela près que certaines cases ont déjà été déplacées et qu’il faut faire attention que cela ne génère pas de nouveau obstacles.

Voilà tous nos nombres placés ! Il ne reste plus qu’à vérifier.

Sur chaque ligne et chaque colonne, tous les premiers identifiants et tous les seconds identifiants sont différents. Or, il n’y a que 14 places possibles, pour autant d’identifiants existants, c’est donc qu’ils figurent tous sur cette ligne/colonne. Autrement dit, la somme sur chaque ligne ou colonne vaut la somme de tous les identifiants possibles, à savoir la valeur 1 + 2 + 3 + 4 + 5 + 6 + 7 + 0 + 7 + 14 + 21 + 28 + 35 + 42, soit 175

Et voilà le travail !

Pour compléter

  • Claude-Gaspard Bachet de Méziriac, Problèmes plaisants et délectables qui se font par les nombres, consultable à cette adresse.
Publié dans Curiosités et récréation | Tagué , , , | 2 commentaires

[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