Où faut-il construire ces palais ? - Micmaths

J'étais en train de lire ce livre de John Conway et Neil Sloane et je suis tombé, page 25, sur un problème étonnant. À quel endroit M dictateurs hostiles doivent-ils construire leur palais sur une planète afin d'être le plus loin possible les uns des autres ? On reconnaît bien à la façon dont le problème est formulé de façon pas du tout académique l'esprit des deux auteurs John Conway et Neil Sloane qui sont tous les deux des mathématiciens assez atypiques. John Conway c'est à lui notamment qu'on doit le jeu de la vie encore le nœud de Conway dont j'avais parlé dans cette vidéo. Et Neil Sloane c'est à lui qu'on doit par exemple entre autres l'OEIS, l'encyclopédie en ligne des nombres entiers. Alors si on veut formuler la question en des termes plus mathématiques, imaginez une sphère (la planète) sur laquelle vous devez placer un certain nombre M de points (les palais) et ces points doivent se trouver le plus loin possible les uns des autres (parce que les dictateurs qui vivent dans ces palais se détestent). Alors pour tout vous dire quand j'ai découvert ce problème j'ai commencé par prendre un papier un crayon et à griffonner deux trois schémas, j'ai essayé de chercher par moi-même et il y a un cas de figure en particulier sur lequel j'étais persuadé d'avoir trouvé la réponse, d'avoir trouvé la meilleure disposition des palais et il se trouve que j'étais complètement à côté de la plaque et que la vraie solution m'a vraiment étonné. Et c'est ça qui m'a donné envie de vous en parler ! Alors évidemment la réponse dépend du nombre M de palais à construire. Si M = 2, si on veut construire deux palais, il y a vraiment pas de suspense : la bonne façon de faire c'est de construire les deux palais à deux points antipodaux de la planète, par exemple le pôle nord et le pôle sud. On peut pas les mettre plus loin. Si M = 3 c'est pas très compliqué non plus, mais il va falloir préciser un peu notre énoncé. Parce qu'imaginez que vous mettiez un dictateur tout seul au pôle Nord et les deux autres juste l'un à côté de l'autre au pôle Sud, évidemment dans cette configuration celui qui est au Nord il est très content il est le plus loin possible des deux autres. Seulement bah les deux autres eux ils sont pas satisfaits du tout parce qu'ils sont collés et nous ce qu'on cherche c'est pas une configuration dans laquelle il y en a qu'un seul qui est super content, mais d'une certaine manière une configuration dans laquelle ils sont tous le moins mécontents possible. Alors si on prend les deux qui sont au pôle Sud et qu'on les fait s'éloigner un peu comme ça dans des directions opposées, certes celui qui au Pôle Nord est un peu moins content parce qu'ils se rapprochent, mais ces deux-là sont plus satisfaits. Plus précisément si on note les distances entre les palais vous voyez qu'ici celui du Pôle Nord continue quand même d'être plus content que les deux autres parce que les distances en rouge sont plus grandes que la distance en vert. Et en fait c'est cette distance en vert la plus petite possible qu'on va choisir comme référence : ce qu'on va chercher c'est une configuration dans laquelle la plus petite distance qui existe entre deux palais est la plus grande possible. Ici vous voyez que la distance en vert on peut encore l'augmenter en écartant davantage les deux du Pôle Sud et il arrive un moment où les trois sont en triangle équilatéral et là stop on s'arrête on bouge plus. Dans cette configuration les trois distances sont égales et donc il est plus possible de bouger un palais sans qu'il y ait une des distances qui devienne plus petite. Ce problème s'inscrit dans la catégorie de ce qu'on appelle les problèmes minimax c'est-à-dire les problèmes dans lesquels on veut que le plus petit quelque chose soit le plus grand possible. Ici c'est la plus petite distance qui doit être la plus grande possible. On avait déjà parlé minimax dans l'épisode sur l'hexagone 666. Alors je vais pas détailler tous les cas, mais globalement pour les petites valeurs de M les configurations sont plutôt intuitives. Pour M = 4 il faut mettre les quatre palais au sommet d'un tétraèdre régulier, c'est-à-dire une pyramide à basse triangulaire comme ça. Là le tétraèdre pour le visualiser il se trouve à l'intérieur de la planète et c'est juste ses quatre sommets qui touchent la surface. On peut aussi gonfler le tétraèdre et représenter ses côtés arrondis qui suivent la surface. Pour M = 5 on a la solution en mettant trois palais en triangle équilatéral comme pour M = 3 par exemple autour de l'équateur, et puis les deux autres on en met un au pôle Nord et un au pôle Sud. Remarquez que dans cette configuration tous les dictateurs ne sont pas aussi contents les uns que les autres : la distance en rouge ici est plus grande que celle en vert. Et donc ils sont pas tous disposés exactement pareil par rapport à leur plus proches voisins. Le truc c'est que pour 5, il existe pas de configuration parfaitement symétrique comme c'est le cas pour 4, donc on est obligé d'être un peu injuste envers certains dictateurs, les pauvres... Pour M = 6 on retrouve une configuration bien symétrique : on en place 4 en carré le le long de l'équateur et puis un au pôle Nord et un au pôle Sud. De cette façon les palais sont aux sommets d'un solide qu'on appelle un octaèdre régulier. Vous voyez que cette fois tous les dictateurs sont logés à la même enseigne : on a dit que ces quatre là sur l'équateur formaient un carré, mais en fait ces quatre là forment aussi un carré et c'est un peu comme si c'étaient ces deux-là qui étaient aux pôles. Et puis c'est pareil pour ces quatre-là. Donc en fait selon la façon dont on regarde la planète on peut tous considérer qu'ils sont un peu à l'équateur et un peu au pôles. Cette configuration elle est parfaitement symétrique, les six palais ont vraiment des positions comparables les uns par rapport aux autres. Pour M = 7, comme pour M = 5, la meilleure configuration est déséquilibrée. Il faut mettre une première couche de palais en triangle équilatéral dans l'hémisphère sud, puis une deuxième couche décalée dans l'hémisphère nord et enfin un dernier au pôle Nord. Et on arrive maintenant au cas M = 8 et je vais m'y attarder un peu parce que c'est celui-là qui m'a donné envie de faire cette vidéo. Quand j'ai découvert le problème, je vous ai dit, j'ai pris un papier un crayon pour essayer de me faire un peu une intuition de ce qui pouvait se passer en étudiant les premiers cas pour les petites valeurs de M. Les cas 2 et 3 je les avais ils sont faciles. Le 4 avec le tétraèdre je l'avais aussi. Le 5 j'avais la solution mais j'étais pas totalement sûr de moi. Le 6 je l'avais aussi parce qu'il y a cette configuration régulière en octaèdre. Et le 7 je l'avais pas du tout. Et pour 8 j'étais persuadé d'avoir la meilleure configuration ! Pourquoi ? et bien parce que il existe dans ce cas-là une configuration parfaitement symétrique qui est assez simple il suffit de placer les palais aux huit sommets d'un cube comme ça. Or intuitivement, en tout cas de mon intuition à moi je sais pas ce que vous en pensez dites-moi, mais on a l'impression qu'on cherche une configuration qui est assez symétrique qui est vraiment la plus régulière possible pour que les palais soient le mieux espacés les uns par rapport aux autres. Donc on peut se dire que ok il existe certaines valeurs de M pour lesquelles c'est pas possible d'avoir des configurations parfaitement symétriques, mais quand il existe une configuration symétrique ça peut être que celle-ci la solution... je vois pas ce qui pourrait mal se passer. Et plus précisément, en maths il existe cinq polyèdres parfaitement réguliers qu'on appelle les solides de Platon : le tétraèdre, l'octaèdre, le cube, l'icosaèdre et le dodécaèdre qui ont respectivement 4, 6, 8, 12 et 20 sommets. Et on a déjà vu que pour les premiers solides de Platon ça marche : quand M = 4 et bien effectivement la meilleure façon de placer les palais c'est de les mettre au sommet d'un tétraèdre régulier, et quand M = 6 on les dispose en octaèdre. Et donc évidemment que pour M = 8 la meilleure configuration c'est de les placer au sommet d'un cube. Et bien pas du tout ! ça m'a d'autant plus surpris que vous allez voir la meilleure configuration est finalement assez simple à comprendre, c'est assez simple de voir pourquoi il y a mieux qu'un cube. Et j'adore ce genre de truc en math quand il y a une astuce qui fait que d'un seul coup on se dit "ah mais oui en fait c'est tout simple mais fallait y penser !" Alors pour faire mieux, comment on s'y prend ? On va quand même partir d'un cube et on va faire pivoter sa face supérieure de 45° de cette façon les quatre palais du haut sont décalés par rapport à ceux du bas et du coup la distance entre les palais du haut et du bas a augmenté. Autrement dit les distances en vert ici sont plus grandes que les distances en rouge. Alors ça pour l'instant ça suffit pas parce que les distances en rouge elles ont pas changé donc la distance minimale entre deux palais reste la même que pour le cube. Oui mais maintenant on va très doucement pouvoir faire monter les quatre palais du bas et descendre ceux du haut. En faisant ça, les distances vertes vont diminuer peu à peu et les distances rouges, elles, vont se mettre à augmenter parce que le carré se rapproche de l'équateur. Et donc fatalement, il y a un moment où les deux vont se croiser et avoir la même valeur et c'est là qu'on s'arrête. Voilà la configuration optimale pour M = 8, cette fois on a bien mieux que que le cube parce que toutes les distances initiales ont été augmentées. Cette forme elle s'appelle un anti-prisme à base carrée et cette fois on peut vraiment pas faire mieux. Et même avec cette démonstration le fait que cette forme fasse mieux qu'un cube reste aussi joli que perturbant. Ce cas M = 8 marque d'une certaine manière une frontière entre les gentilles solutions qui sont en dessous et le chaos le plus total. Parce que au-delà ça devient n'importe quoi. Déjà on ne connaît les solutions optimales que jusqu'à M = 14 et à partir de de 15 il n'existe que des conjectures. Sauf pour M = 24 où là on connaît la meilleure configuration aussi, parce que pourquoi pas M = 24. En 1961 Robinson a donné cette forme qu'on appelle un cube adouci et qui donne la solution. Remarquez d'ailleurs que les choses sont pas arrivées dans l'ordre parce que le cas M =14 a été trouvé beaucoup plus récemment en 2014 par Oleg Musin et Alexey Tarasov. Parmi les autres cas particuliers on peut citer M = 12 où là la solution optimale redevient bien régulière : c'est les sommets d'un solide de Platon, l'icosaèdre. En revanche pour M = 20 prendre les sommets du dodécaèdre, le dernier des solides de Platon, c'est pas optimal. On sait qu'il existe des dispositions plus efficaces mais on sait toujours pas démontrer avec certitude quelle est la meilleure. Bref, c'est tout sur ce sujet merci d'avoir suivi cette vidéo si vous voulez en savoir plus comme d'habitude je vous mets des liens et des sources en description. Je vais continuer la lecture de mon livre et on se retrouve bientôt !