Vidéo pop :: Qui se soucie de la topologie ? Colliers volés et Borsuk-Ulam

Transcription de la vidéo

Vous savez ce sentiment que vous ressentez lorsque deux choses qui semblent complètement indépendantes se révèlent avoir une connexion clé. En mathématiques en particulier, il y a une certaine sensation de picotement que je ressens chaque fois que l’un de ces liens commence à se mettre en place. C’est ce que je vous réserve aujourd’hui. Cela prend un peu de temps à mettre en place. Je dois présenter ce casse-tête de la division équitable en mathématiques discrètes ; ça s’appelle le problème du collier volé. Et nous devons également établir un certain fait topologique sur les sphères que nous utiliserons pour le résoudre, appelé théorème de Borsuk–Ulam. Mais croyez-moi, voir la mise en place de ces deux éléments mathématiques apparemment déconnectés vaut vraiment la peine d’être fait.

Et plus amusant, j’ai coordonné cette vidéo avec Mathologer, qui vient de sortir une vidéo qui résout un problème très similaire de division équitable, mais avec une tactique complètement différente. Après cette vidéo, si vous souhaitez en savoir plus, rendez-vous sur sa chaîne. Si, d’une manière ou d’une autre, vous ne connaissez pas encore Mathologer, son contenu figure parmi les meilleurs en mathématiques sur YouTube, il vous suffit de fouiller dans le reste de la chaîne et de vous abonner si vous l’aimez autant que moi.

Alors, voici le puzzle que nous allons résoudre, le problème des colliers volés. Vous et votre ami volez un collier, rempli de nombreux bijoux de grande valeur. Peut-être y a-t-il des saphirs, des émeraudes, des diamants et des rubis. Et disons qu’ils sont tous disposés sur le collier dans un ordre totalement aléatoire. De plus, supposons qu’il existe un nombre pair de chaque type de bijou. Ici, j’ai huit saphirs, 10 émeraudes, quatre diamants et six rubis. Votre ami et vous souhaitez partager le butin de manière égale, chacun de vous obtenant la moitié de chaque type de bijou. Quatre saphirs, cinq émeraudes, deux diamants et trois rubis chacun.

Et, bien sûr, vous pouvez couper tous les bijoux du collier et les répartir de manière égale, mais c’est ennuyeux. Il n’y a pas vraiment de puzzle ici. Le défi consiste plutôt à réduire le plus possible le nombre de coupes dans le collier afin de pouvoir diviser les segments résultants entre vous et votre associé tout en vous permettant de vous retrouver avec la moitié de chaque type de bijou. Par exemple, je viens de le faire en utilisant quatre coupes. Si je vous donne ces trois brins supérieurs et ces deux brins inférieurs à votre associé. Remarquez comment chacun de vous se retrouve avec quatre saphirs. Chacun de vous a cinq émeraudes, deux diamants et trois rubis.

L’affirmation, la chose, que je veux prouver dans cette vidéo est que si vous avez 𝑛 différents types de bijoux, il est toujours possible de trouver une répartition équitable en utilisant seulement 𝑛 coupes ou moins. Ainsi, avec quatre types de joyaux, comme dans cet exemple, vous devriez toujours être en mesure de faire quatre coupes et de diviser les cinq pièces résultantes de sorte que chaque voleur ait le même nombre de bijoux de chaque type. S’il y avait cinq types de joyaux, vous devriez pouvoir le faire en cinq coupes, quel que soit l’arrangement. C’est un peu difficile à penser, non ? Je veux dire que vous devez suivre tous ces différents types de bijoux, en veillant à ce qu’ils soient divisés équitablement. Mais en même temps, vous devez essayer de minimiser le nombre de coupes que vous faites.

En fonction de votre prédisposition aux énigmes en mathématiques, cela peut sembler un peu artificiel. Mais les caractéristiques fondamentales qui rendent ce problème difficile. C’est comme essayer de minimiser la fragmentation et d’essayer de répartir une collection d’éléments de manière équilibrée. Ce sont le genre de problèmes d’optimisation qui se posent assez souvent dans les applications pratiques. Pour les informaticiens, je suis sûr que vous pouvez imaginer comment cela pourrait être lié à une sorte de problème d’allocation de mémoire efficace. Aussi, si vous êtes curieux de le voir en action. J’ai laissé un lien dans la description de la vidéo à un certain document d’ingénierie électrique qui utilise ce problème même.

Indépendamment de son utilité, elle constitue certainement un bon casse-tête. Pouvez-vous toujours trouver une division juste en utilisant seulement autant de tailles qu’il y a de types de bijoux ? Voilà donc le casse-tête. Souviens toi, et maintenant, nous allons prendre un pas de côté apparemment sans rapport avec le côté opposé total de l’univers mathématique, la topologie. Imaginez que vous preniez une sphère dans un espace tridimensionnel et que vous l’écrasiez d’une manière ou d’une autre sur le plan 2D, que vous l’étiriez et la transformiez comme vous le souhaitez. La seule contrainte est que vous le faites continuellement, ce qui signifie que vous ne devez jamais couper la sphère ni la déchirer de quelque façon que ce soit pendant la cartographie. Pendant que vous faites cela, écrasez continuellement cette sphère sur le plan. Beaucoup de paires de points différents sur la sphère vont se poser l’un sur l’autre une fois que celle-ci aura touché le plan. Et ce n’est pas vraiment grave.

Le fait particulier que nous allons utiliser, connu sous le nom de théorème de Borsuk–Ulam, est que vous serez toujours en mesure de trouver une paire de points qui ont débuté de part et d’autre de la sphère et qui se sont superposés au cours de la cartographie. Les points situés exactement à l’opposé d’une sphère sont appelés antipodes ou points antipodaux.

Par exemple, supposons que la sphère soit la Terre et que la cartographie que vous choisissez consiste à projeter chaque point directement sur le plan de l’équateur. Eh bien, dans ce cas, les pôles nord et sud, qui sont antipodaux, atterrissent chacun sur le même point. Et dans cet exemple, c’est le seul couple antipodal qui atterrit sur le même point. Toute autre paire d’antipodes finira par être décalée l’une de l’autre. Mais disons que vous modifiez un peu cette fonction, peut-être en la cisaillant pendant la projection. Eh bien, dans ce cas, les pôles nord et sud ne se touchent probablement plus l’un et l’autre. Mais lorsque les dieux de la topologie ferment une porte, ils ouvrent une fenêtre. Parce que le théorème de Borsuk–Ulam garantit que, quoi qu’il en soit, il doit exister un autre couple antipodal qui atterrit maintenant l’un sur l’autre.

L’exemple classique pour illustrer cette idée, que tout formateur en mathématiques introduisant le théorème de Borsuk–Ulam est tenu par la loi. Est-ce qu’il doit exister une paire de points de l’autre côté de la Terre où la température et la pression barométrique sont exactement les mêmes. Pensez-y un instant. Associer chaque point de la Terre à une paire de nombres, à la température et à la pression revient à cartographier la surface de la Terre dans un plan de coordonnées 2D. Où la première coordonnée représente la température, et la seconde la pression. De plus, chacune de ces valeurs varie continuellement lorsque vous vous promenez autour de la Terre. Donc, cette association est une cartographie continue de la surface d’une sphère sur le plan, une manière non-effrénée d’écraser cette surface en deux dimensions.

Le théorème de Borsuk–Ulam garantit donc que, quelles que soient les conditions météorologiques sur la Terre, ou sur toute autre planète, quelques points antipodaux quelque part doivent atterrir l’un sur l’autre. Ce qui signifie qu’ils correspondent aux mêmes coordonnées de pression de température. Maintenant, j’imagine que si vous regardez cette vidéo, vous êtes probablement un mathématicien dans le cœur et vous voulez voir pourquoi c’est vrai, et pas seulement que c’est vrai. Vsauce a en fait parlé du théorème de Borsuk–Ulam dans une excellente vidéo qu’il a récemment faite à propos de points fixes. Et il a donné une très belle ligne de raisonnement pour l’expliquer intuitivement, ce que je vais simplement adopter sans vergogne pour mon usage personnel ici.

Étant donné la fonction de la sphère dans le plan, imaginez-vous marcher autour de l’équateur. Les sorties correspondantes sur le plan vont former une sorte de boucle fermée. Et disons que votre sœur est à l’opposé du globe. Et pendant que vous vous promenez, elle continue à se tenir parfaitement en face de vous, de façon antipodale. Depuis les deux vous éventuellement changer de place, à un moment donné le long du chemin, la coordonnée 𝑥 de vos sorties correspondantes doivent aligner. La première fois que cela se produit, je veux que vous marquiez où vous vous trouvez sur la sphère, ainsi que où se trouve votre sœur antipodale. Ensuite, si vous inclinez légèrement l’équateur et marchez le long d’un grand cercle légèrement différent, la boucle correspondante dans l’espace de sortie changera un peu.

Mais selon le même raisonnement, il doit y avoir un moment dans votre promenade où vous et votre sœur antipodale atterrissez sur des sorties avec la même coordonnée 𝑥, alignées verticalement. Marquez également ces deux points sur la sphère. Si vous répétez cela, en tournant continuellement cet équateur de 180 degrés autour du cercle complet, vos points marqués constitueront une nouvelle boucle fermée autour de la sphère. Voici à quoi cela pourrait ressembler dans l’espace de sortie, en gardant une trace de tous les points où vous et votre première sœur antipodale vous alignez verticalement. Chaque point de cette nouvelle boucle est un point où vous et votre sœur antipodale, par définition, vous retrouvez avec la même coordonnée 𝑥. Donc, si vous marchez autour de cette nouvelle boucle, vous vous alignez toujours verticalement.

Mais quoi de plus, puisque vous allez éventuellement échanger vos places, il doit y avoir un point en cours de route sur lequel vous avez également la même coordonnée 𝑦, alignant horizontalement. Cela donne un point où vous et votre sœur antipodale devez atterrir sur la même sortie. Assez cool, non ? Pour aider à préparer le terrain pour comment diable cela s’applique au problème du collier, je veux écrire ce que cela signifie un peu plus symboliquement. Les points dans l’espace 3D sont représentés avec trois coordonnées, non ? Je veux dire, d’une certaine manière, c’est ce que l’espace 3D est, du moins pour un mathématicien, tous les triplets possibles de nombres. Maintenant, la sphère la plus simple à décrire avec des coordonnées est la sphère unité standard centrée à l’origine, l’ensemble de tous les points se trouvant à une distance de cette origine. Cela veut dire que tous les triplets de nombres avec la propriété spéciale que la somme de leurs carrés est égal à un.

Donc, l’idée géométrique d’une sphère est liée à l’idée algébrique d’un ensemble de nombres positifs qui s’ajoutent à un, souvenez-vous en. Si vous avez l’un de ces triplets, le point situé de l’autre côté de la sphère, le point antipodal correspondant, correspond à tout ce que vous obtenez en retournant le signe de chaque coordonnée, n’est-ce pas ? Écrivons donc simplement ce que le théorème de Borsuk–Ulam dit symboliquement. Ça va aider pour où nous allons. Pour toute fonction qui prend des points sur la sphère, les triplets de nombres dont les carrés sont égaux à un et crachent un point dans l’espace 2D, des paires de coordonnées comme la température et la pression. Tant que cette fonction est continue, il y aura une entrée pour que l’inversion de tous les signes ne modifie pas la sortie. Et avec cela sur la table, revenons au problème du collier volé.

Une des raisons pour lesquelles ces deux choses ne sont pas liées est que le problème du collier est discret. Mais le théorème de Borsuk–Ulam s’applique à une situation continue. Notre première étape consiste donc à traduire le problème du collier volé en une version continue. Pour l’instant, limitons-nous au cas où il n’y a que deux types de joyaux, le saphir et l’émeraude. Et nous espérons faire une division équitable du collier après seulement deux coupes. Par exemple, disons que nous avons huit saphirs et 10 émeraudes sur le collier. Pour rappel, cela signifie que le but est de couper le collier en deux endroits différents et de diviser ces trois segments afin que chaque voleur ait la moitié des saphirs et la moitié des émeraudes. Remarquez comment le haut et le bas ici ont chacun quatre saphirs et chacun cinq émeraudes.

Pensez à ce collier comme une ligne avec la longueur un, avec les bijoux assis uniformément espacés dessus. Divisez maintenant cette ligne en 18 segments de taille égale, un pour chaque type de bijou. Et plutôt que de considérer chaque bijou comme une entité indivisible discrète sur le segment, supprimez le bijou lui-même. Et, au lieu de cela, il suffit de peindre ce segment de la couleur du bijou. Donc, dans ce cas, si vous peignez le collier en entier de manière appropriée, huit dix-huitièmes de la ligne vont être peints en saphir, tandis que dix dix-huitièmes de la ligne seront peints en émeraude. La version continue de ce casse-tête consiste à demander maintenant si nous pouvons trouver deux coupes n’importe où sur cette ligne, pas nécessairement sur ces marques d’un dix-huitième de segment, qui permettent de diviser les pièces de sorte que chaque voleur ait une longueur égale de chaque couleur.

Dans ce cas, cela signifie que chaque voleur doit avoir une longueur totale de quatre dix-huitièmes de segments de couleur saphir et de cinq dix-huitièmes de segments de couleur émeraude. Un point important mais quelque peu subtil est que si vous pouvez résoudre cette variante continue du puzzle, vous pouvez également résoudre la version discrète originale. Pour voir pourquoi, supposons que vous trouviez une division équitable mais dont les coupes ne tombent pas nécessairement entre les bijoux. Peut-être que cela coupe une partie de la ligne à travers un segment d’émeraude. Comme il s’agit d’une division équitable, la longueur de l’émeraude dans les groupes supérieur et inférieur doit donner au total exactement cinq segments d’émeraude, un multiple entier de la longueur du segment. Ainsi, même si la division coupe partiellement un segment d’émeraude à gauche, elle devra également couper partiellement un segment d’émeraude à droite ici. Ainsi, la longueur totale peut s’ajouter à un multiple entier de la longueur du segment.

Cela signifie que nous pouvons ajuster chaque coupe sans affecter la division afin qu’elles se retrouvent finalement alignées sur ces marques d’un dix-huitièmes. Maintenant, dans ce cas continu, où vous pouvez couper la ligne où bon vous semble, pensez à tous les choix qui entrent dans la coupe du collier et dans l’affectation de ses pièces. Tout d’abord, vous choisissez deux endroits différents pour couper l’intervalle. Mais une autre façon de penser à cela est de choisir trois nombres positifs dont la somme vaut un. Par exemple, vous pouvez choisir un sixième, un tiers et un demi. Cela correspondrait aux deux coupes ici. Chaque fois que vous trouvez trois nombres positifs dont la somme vaut un, cela vous donne un moyen de couper le collier, et vice versa. Ensuite, après l’avoir coupé, vous devez faire un choix binaire pour chacune de ces trois pièces, que ce soit pour le voleur un ou pour le voleur deux.

Maintenant, comparez cela à si je vous demandais de choisir un point quelconque sur la sphère 3D. Un certain point de coordonnées 𝑥, 𝑦, 𝑧 de sorte que 𝑥 carré plus 𝑦 carré plus 𝑧 carré est égal à un. Eh bien, vous pouvez commencer par choisir trois nombres positifs qui totalisent un. Peut-être, vous voulez que 𝑥 au carré soit égal à un sixième, 𝑦 au carré un tiers et 𝑧 au carré un demi. Ensuite, vous devez faire un choix binaire pour chacun, en choisissant entre la racine carrée positive ou son opposée. Donc, d’une manière complètement parallèle au choix d’une division de collier, choisir un point sur la sphère implique tout d’abord de trouver trois nombres positifs qui totalisent un, puis de faire un choix binaire pour savoir quoi faire avec chacun d’entre eux. Ce droit, il y a une observation clé pour toute la vidéo. Il donne une correspondance entre les points sur les divisions de la sphère et du collier.

Pour tout point 𝑥, 𝑦, 𝑧 qui se trouve sur la sphère, car 𝑥 au carré plus 𝑦 carré plus 𝑧 carré est égal à un, vous pouvez couper le collier de sorte que la première pièce a une longueur de 𝑥 au carré. Le second a une longueur de 𝑦 carré, et la troisième a une longueur de 𝑧 carré. Ensuite, pour choisir comment attribuer ces éléments, si 𝑥 est positif, donnez-le au voleur. Sinon, donnez-le au voleur deux. Si 𝑦 est positif, donnez ce deuxième morceau au voleur un. Sinon, donnez-le au voleur deux. Et puis, de même, pour attribuer le troisième morceau, si 𝑧 est positif, donnez-le au voleur un. Sinon, donnez-le au voleur deux. Et vous pouvez faire l’inverse. c’est une correspondance un à un. N’importe quel moyen de diviser le collier et de diviser les pièces vous donnerait un point unique sur la sphère.

C’est comme si la sphère était le moyen idéal d’encapsuler l’idée de toutes les divisions de collier possibles à l’aide d’un objet géométrique. Et avec cette association, nous sommes extrêmement proches. Prenez un moment pour réfléchir à la signification des points antipodes dans cette association. Si le point 𝑥, 𝑦, 𝑧 sur la sphère correspond à une allocation de collier, à quoi correspond le point moins 𝑥, moins 𝑦, moins 𝑧 ? Eh bien, les carrés de toutes ces coordonnées sont les mêmes. Donc, cela correspondrait à faire les mêmes coupes sur le collier. La différence est que chaque pièce change le voleur auquel elle appartient. Donc, sauter à un point antipode de l’autre côté de la sphère correspond à l’échange de toutes les pièces entre les deux voleurs.

Maintenant, rappelez-vous ce que nous recherchons réellement. Nous voulons que la longueur totale de chaque type de bijou appartenant au voleur un soit égale à celle du voleur deux. En d’autres termes, dans une division équitable, cette permutation antipodale ne change pas la quantité de chaque bijou appartenant à chaque voleur. Votre cerveau devrait être brûlé par la pensée de Borsuk–Ulam à ce stade. Plus précisément, vous pouvez créer une fonction donnée, une fonction qui prend une allocation de collier donnée et crache deux nombres. La longueur totale du saphir appartenant au premier voleur et la longueur totale de l’émeraude appartenant au premier voleur.

Ce que nous voulons montrer, c’est qu’il doit exister un moyen de diviser le collier en deux coupes et de diviser les pièces pour que ces deux nombres soient identiques à ce qu’ils auraient été pour le voleur deux. Ou, dit un peu différemment, où échanger toutes les pièces ne changera pas ces deux nombre pour le voleur un. En raison de ce va-et-vient entre les allocations de collier et des points sur la sphère et que des paires de nombres correspondent à des points sur le plan 𝑥𝑦, ceci est en effet une mise en correspondance de la sphère sur le plan. Le théorème de Borsuk–Ulam garantit donc que certains points antipodaux de la sphère se posent l’un sur l’autre sur le plan. Et ce que cela signifie, c’est la division et l’attribution des colliers de manière à ce que l’échange des pièces entre les deux voleurs ne change pas la quantité de chaque bijou que chacun possède.

C’est une division juste. Voilà, mes amis, c’est ce que de belles mathématiques sont. Et si vous êtes un peu comme moi, vous ne pouvez que profiter de la preuve intelligente de ce qu’est une preuve intelligente. Et il peut être facile d’oublier que nous voulons en fait résoudre le problème plus général des colliers volés, qui ne se limite pas à deux types de bijoux. Pour cela, nous pouvons utiliser une version plus générale du théorème de Borsuk–Ulam, qui s’applique aux sphères de plus grande dimension. Par exemple, Borsuk–Ulam s’applique également à la cartographie d’hyper-sphères de l’espace 4D dans l’espace 3D. Ce que je veux dire par hyper-sphère, la façon de penser, sont toutes les listes possibles de quatre coordonnées où la somme de leurs carrés est égale à un. Ce sont tous les points de l’espace 4D situés à une certaine distance de l’origine.

Le théorème de Borsuk–Ulam dit que si vous essayez de mapper cet ensemble, tous ces quadruplés spéciaux, dans un espace tridimensionnel, en associant continuellement chacun d’eux à un triplet de nombres. Il doit y avoir une collision antipode, une entrée 𝑥 un, 𝑥 deux, 𝑥 trois, 𝑥 quatre, où renversant tous les signes ne changerait pas la sortie. Je vais vous laisser le temps de réfléchir et de réfléchir à la manière dont cela s’appliquerait au cas de trois joyaux. Et à propos de ce que la déclaration générale du théorème de Borsuk–Ulam pourrait être et comment elle peut s’appliquer au problème général du collier. Inutile de dire qu’il est assez difficile d’essayer de visualiser une sphère 4D dans l’espace 3D. Néanmoins, pour l’animation finale, je vais essayer de vous montrer à quoi cela pourrait ressembler.

Bon, voici donc l’animation finale. C’est un peu déroutant. Donc, pour l’analogie en haut à gauche ici, je tourne une sphère en trois dimensions et la projette en 2D. Mais je ne fais que montrer les lignes de latitude sur cette sphère sans la colorer ou quoi que ce soit du genre. Ainsi, de la même manière au centre, je fais pivoter une hyper-sphère à quatre dimensions dans l’espace 4D, mais je la projette dans un espace 3D. Mais tout ce que je montre, ce sont les sphères de latitude, pour ainsi dire. N’oubliez pas qu’il n’est pas nécessaire de pouvoir visualiser une cartographie en trois dimensions d’une sphère 4D pour pouvoir comprendre le théorème de Borsuk–Ulam. Mieux, cela ne s’applique pas au problème du collier volé. C’est juste pour s’amuser. Mais c’est joli d’essayer, vous ne pensez pas ?