Le problème des reines

Dans ma dernière vidéo, j’abordais le lien entre les carrés magiques et le problème des reines. Dans ce dernier, l’énigme consistait à placer n reines sur un échiquier de taille n x n sans qu’aucune reine ne puisse en attaquer une autre.

Des solutions existent pour toute taille d’échiquier strictement supérieure à 3… Il est temps de s’y atteler !

Le problème aux origines

Au départ, il n’y avait qu’un échiquier classique, de taille 8 x 8, et c’est un joueur d’échec allemand, Max Bezzel, qui proposa l’énigme en 1848. En 1850, un certain Carl Friedrich Gauss affirma que ce problème présentait au total 92 solutions (en comptant toutes les possibilités, y compris celles qui ne sont que des rotations d’autres solutions de ce problème).

Mais comme pour tout problème de mathématique, il serait dommage de s’arrêter à un cas particulier. On se demanda alors si le même problème était résoluble pour des tailles d’échiquier différentes.

Notons d’abord que, puisqu’il ne peut y avoir qu’une seule reine par colonne, écrire une solution revient à écrire une liste comportant une seule et unique fois chaque entier de 1 à n. Ces nombres représentent les lignes sur lesquelles placer nos reines. Par exemple, sur l’échiquier 5 x 5 qui suit, la solution présentée peut se résumer par la liste ( 3 ; 5 ; 2 ; 4 ; 1 )

Solution 5 x 5

Une solution pour l’échiquier 5 x 5

Comment alors se rendre compte si la solution donnée est correcte ?

Prenez chaque nombre de cette liste et ajoutez-y le numéro de sa colonne – sa position dans la liste.

Pour le cas précédent, cela donne ( 3 + 1 ; 5 + 2 ; 2 + 3 ; 4 +4 ; 1 + 5 ) soit (4 ; 7 ; 5 ; 8 ; 6). On remarque que tous les nombres obtenus sont différents.

Maintenant, reprenez la liste de départ, et retirez à chaque nombre sa position, sa colonne. Dans l’exemple on a ( 3 – 1 ; 5 – 2 ; 2 – 3 ; 4 – 4 ; 1 – 5 ), soit (2 ; 3 ; -1 ; 0 ; -4). Là encore, tous les nombres sont différents… Eh bien, avec ces deux critères, nous pouvons affirmer que notre liste donne bien une solution au problème des reines.

En effet, récapitulons les conditions au problème de la reine.

  • Il ne peut y avoir qu’une reine par colonne. C’est pour cela que nous pouvons résumer un placement des reines avec des nombres entiers.
  • Il y a une et unique reine par ligne : tous les nombres de 1 à n doivent être présents une et une seule fois dans la liste.
  • Deux reines ne doivent pas partager la même diagonale. C’est ce que l’on vérifie en faisant cette manipulation.

Regardons par exemple ce placement, qui n’est pas une solution du problème des reines.

Placement incorrect

Ce placement s’écrit (1 ; 4 ; 3 ; 5 ; 2). Il respecte les deux premières conditions. Ajoutons donc à chaque nombre sa position dans la liste.

( 1 + 1 ; 4 + 2 ; 3 + 3 ; 5 + 4 ; 2 + 5) fait (2 ; 6 ; 6 ; 9 ; 7). On voit apparaître le nombre 6 en 2ème et 3ème position : c’est parce que les reines des deuxièmes et troisièmes colonnes sont sur la même diagonale ascendante.

Faisons de même avec la soustraction ( 1 – 1 ; 4 – 2 ; 3 – 3 ; 5 – 4 ; 2 – 5), ce qui fait
(0 ; 2 ; 0 ; 1 ; -3). Cette fois, le 0 apparaît en 1ère et 3ème position : c’est parce que les reines des premières et troisièmes colonnes sont sur la même diagonale descendante.

Un test fort pratique donc ! Pour les amateurs de permutation, on cherche donc une permutation P de l’ensemble des entiers de 1 à n telle que P + id et P – id soient injectives. Oui, d’un coup, ça fait plus savant et sérieux que placer des dames sur du carrelage.

D’accord, mais nous on veut les solutions !

Passons donc aux choses sérieuses. Plusieurs cas existent, suivant la taille de votre échiquier.

Cas n°1 : La taille de votre échiquier n’est pas de la forme 6k + 2 ou 6k + 3.

C’est le cas d’un échiquier de taille 5, 6, 7, mais pas de taille 8, puisque 8 = 6 x 1 + 2, ni de 39, puisque 39 = 6 x 6 + 3. Ce cas est très simple puisqu’il suffit de placer les reines en « L ».

Placez une reine sur la deuxième case en partant du bas sur la première colonne. Puis avancez d’une case à droite et deux cases en haut, placez une nouvelle reine. Et ainsi de suite, jusqu’à dépasser du bord supérieur. Placez alors une reine tout en bas dans la colonne suivante et recommencez. Vous avez votre solution !

Solution pour 7

Une solution en escalier pour un échiquier 7 x 7

Cas n°2 : La taille de votre échiquier est de la forme 6k + 2

C’est le cas de 8, 14, 20, et ainsi de suite, de 6 en 6.

Placez les nombres paires d’un côté et les nombres impairs de l’autre. Pour 8, cela donne (2 ; 4 ; 6 ; 8 ; 1 ; 3 ; 5 ; 7).

Inversez le 1 et le 3, puis placez le 5 à la fin : (2 ; 4 ; 6 ; 8 ; 3 ; 1 ; 7 ; 5). Terminé !

Solution 14 x 14

Une solution pour le problème 14 x 14

Cas n°3 La taille de votre échiquier est de la forme 6k + 3

C’est le cas de 9, 15, 21 et ainsi de 6 en 6.4

De la même manière, séparons la liste des entiers selon la parité. Pour 15, cela donnerait donc (2 ; 4 ; 6 ; 8 ; 10 ; 12 ; 14 ; 1 ; 3 ; 5 ; 7 , 9 , 11 ; 13 ; 15)

Il faut ensuite placer le 2 à la fin de la liste des pairs puis le 1 et le 3 à la fin de la liste des impairs, ce qui donne ( 4 ; 6 ; 8 ; 10 ; 12 ; 14 ; 2 ; 5 ; 7 ; 9  ; 11 ; 13 ; 15 ; 1 ; 3)

Solution sur l’échiquier 15×15

Et c’est terminé !

Combien de solutions ?

C’est bien beau tout ça, mais combien de solutions a-t-on ? Ces nombres ont été déterminés pour des échiquiers de taille allant jusqu’à 27 : on compte 234907967154122528 – plus de 200 millions de milliards – solutions au total, ce qui se réduit à 29363495934315694 – plus que 29 millions de milliards.

Les plus curieux pourront consulter les séquences A002562 et A000170 sur l’OEIS.

Pour le reste, nul ne sait vraiment. L’hypothèse a été faite que le nombre total était de l’ordre de n!/c où c est un réel, environ égal à 2,54, mais nul ne le sait vraiment. Alors, si vous vous ennuyez un jour…

Pour aller plus loin

Publié dans Curiosités et récréation | Tagué , , , , , | 1 commentaire

Les moyens de moyenner

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


Si vous avez fait un tour sur Blogdemaths, vous avec surement lu cet article poétiquement intitulé Harmonique, nique, nique, qui vous présentait une autre manière de calculer une moyenne, selon le contexte. C’est ce que l’on appelle la moyenne harmonique.

Seulement, des moyennes, il en existe une belle fournée – à vrai dire, on peut en fabriquer autant qu’on veut, mais certaines sont plus utiles que d’autres…

Petit tour d’horizon !

C’est quoi une moyenne ?

Avant d’aller plus loin, il convient de rappeler ce que l’on appelle une « moyenne ». Dans vos souvenirs de collège, vous avez peut-être inscrit quelque part que pour calculer une moyenne, il suffit d’additionner toutes les valeurs puis de diviser par le nombre de valeurs.

Hélas ! C’est une formule que vous retenez, pas le concept qui est derrière.

Prenons l’exemple de Paulo le cheval qui doit traîner sa carriole et les personnes  l’intérieur. Il s’avère que, dans sa charrette, Paulo transporte 5 personnes dont les poids sont de 70, 42, 84, 24 et 60 kilogrammes – non, je ne sais pas si un vrai cheval est bien capable de déplacer une telle charge, mais c’est un cheval mathématique ici, ne sous-estimez pas ses capacités.

Au total, Paulo doit donc déplacer 280 kilos, et c’est bien tout ce qui l’intéresse. Tout au plus pourrait-on lui murmurer à l’oreille qu’il doit transporter 5 personnes de 280/5=56 kilos chacune que ça ne lui changerait rien.

Paulo et Paula sont prêts à partir..

C’est là tout l’intérêt de la moyenne : à partir de plusieurs observations faites sur un certain nombre d’individus, il faut assigner à chacun de ces individus une valeur qui laisse le total des observations inchangé. Dans notre cas, que les 5 personnes aient le poids énoncé plus haut ou pèsent toutes 56 kg, cela ne change rien pour notre cheval.

Toute la nuance de la moyenne réside en fait dans ce mot « total ». S’il nous paraît parfois raisonnable de convertir le mot « total » en « somme », il y a des situations où l’on ferait mieux de se retenir violemment.

D’autres moyennes

A ce titre, on peut reprendre la moyenne harmonique présentée sur Blogdemaths.

Si un automobiliste roule à 60 km/h durant une certaine distance puis à 100 km/h durant une même distance, sa vitesse moyenne durant son parcours sera de 75 km/h, et non de 80. Faire une somme de vitesse n’a pas de sens. Tout ce que l’on peut faire, c’est additionner des distances ou des temps.

Dans un autre registre, imaginez donc que le prix de la baguette double l’année prochaine, puis, suite à une crise massive, soit multiplié par 8 l’année suivante. Quelle aura été son augmentation moyenne ?

Au total, la baguette a été multipliée par 2 puis par 8, soit par 16 en deux ans. Notre total est ici déterminé par une multiplication. Il faut maintenant prendre la racine carrée de 16, soit 4, pour obtenir la multiplication moyenne du prix du pain. Multiplier par 2 puis par 8 revient bien à multiplier deux fois de suite par 4. C’est ce qu’on appelle la moyenne géométrique.

Moyenne géométrique

Si l’on considère deux nombres positifs a et b, la moyenne géométrique g de ces deux nombres est telle que a/g = g/b. Autrement dit, on se retrouver avec g²=ab, d’où :

g=\sqrt{ab}

On peut interpréter ce résultat géométriquement (ah, ah !) : g est la longueur du côté du carré ayant même aire que le rectangle ayant pour longueurs de côté les nombres a et b.

Autre interprétation dans un triangle rectangle : la moyenne géométrique de a et b est la longueur de la hauteur issue de l’angle droit qui partage l’hypoténuse de longueur a+b en deux segments de longueur a et b. Et comme un dessin vaut mieux qu’un long discours…

Moyenne géométrique

Moyenne géométrique de deux nombres positifs

On peut, pour s’en convaincre, remarquer que les deux angles signalés en vert ici sont égaux. Or, les amateurs de trigonométrie auront noté que la tangente de ces angles vaut a/g pour l’un et g/b pour l’autre : on en revient à la définition de la moyenne géométrique.

Notons au passage que la moyenne arithmétique correspond à la longueur du rayon du cercle circonscrit à ce triangle rectangle. Elle  est donc forcément supérieur ou égale à la moyenne géométrique.

Il est également possible de placer la moyenne harmonique sur ce dessin, ainsi qu’une autre moyenne : la moyenne quadratique, qui vaut :

q = \sqrt{\frac{a^2+b^2}{2}}

Moyennes

Différentes moyennes sur un seul dessin

Pour les amateurs de rugby, sachez au passage que la moyenne géométrique vous permettra de placer optimalement votre ballon dans le cas d’une tentative de transformation d’essai.

L’angle est maximal lorsque la longueur x est la moyenne géométrique des longueurs a et b.

Pour aller un peu plus loin dans la moyenne…

La moyenne géométrique, comme les moyennes arithmétiques et harmoniques, peut se généraliser à plus de deux observations : il suffit de prendre la racine n-ième du produit de toutes les observations. Ainsi, si le prix du pain était multiplié par 2, puis par 9, puis par 12, on aurait une multiplication moyenne de \sqrt[3]{2\times 9 \times 12}, soit un prix du pain multiplié en moyenne par 4 chaque année.

Sachez également que si ces moyennes ne vous conviennent pas, il vous est possible d’en créer à volonté : si l’on considère une fonction f qui est monotone sur l’ensemble des réels strictement positifs, la formule

f(m)=\frac{f(a)+f(b)}{2}

permet de définir une moyenne selon f. En prenant par exemple f(x)=x, on retrouve la moyenne arithmétique. En prenant f(x)=ln(x), c’est la moyenne géométrique…

Ne vous reste plus qu’à donner un sens à tout cela…

Pour compléter

Publié dans Curiosités et récréation | Tagué , , , , | Laisser un commentaire

Solides de Platon, d’Archimède et de Catalan

Ce billet de blog fait écho à la dernière vidéo publiée sur la chaîne, dans laquelle j’abordais les formes des dés et parlais vaguement des solides de Catalan. Il est temps d’éclaircir le mystère.

C’est l’heure du dual !

Lorsque l’on parle de solides, on ne peut évidemment pas passer outre les solides de Platon, au nombre de 5.

Les 5 solides de Platon : Tétraèdre régulier, Cube, Octaèdre régulier, Dodécaèdre régulier et Icosaèdre régulier

Rappelons les conditions d’entrée dans ce club très fermé :

  • Le polyèdre doit être convexe (sans creux, il doit pouvoir être posé sur chacune de ses faces)
  • Toutes les faces doivent être des polygones réguliers identiques
  • Elles ne doivent pas se couper, hormis sur les arêtes
  • Tous les sommets doivent être le point de rencontre du même nombre de faces

Forcément, avec toutes ces conditions, pas étonnant de ne compter que peu de membres. Et encore, ce nombre pourrait être, d’une certaine manière, réduit à 3 si l’on regroupe ensemble les polyèdres duaux.

Pour construire le dual d’un polyèdre régulier, il suffit de placer un point au centre de chacune de ses faces. Il faut ensuite relier les points qui appartiennent à des faces adjacentes, qui partagent une arête. Par exemple, en faisant ce procédé, on voit que l’octaèdre est le dual du cube.

Octaèdre et cube sont duaux.

De la même manière, on se rendra compte que dodécaèdre et icosaèdre sont duaux et que le tétraèdre est son propre dual.

Puisque les sommets de l’un deviennent les faces de l’autre et inversement, deux polyèdres duaux partagent alors les mêmes propriétés de symétrie. On se restreint alors à trois groupes de symétrie : les symétries du tétraèdre, du cube et du dodécaèdre

Relâcher les conditions

Tout ça, c’est bien beau, mais avoir un club fermé n’est pas forcément pour nous plaire : c’est assez ennuyeux, en somme. Relâchons légèrement les conditions : nous allons maintenant regarder les polyèdres convexes qui sont composés de plusieurs sortes de polygones réguliers, mais qui ont toujours la même propriété sur leur sommet : ceux-ci doivent être le point de rencontre des mêmes types de face, dans le même ordre.

Ces solides sont appelés les solides d’Archimède, et on en exclut en général les prismes et anti-prismes, fort peu intéressants.

Un exemple de solide d’Archimède, il s’agit du cuboctaèdre : composé de 6 carrés et 8 triangles équilatéraux, chaque sommet est entouré d’un triangle, d’un carré puis d’un triangle et de nouveau un carré

Cuboctaèdre

Comment obtenir tous ces solides ? Eh bien nous allons faire subir toutes sortes de choses à nos solides de Platon.

Le cuboctaèdre peut par exemple être vu comme un cube que l’on a tronqué au niveau des sommets, jusqu’au milieu de l’arête (on parle de solide rectifié). En s’arrêtant un peu avant, de manière à avoir des hexagones réguliers comme faces, on obtient un cube tronqué. En continuant l’opération, on arrivera finalement jusqu’à l’octaèdre tronqué, puis l’octaèdre.

La troncature des sommets permet de passer du cube au cube tronqué, au cuboctaèdre, à l’octaèdre tronqué, à l’octaèdre.. et inversement !

En tronquant un octaèdre, on peut faire tout le cheminement dans le sens inverse. Mais l’on peut également tronquer un cuboctaèdre : on obtient bien sûr un… cuboctaèdre tronqué, composé de 26 hexagones, octogones et carrés. On parle également de cube bitronqué

Tronquer un cuboctaèdre donne un nouveau solide d’Archimède

Quitte à bien limer notre solide, il est également possible d’attaquer ses arêtes : on dit alors que le solide est biseauté

En biseautant notre cube, on obtient un petit rhombicuboctaèdre

Dernière torture à infliger à notre solide, un peu moins évident : il est possible de l’adoucir. Cette opération consiste à écarter les faces et les faire pivoter de manière à faire entrer des triangles équilatéraux dans les espaces.

Tuto : Comment adoucir un cube ?

Et… C’est à peu près tout. En faisant de même avec le tétraèdre et le dodécaèdre, on obtient alors un total de 13 solides d’Archimède différent, dont toute la liste se trouve ici.

Vous y trouverez notamment le fameux icosaèdre tronqué, plus connu sous l’appellation ballon de football !

Et Catalan alors ?

J’y viens, rassurez-vous ! Les solides de Catalan adoptent le point de vue inverse des solides d’Archimède : les sommets sont différents mais toutes les faces doivent être les mêmes, indissociables les unes des autres.

Nous avons à notre disposition 13 solides d’Archimède, aux sommets identiques, et nous avons également une formidable transformation : le dual. Il faudra toutefois légèrement modifier la construction par rapport aux polyèdres réguliers, mais le principe reste le même : les sommets deviennent les faces et les faces deviennent des sommets.

Puisqu’un solide d’Archimède a tous ses sommets équivalents, le dual d’un solide d’Archimède aura toutes ses faces équivalentes. Il y a ainsi 13 solides de Catalan.

Voici par exemple le dual du cuboctaèdre, qui est le dodécaèdre rhombique

Le dual du cuboctaèdre est le dodécaèdre rhombique

Pour découvrir tous les solides de Catalan, c’est par ici !

Pour compléter

  • Le site Mathcurve présente les polyèdres archimédiens et les liens avec les pavages du plan et de la sphère
  • Pour visualiser les solides et les transformations pour passer de l’un à l’autre : https://polyhedra.tessera.li
Publié dans Curiosités et récréation, Vidéo | Tagué , , , , , | 1 commentaire

Paradoxe des deux enfants – Episode 2 !

Pour le premier épisode : cela se passe ici ! Rassurez-vous, il n’est pas utile de comprendre toute la vidéo pour bien suivre la suite du raisonnement !

Ce paradoxe peut s’expliquer en deux mots : probabilité conditionnelle

Peut-être vous êtes-vous dit que l’on calculait à chaque fois les mêmes probabilités, qu’il n’y avait pas lieu que celles-ci changent. Hélas !

A chaque fois, l’événement « Avoir deux filles » était conditionné suivant d’autres événements. Ainsi, la probabilité d' »Avoir deux filles » sachant l’événement « Le couple a au moins une fille » est de 1/3, alors que la probabilité de l’événement « Avoir deux filles » sachant l’événement « Le couple a une fille née un mardi » est de 13/27

Heureusement, une formule bien connue nous permet de nous y retrouver. Nous l’avons déjà rencontrée dans un précédent article, il s’agit de la formule de Bayes.

Dans le premier cas, cette formule s’écrit comme suit (pour rappel, le | se lit « sachant que ») :

P(Le couple a deux filles | Le couple a au moins une fille) = P (Le couple a au moins une fille | Le couple a deux filles) x P (Le couple a deux filles) / P (Le couple a au moins une fille)

  • P (Le couple a au moins une fille | Le couple a deux filles) = 1. Enfin, si le couple a deux filles, c’est qu’il en a au moins une.
  • P (Le couple a deux filles) = 1/4. En effet, chaque enfant a une chance sur 2 d’être une fille, et 1/2 * 1/2 = 1/4
  • P (Le couple a au moins une fille) = 3/4. On peut le voir comme étant 1 – P (Le couple a deux garçons), donc 1 – 1/4 = 3/4

En fin de compte, on a bien P(Le couple a deux filles | Le couple a au moins une fille) = 1/3

Obtenir l’information

Oui mais voilà, je n’ai pas fini de vous retourner le cerveau ! Voici deux formulations pour vous faire travailles vos petits méninges :

  1. On demande à M. Dupond, qui a deux enfants, s’il a au moins une fille. Il répond « Oui »
  2. On demande à M. Dupont, qui a deux enfants, de lui donner le sexe d’un de ses enfants, il répond « Fille »

Quelle est la probabilité que chacun de ces messieurs aient deux filles ?

Pour le premier, rien ne change : c’est 1/3. On est dans le même cas de figure.

Pour le deuxième en revanche, imaginez que M. Dupont ait un garçon et une fille. Il aurait très bien pu répondre « Garçon » après tout ! Contrairement aux apparences, on ne regarde pas les mêmes événements.

Imaginons que M. Dupont choisisse au hasard un de ses enfants, sans préférence, et en donne le sexe. Voici toutes les possibilités, suivant le sexe de ses enfants.

Nous cherchons donc la probabilité que M. Dupont ait deux garçons sachant qu’il a répondu « Garçon ». Utilisons la formule de Bayes :

P(M. Dupont a deux filles| M. Dupont répond Fille) = P(M. Dupont répond Fille |M. Dupont a deux filles) x P(M. Dupont a deux filles) / P(M. Dupont répond Fille)

  • P(M. Dupont répond Garçon |M. Dupont a deux garçons) = 1. Si M. Dupont a deux garçons, il répondra forcément Garçon a la question
  • P(M. Dupont a deux garçons) = 1/4, comme plus haut
  • P(M. Dupont répond Fille) = 1/2. Il suffit d’additionner toutes les probabilités dans l’arbre, lorsque M. Dupont répond Fille : 1/4 + 1/8 + 1/8 = 1/2

Finalement P(M. Dupont a deux filles| M. Dupont répond Fille)  = 1/2

Non seulement, certaines informations ne sont pas anodines, mais en plus, l‘acquisition de l’information peut tout changer !

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

Démonstrations par récurrence

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


Faire des mathématiques, c’est en grande partie démontrer, prouver des théorèmes, des propriétés. Pour cela, plusieurs méthodes différentes peuvent être employées, suivant les cas de figures.

Lorsque la propriété qui nous intéresse dépend d’un nombre entier, il est souvent possible d’utiliser ce que l’on appelle le raisonnement par récurrence.

Le principe

La démonstration par récurrence se passe en trois étapes :

  • Initialisation : On trouve un entier pour lequel la propriété que nous souhaitons démontrer fonctionne
  • Hérédité : On montre que si la propriété est vérifiée pour un certain entier plus grand ou égal à celui choisi pour l’initialisation, alors la propriété reste vraie lorsque l’on passe à l’entier suivant.
  • Conclusion : La propriété est donc vraie pour tous les entiers supérieurs à notre entier d’initialisation

On parle dans ce cas de récurrence simple. D’autres schémas de récurrence plus complexes existent également.

Globalement, le raisonnement par récurrence peut être vu comme une chute de dominos :

  • On fait tomber le premier domino : c’est l’initialisation
  • On sait que nos dominos sont placés de telle sorte que si l’un tombe, il entraîne le suivant dans sa chute : c’est l’hérédité
  • Par conséquent, tous nos dominos seront tombés

D’autres analogies peuvent être imaginés : la propagation d’une maladie – très contagieuse pour le coup – dans une population ou de la flamme d’une allumette à ses plus proches voisines. A la fin, toutes les personnes seront malades et toutes les allumettes seront enflammées.

Il ne faut d’ailleurs pas oublier l’initialisation ! Placer ses dominos, c’est bien, mais si l’on ne fait pas tomber le premier, ça ne sert à rien.

Notez par ailleurs que la démonstration par récurrence permet d’établir une propriété sur tous les entiers, et il y en a une infinité ! Ca fait un sacré paquet de dominos. Henri Poincaré qualifie d’ailleurs ce type de démonstration d’  « instrument qui permet de passer du fini à l’infini. ». En ne faisant tomber les dominos qu’un par un, on finit pourtant par tous les faire s’écrouler.

Des exemples !

Une légende raconte qu’un professeur, excédé par sa classe fort pénible, leur demanda comme punition de calculer la somme de tous les nombres entiers de 1 à 100. Seulement, dans cette classe se serait trouvé un élève du nom de Carl Friedrich Gauss qui, au bout de quelques secondes seulement, aurait donné la réponse : 5050.

Gauss… Plus vraiment écolier.

Pour cela, Gauss avait écrit la somme dans un sens, puis juste en dessous, dans l’autre :

1 + 2 + 3  …. +  98 + 99 + 100
100 + 99 + 98 +… + 3 + 2 + 1

En additionnant par colonne, on trouve alors

101 + 101 + 101 + … + 101 + 101

Soit une somme de 100 fois le nombre 101, qui vaut 10100. Il suffit alors de diviser par 2 pour obtenir le résultat, 5050.

Cette astuce, on peut l’utiliser pour n’importe quel nombre :

  • La somme des entiers de 1 à 1 vaut 1 x (1+1) / 2, soit 1
  • La somme des entiers de 1 à 2 vaut 2 x (2+1) / 2, soit 3
  • La somme des entiers de 1 à 3 vaut 3 x (3+1) / 2, soit 6
  • La somme des entiers de 1 à n vaut n x (n+1) / 2

Nous avons une propriété qui dépend de l’entier n, nous allons donc la montrer par récurrence, en suivant les étapes plus haut. Nous noterons donc P(n) le prédicat « La somme des entiers de 1 à n vaut n x (n+1) / 2″

  • Initialisation : La somme des entiers de 1 à 1 vaut 1 x (1+1) / 2, soit 1. P(1) est vraie
  • Hérédité : On suppose que, pour un certain n, P(n) est vraie, et on va en déduire que P(n+1) est vraie. Pour cela, écrivons P(n+1), il suffit de remplacer tous les n par n+1 : « La somme des entiers de 1 à n+1 vaut (n+1) x (n+1+1) / 2, soit (n+1)(n+2)/2″.

Par hypothèse de récurrence, on a

1 + 2 + 3 + 4 + … + n = n x (n+1) / 2

En ajoutant n + 1 de chaque côté et en réarrangeant les calculs, on a :

1 + 2 + 3 + 4 + … + n + (n +1) = n (n+1) / 2 + (n+1)
1 + 2 + 3 + 4 + … + n + (n +1) = n (n+1) / 2 + 2(n+1) / 2
1 + 2 + 3 + 4 + … + n + (n +1) = [n (n+1) + 2(n+1)]  / 2
1 + 2 + 3 + 4 + … + n + (n +1) = (n+1) (n+2)  / 2

Si P(n) est vraie, alors P(n+1) est vraie : la propriété est héréditaire.

  • Conclusion : Pour n’importe quel entier positif n, la somme des entiers de 1 à n vaut n(n+1)/2

Evidemment, on a ici tout détaillé et raconté, pas la peine de s’épancher autant sur les détails pour rédiger une récurrence. Un autre exemple de raisonnement par récurrence est celui d’une existence de solution à l’énigme des tours de Hanoi, que vous trouverez sur cette vidéo :

Attention aux pièges !

Maintenant, il est temps de faire une nouvelle preuve : Toutes les chaussettes sont de la même couleur. Non, vous ne rêvez pas, et je m’empresse de vous le démontrer par récurrence. Ma propriété sera donc P(n) : Pour tout groupe de n chaussette, toutes les chaussettes sont de la même couleur.

  • Initialisation : n = 1, Dans tout groupe de 1 chaussette, toutes les chaussettes sont de la même couleur… Logique !
  • Hérédité : Supposons que pour un certain n, P(n) soit vraie, et regardons un groupe de n+1 chaussettes :
    • Si on prend les n premières chaussettes, par hypothèse de récurrence, celles-ci sont toutes de la même couleur (par exemple, rouge, peu importe)
    • Si on prend les n dernières, celles-ci sont aussi de la même couleur. Or, dans celles-ci, vu ce qu’on a raconté juste avant, on sait la couleur de certaines : elles sont rouges
    • Les n+1 chaussettes sont toutes de la même couleur.
  • Conclusion : Pour tout n, dans un groupe de n chaussettes, toutes les chaussettes sont de la même couleur

Bon, la conclusion est absurde, n’est-ce pas ! Il doit y avoir une erreur.

Deux interprétations différentes peuvent la retrouver :

  • Soit on a mal initialisé : en prenant 2 chaussettes, on n’est pas sûr que ces 2 chaussettes soient de la même couleur
  • Soit on n’a pas fait assez attention dans l’hérédité : pour passer de 1 à 2 chaussette, notre raisonnement ne tient pas, puisque cela consiste à faire deux groupes de 1 chaussette, sans chaussette commune…

Bref, la récurrence, c’est bien pratique, mais à manipuler avec précaution !

Pour compléter

Publié dans Conjectures et théorèmes | Tagué , , , | Laisser un commentaire

Boire ou conduire, il faut choisir !

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


Les vacances ont débuté pour certains, arrivent bientôt pour d’autres. Peut-être prendrez-vous la route cet été, qui sait ?

Vous connaissez certainement ce slogan : celui qui conduit, c’est celui qui ne boit pas. Une statistique donne en effet le ton : l’alcool est en cause dans près de 30% des accidents mortels.

Seulement, dans ce cas, après un rapide calcul, on se rend compte que cela signifie que 70% des accidents sont causés par des personnes ayant bu de l’eau. C’est donc que l’eau est plus meurtrière que le vin !

Alors, vraiment dangereux l’alcool ? C’est l’heure de l’article de maths rabat-joie !

Différences de fréquence

Ce raisonnement est bien évidemment absurde ! Lorsqu’on lit la phrase  » l’alcool est en cause dans près de 30% des accidents mortels », il ne faut pas comprendre qu’on a 30% de risque d’avoir un accident mortel si l’on a consommé de l’alcool. On parle en fait d’un événement conditionnel : si l’on choisit uniformément au hasard un accident mortel – ce qui est quand même bien morbide, on ne va pas se le cacher -, la probabilité que l’alcool soit en cause dans celui-ci est d’environ 0.3, soit 30%.

Autrement dit, la probabilité que de l’alcool ait été consommé sachant qu’un accident a eu lieu est de 0.3, ce que l’on écrit de manière plus condensée P( Alcool | Accident ) = 0.3. Le | se lit alors « sachant ».

Rajoutons alors une information à notre énoncé : environ 2% des conducteurs prennent le volant alors qu’ils ont consommé de l’alcool, ce qui signifie qu’en prenant un conducteur au hasard, accident ou pas, on a une probabilité de 0.02 que celui-ci ait pris de l’alcool avant d’embarquer en voiture. On note alors P( Alcool ) = 0.02

D’entrée on remarque la différence des deux fréquences : quand l’on considère tous les conducteurs, on a 2% de personnes ayant consommé de l’alcool alors qu’en se restreignant à un plus petit groupe, on en trouve 30%. C’est donc que, vraisemblablement, il y a un lien entre ces deux groupes !

La formule de Bayes

Pour connaître « l’influence » de l’alcool sur la survenue d’accidents, il faudrait plutôt calculer la probabilité P( Accident | Alcool ). Et cette probabilité, c’est la formule de Bayes qui va nous la donner.

Formule de Bayes

La Formule de Bayes

Pour plus d’informations et d’explications sur cette formule, n’hésitez pas à consulter ce billet très bien rédigé : http://dridk.me/le-theoreme-de-bayes.html

Dans notre cas, le « A » est l’accident, le « B » est la consommation d’alcool, et nous obtenons donc :

 

Nous n’avons pas accès à la probabilité d’avoir un accident en général. Toutefois, nous pouvons faire le même calcul pour les personnes ne consommant pas d’alcool :

La probabilité d’avoir un accident étant – hélas – non nulle, on peut alors diviser les membres de gauche et de droite de nos deux égalités.

Morale de l’histoire : en prenant de l’alcool, on a 21 fois plus de risques d’avoir un accident que lorsque l’on n’en prend pas.

Evidemment, tous ces calculs ont leur limite – on met dans le même sac les personnes ayant 0.5 g ou 5g d’alcool par litre de sang, on ne considère que des conducteurs seuls et on a une estimation pas forcément réaliste du nombre de personnes roulant malgré leur consommation d’alcool – mais ils permettent de mieux comprendre ces chiffres que l’on nous donne.

Allez, soyez prudents !

Publié dans Actualité | Tagué , , , | 2 commentaires

C’est quoi un pavage ?

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


Je dois vous faire une confession : lorsque je visite certains monuments comme les châteaux et les églises, je ne peux m’empêcher d’aborder leur architecture par une approche mathématique : forme des voûtes, symétries, mais surtout pavages.

Oui, les pavages, ces fameux pavages qui font tant désespérer ma femme lorsqu’elle me surprend à prendre en photo les fenêtres du château de Blois plutôt que de m’intéresser à la chambre du roi -enfin, sauf lorsque le sol présente lui aussi un joli motif ! Alors voilà, il faut bien que je m’explique un peu, mais commençons par le commencement !

C’est quoi un pavage ?

Le pavage, c’est tout bêtement le carrelage de votre salle de bain !

Plus précisément, on se donne un nombre fini de formes géométriques, que l’on appelle les tuiles. Restons dans le classique et commençons avec une dalle de carrelage carré. Le but de la manoeuvre, c’est de recouvrir tout le sol de votre salle de bain à l’aide de ces petits carrés, sans laisser le moindre trou et sans que les carrés ne se chevauchent, bien évidemment.

Ce carrelage est un pavage ayant un carré pour tuile de base.

Vous avez réussi ? Bravo ! Vous avez réalisé le pavage de votre salle de bain. Alors, nuançons tout de même : pour réaliser un pavage proprement dit, il faut paver une salle de bain infiniment grande.

Plusieurs motifs différents

Pavage d’Escher, utilisant des lézards comme tuiles

Pour notre premier pavage, nous avons commencé simplement avec un carré, mais il est possible d’utiliser d’autres tuiles de base, comme des triangles et les hexagones réguliers, ou d’autres un peu plus compliquées.

Un pavage utilisant des hexagones légèrement déformés

Les hexagones, d’ailleurs, se retrouvent aussi dans la nature comme par exemple dans les ruches ou dans la forme des colonnes de basalte : il s’avère que ce pavage est le « plus économique », dans le sens où, si l’on souhaite mettre des joints entre les tuiles de notre pavage, à surface de tuile donnée, c’est le pavage hexagonal qui nous permettra d’économiser le plus de joints – et de temps ! Ce théorème porte le nom du théorème du nid d’abeilles et a été prouvé en 1999 par Thomas Hales, autant dire qu’il est très récent.

Les abeilles seraient-elles de brillantes mathématiciennes ?

On peut bien sûr explorer les polygones non réguliers : si un pentagone régulier ne permettra jamais de paver le plan, d’autres pentagones feront un joli carrelage, comme c’est par exemple le cas dans le pavage du Caire.

Pavage du Caire, quatre pentagones sont assemblés pour former un hexagone

Rien ne nous interdit également d’utiliser deux ou trois tuiles différentes et de les combiner pour paver le plan : c’est par exemple le cas du pavage « carré adouci » qui utilise des tuiles en forme de carrés et de triangles équilatéraux.

Notez d’ailleurs que, dans ce pavage, chaque sommet du polygone est le point de rencontre de deux carrés et de trois triangles : un tel pavage est dit uniforme, et il en existe 11 au total.

On peut encore aller plus loin selon le nombre de points de rencontre différents que l’on s’impose, mais pour cela, je vous conseille la très complète vidéo d’Eljj sur le sujet.

Une des fenêtres du château de Blois, à l’origine de cet article !

Mais pourquoi on fait ça ?

Un pavage, c’est joli, c’est mignon, mais à quoi ça sert ? L’intérêt de l’étude de ces pavages remonte au XVIIIe siècle, avec l’abbé René Just Haüy. Celui-ci eut en effet le malheur de laisser tomber un cristal de calcite, lequel se brisa alors. Surpris, puisque ces cristaux étaient supposés très résistants, l’abbé essaye alors de briser d’autres cristaux de son importante collection à l’aide d’un marteau. Il n’y parvint que selon certains angles bien précis. Il continua ainsi ses coups de marteaux et obtint une forme semblable à celle d’un cristal intact, mais en plus petit bien entendu.

Les cristaux, à l’origine de la fascination pour les pavages ?

L’idée lui vint alors qu’un cristal serait en fait l’assemblage de mailles de petites tailles, mais toujours de la même forme : tout comme un carré peut être découpé en 4 carrés plus petits, il serait possible de découper un cristaux en un certain nombres de mailles plus petites… Du moins pendant un temps. Lorsque ce découpage n’est plus possible, on obtient alors une maille élémentaire.

Un cristal serait donc l’assemblage de ces mailles élémentaires, toutes similaires et collées les unes avec les autres selon leur face.

La question que l’on se pose alors est celui de la forme des mailles : quelles sont les possibilités ? Contrairement à ce que nous avons fait avec nos pavages, il ne s’agit plus ici de paver un plan avec des dalles mais de remplir tout l’espace avec des solides, des polyèdres plus précisément.

Le plan comme départ

Le remplissage de tout l’espace est bien complexe, ceci dit ! Pour comprendre ceux-ci, simplifier le problème n’est pas du luxe, et une première idée est de se restreindre au plan, aux pavages. On chercha donc à classer tous les pavages du plan possible à l’aide d’une seule tuile polygonale :

  • D’abord, il est possible de paver le plan avec n’importe quelle tuile triangulaire ou n’importe quel quadrilatère. Ca c’est fait.
  • Ensuite, dès que l’on a des polygones de plus de 7 côtés, ce n’est pas possible, peu importe la forme du polygone.

Restent alors les pentagones et hexagones. Le but est donc de trouver des conditions que doivent remplir les tuiles pentagonales ou hexagonales pour pouvoir remplir le plan.

Les hexagones qui pavent le plan se divisent alors en trois classe, un même hexagone pouvant appartenir à plusieurs classes différentes.

Pour le pentagone, obtenir un résultat définitif a été bien plus compliqué. A plusieurs reprises, des mathématiciens ayant affirmé avoir obtenu une classification complète des pentagones pavant le plan se sont vus contredits par la découverte d’un nouveau modèle. On citera notamment Marjorie Rice, en 1977, ajouta pas moins de 4 classes à la collection, alors même qu’elle n’a suivi aucune formation mathématique particulière !

La question fut réglée en 2017, lorsque Michael Rao prouva, à l’aide de l’informatique, qu’il n’y avait que 15 classes de pentagones qui pavent le plan. Bref, pour le plan, c’est fini.

Les 15 classes de pavages pentagonaux.

Pour l’espace… Il faudra encore de petits efforts !

Pour compléter

Publié dans Curiosités et récréation | Tagué , , , | 1 commentaire