20 mai 2012
[#] Alan Turing : 1912-2012
Le 17 mai dernier a eu lieu la 8ème journée mondiale contre l'homophobie, l'occasion d'évoquer le destin tragique de Alan Turing, dont on fête le centenaire en cette année 2012.
Le Memorial Alan Turing au Sackville Park (Manchester).
Fait intéressant : Turing est représenté avec une pomme.
Si on devait résumer la vie de Turing, on pourrait le faire ainsi :
- 23 juin 1912 : il naît du côté de Londres.
- 1936-1937 : il révolutionne l'informatique théorique en inventant la notion d'algorithme (renvoyant dans les cordes Church et son lambda-calcul) et les machines de Turing, ce qui lui permet de résoudre le problème de la décision (peut-on toujours résoudre un problème par un algorithme ?) et le problème de l'arrêt (peut-on savoir à l'avance si un algorithme va boucler ?).
- 1942-1943 : il révolutionne la cryptanalyse (le cassage de codes secrets), en décryptant les messages allemands codés par Enigma. Impliqué dans les services de renseignement militaires britannique, c'est un peu grâce à lui que le monde a été sauvé des nazis.
- 1950 : il révolutionne l'histoire de l'intelligence artificielle, en inventant le test de Turing : on pourra dire que l'intelligence artificielle existe le jour où on ne pourra plus la différencier de l'intelligence humaine. C'est pour cela que, aujourd'hui, on croise tous les jours le nom de Turing : c'est le T de l'acronyme CAPTCHA (vous savez, les mots illisibles qu'il faut identifier dès que l'on veut s'inscrire sur un site de rencontre éducatif).
- 1952 : il révolutionne l'histoire de la morphogénèse (en l'inventant), en proposant une bonne raison au fait que les zèbres sont zébrés, alors que les léopards, ben non.
- 1952 : du seul fait de son homosexualité, il jugé coupable d'"indécence manifeste et de perversion sexuelle" (comme l'a été Oscar Wilde 50 ans plus tôt), qui lui donne le choix entre plusieurs années de prison et la castration chimique. Il choisit la deuxième option. Mauvaise idée.
- 1954 : on le retrouve mort deux semaines avant ses 42 ans, empoisonné au cyanure. Les circonstances de sa mort ne sont pas parfaitement comprises, la thèse la plus probable étant celle du suicide à la pomme empoisonnée, façon Blanche-Neige. (Notons au passage que la pomme d'Apple fait référence à celle de Newton, et non à celle de Turing)
- 1966 : son nom est donné au prix Turing, l'équivalent du Nobel en informatique.
- 2009 : Gordon Brown, premier ministre britannique, reconnaît que, finalement, c'était peut-être pas une bonne idée que de castrer chimiquement l'un des plus grand mathématicien britannique, d'autant plus que son aide a été la bienvenue pendant la guerre.
Machines de Turing et problème de l'arrêt
En 1928, Hilbert propose ce qu'il appelle dans sa langue le Entscheidungsproblem (problème de la décision) : peut-on toujours prouver mécaniquement (par un algorithme) qu'un énoncé est (ou non) un théorème. Ce problème est lié au problème de l'arrêt : si j'écris un algorithme dans un langage de mon choix, peut-on vérifier sans le lancer que l'algorithme ne va pas boucler indéfiniment (et donc, qu'il va finir par s'arrêter) ?
Pour répondre à ces questions, il faut tout de même savoir exactement ce qui peut mériter d'être appelé "algorithme", et définir la calculabilité. Ce travail est surtout l’œuvre de Alonzo Church, l'inventeur λ-calcul. Ce système formel, qui fonde historiquement la notion de fonctions, a permis à Church de résoudre le problème de la décision. Le λ-calcul a tout de même un gros défaut : il est (beaucoup) moins intuitif que les machines de Turing, qui seront inventés quelques années plus tard par le mathématicien qui nous intéresse cette année. Même Church le reconnaîtra.
Concrètement, une machine de Turing, c'est une machine (théorique) composée :
- d'un ruban de papier (si possible, infini) divisé en cases. Dans chacune de l'une d'elle, un 0 ou un 1.
- d'une tête de lecture/écriture, capable de lire le ruban et, le cas échéant, de remplacer un 0 par un 1, ou inversement.
- d'un registre d'état (un compteur - fini -, qui liste les états dans lequel peut être la machine)
- d'une table d'action, qui dit à la tête de lecture quand il faut faire quoi (du genre "si tu es en état x et que tu lis un 0, alors tu le transforme en 1, tu te mets en état y et tu passe à la case d'à côté"). C'est le programme en lui même.
Le ruban correspond à l'input du programme, tandis que la table d'action correspond au programme lui-même.
Une machine de Turing peut donc ressembler à ceci :
Démarrer en l'état 0 avec une bande pleine de 0.
Étape 1 (état 0) : la tête est en position 0, elle lit "0". Elle va donc écrire "1", se déplacer à droite, et se mettre dans l'état 1
Étape 2 (état 1) : la tête est en position 1, elle lit "0". Elle écrit alors "1", se déplace à gauche, et revient en état 0.
Et ainsi de suite...
Bon, ce programme n'est pas spécialement intéressant, surtout qu'il ne s'arrête jamais. On pourrait cependant simuler avec une machine de Turing n'importe quel algorithme (comme le crible d'Erathostène, l'algorithme d'Euclide...), aussi compliqué soit-il. C'est finalement cette définition que l'on retiendra d'un algorithme : si on peut le simuler par une machine de Turing, c'est que c'est un algorithme.
Du coup, on peut théoriser beaucoup de chose sur les algorithmes, notamment celui du problème de l'arrêt, en utilisant un argument diagonal à la Cantor.
Pour cela, numérotons de 1 à ∞ l'ensemble (dénombrable) des machines de Turing, et appelons h(i,x) la fonction qui renvoie 1 si la machine n°i avec l'entrée x s'arrête, et 0 sinon. Cette fonction, si elle est mécanisable, résoudrait le problème de l'arrêt pour n'importe quel algorithme.
Notons de plus g(i) la fonction qui renvoie 0 si h(i,i)=0, mais qui n'est pas défini sinon. Supposons que cette dernière fonction est calculable et qu'elle correspond à la machine n°e. Mais alors, quelle est la valeur de g(e) ? Deux possibilités : soit 0, soit rien du tout.
Si g(e)=0, c'est que h(e,e)=0. Mais dans ce cas, g a une image, et donc, le programme n°e s'arrête bien : h(e,e)=1. Absurde !
Si g(e) n'est pas défini, c'est que h(e,e)=1. Dans ce cas, h(e,e)=0, car le programme n°e ne s'arrête pas. Absurde !
La fonction h n'est donc pas calculable !
Bref : le seul moyen de savoir si un algorithme boucle ou non, c'est de le lancer et d'attendre. Merci Turing d'avoir trouvé ça.
Être ou ne pas être Turing-complet ?
Par essence, tout ce qui est calculable l'est par une machine de Turing. Du coup, on dira d'un système qu'il est Turing-complet s'il permet (au moins en théorie) de calculer autant de choses qu'une machine de Turing. On retrouve de la Turing-complétude dans la plupart des langages de programmation (du C++ au brainf*ck), mais on le retrouve ailleurs... Top 5 dans endroits étrange où l'on retrouve de la Turing-complétude :
N°5 : Minecraft
N°4 : Little Big Planet
N°3 : L'eaurdinateur, un assemblage de siphons et de réservoirs.
N°2 : Le jeu de la vie
N°1 : Une véritable machine de Turing en Légo !
(à suivre...)
Sources :
The Alan Turing Year - page officielle dédiée à l'année Alan Turing.
Images : Alan Turing Memorial
06 mai 2012
[#] Le problème avec l'intégration
En ce dimanche, le peuple français est appelé à faire son devoir de citoyen : se connecter sur ce blog pour voir s'il y a enfin de la nouveauté. Pour une fois, la réponse est oui ! Youpi !
Ce week-end, je parlerai d'un sujet grave, l'intégration, et d'un théorème injustement ignoré : le théorème de Liouville-Rosenlicht, qui ose dire que toutes les fonctions ne se valent pas. Certaines s'intègrent très bien, alors que d'autres refusent la main qu'on leur tend. Et je ne parle ici que des fonctions élémentaires.
On peut appeler fonction élémentaire toutes les fonctions que l'on peut construire avec des exponentielles, des logarithmes ou des opérations algébriques usuelles (+, -, ×, ÷, ^, √). Les fonctions trigo (cos, sin, arctan, acoth) y rentrent également, puisqu'on peut les écrire à partir d'exponentielles ou de logarithmes. Ainsi, les fonctions 3x² ou (e3x-1/√x+log(4x2))x sont des fonctions élémentaires.
Avec de l'entrainement et un bon logiciel de calcul formel, vous devez être capable de calculer la fonction dérivée de n'importe quelle fonction élémentaire. Les formules sont simples, s'appliquent sans difficultés. Mais pourquoi est-ce si difficile de faire l'opération inverse, et de calculer des primitives ?
Au lycée, on découvre que certaines fonctions s'intègrent facilement, comme les fonctions polynômes (x20/2) ou les fonctions trigonométriques (cos(x)+sin(x)).
Puis, en licence, on découvre que certaines fonctions s'intègrent n'importe comment :
Et puis, on finit par ne plus chercher à s'embêter, et on invente de nouvelles fonctions quand ça nous arrange.
On ne sait pas intégrer sin(x)/x (le sinus cardinal) ? Eh bien, on invente la fonction Si(x) (sinus intégral), dont la dérivée est précisément sin(x)/x.
On ne sait pas intégrer e-x² ? Eh bien, on invente la fonction erf (Fonction d'erreur de Gauss), dont la dérivée est ex² (à peu de choses près).
On ne sait pas intégrer cos(x²) et sin(x²) ? Eh bien, on invente les fonctions C(x) et S(x) (Les fonctions de Fresnel), dont les dérivées sont plus ou moins ce qu'on attend d'elles.
Du coup, les primitives des fonctions deviennent plus faciles à apprendre, mais perdent en subtilité :
Mais est-ce une fatalité ou de la pure flemme mathématique ? Peut-être a-t-on mal cherché, et qu'il existe quelque part une fonction tordue dont la dérivée donne ex/x ?...
La réponse est non, c'est une fatalité. Et cette fatalité a un nom : le théorème de Liouville-Rosenlicht !
Ce théorème, démontré en 1834 par Liouville, (que je préfère ne pas énoncer) indique à quoi peut ressembler la primitive (si elle existe et qu'elle est élémentaire) d'une fonction élémentaire. La conséquence, c'est que seule une petite catégorie de fonctions ont une primitive de complexité équivalente (et encore, il faut admettre que les logarithmes sont aussi complexes que les polynômes). Cela dit, le théorème ne donne que peut d'indication sur la primitive de la fonction de l'on cherche à intégrer.
La théorie revient au goût du jour dans les années 1940 avec les travaux de Ostrowski et Ritt. En 1968, Rosenlicht fournit la démonstration la plus classe du théorème, entièrement algébrique.
On se retrouve donc avec deux types de fonctions élémentaires : une minorité qui admettent des primitives élémentaires (les polynômes, les fonctions rationnelles...), et une majorité qui admettent aussi une primitive, mais non élémentaire (il faut alors inventer de nouvelles fonctions pour pallier les manques). Cela dit, le théorème
Il ne faut pas sa voiler la face : certaines fonctions n'ont pas de primitives, il va falloir vivre avec ça.
Sources :
Quelles sont les primitives de e-x² ? De sin(x)/x ? De xx ? par Matthew Wiener
15 avril 2012
[#] Une chance sur beaucoup
Y a-t-il plus de chance de gagner au loto ou de battre Federer au tennis ? Y a-t-il plus de chances de tomber deux fois de suite sur une même blague carambar ou de mourir un vendredi 13 ? Je ne vois qu'une façon de répondre à ces questions : consulter ce schéma.
Remarques :
Une chance sur 4 : pour une galette 8 personnes de 30cm de diamètre.
Une chance sur 30 : c'est une proba conditionnelle !
Une chance sur 7 200 000 : Statistiques avion / moto (2001-2002)
Une chance sur 4 000 000 000 000 : avec une machine à écrire à 50 touches, la première réplique "Who's there?!" comportant 13 caractères.
25 mars 2012
[#] Szemerédi, go !
Après un mois d'hibernation, je me dois de réouvrir le blog pour annoncer quelque chose de très important : il s'est passé quelque chose sur la planète maths ! Le 22 mars dernier, un prix mathématique a été remis, et pas n'importe lequel : le prix Abel. Et pour la deuxième fois, c'est un hongrois qui décroche la récompense suprême : le célèbre Endre Szemerédi !
Endre Szemerédi, regard langoureux, sourire enjoleur.
Faisons bref : le prix Abel, c'est le prix Nobel des mathématiques (à ne pas confondre avec la médaille Fields, qui est aussi le prix Nobel des mathématiques). Remis par l'académie norvégienne des sciences et des lettres, elle récompense ce qui se fait de mieux en matière de mathématiciens vivants. Cette année, c'est donc Endre Szemerédi qui a été récompensé, «pour ses contributions fondamentales aux mathématiques discrètes et à la science de l'informatique théorique, et en reconnaissance du retentissement profond et durable de ces contributions sur la théorie additive des nombres et la théorie ergodique». S'il fallait résumer de manière très grossière, on pourrait dire que sans lui, Internet n'existerait pas (mais on va éviter de faire ce genre de raccourcis).
Le domaine de prédilection de Szemerédi, c'est donc les mathématiques discrètes. Par exemple, pour modéliser les mouvements d'un fluide, on va s'intéresser aux pressions ou aux vitesse de tout points en fonction du temps pour en déduire des équations dans le meilleur des cas différentielles : ça, c'est le travail des mathématiques continues. Le travail de Szemerédi est donc l'exact opposé.
Le théorème de Szemerédi
Avant de parler du théorème, rappellons qu'une progression arithmétique, c'est une suite où chaque pas (la "raison") est de la même longueur. Par exemple, 4; 7; 10; 13; 16; 19; 22 est une suite arithmétique de longueur 7 et de raison 3.
L'œuvre la plus célèbre de Szemerédi restera donc avant tout sa démonstration en 1975 de la conjecture d'Erdős–Turán, énoncée 40 ans plus tôt : toute suite d'entiers de densité non nulle contient une progression arithmétique arbitrairement longue ! Quand on sait à quel point ses prédécesseurs ont galéré sur le cas des progressions arithmétiques de longueur 3 (Roth, 1956) et de longueur 4 (Szemerédi, 1969), il mérite le respect. Trente ans plus tard, ce théorème deviendra le théorème de Green-Tao ("La suite des nombres premiers contient des suites arithmétiques arbitrairement longues.")
Le théorème de Szemerédi, comme celui de Green-tao, reste un cas particulier d'une conjecture à 3000$ (la conjecture d'Erdõs) : si la série des inverses d'une suite entière positive diverge, alors alle admet une progression arithmétique arbitrairement longue.
Mais au fait, que dit exactement ce théorème ?
Pour le comprendre, prenons une proportion p (par exemple, 40%) et un nombre k (par exemple, 3). Le théorème énonce donc que si l'on prend au moins 40% des nombres entre 1 et N (N étant un nombre assez grand qui dépend de p et de k), on pourra y trouver une progression arithmétique de 3 termes (une suite où la différence entre deux termes consécutifs est constante).
Le nombre N, dans ce cas-là, est 42. Si vous prenez 17 nombres entre 1 et 42, vous serez certain d'y trouver une suite arithmétique de 3 termes ! La preuve en image :
1, 2, 4, 6, 9, 14, 15, 17, 18, 20, 21, 25, 31, 32, 36, 40, 42
(en cherchant un peu, vous ne tarderez pas à en trouver d'autres)
Ce théorème fonctionne pour n'importe quelle proportion p (aussi petite soit-elle), et pour n'importe quelle longueur k (aussi grande soit-elle). Ainsi, en ne gardant que 1% de la totalité des nombres entiers, on peut quand même y trouver des suites arithmétiques de longueur 200.
Le même théorème (démontré également par Szemerédi) existe en deux dimensions : pour une proportion p donnée, on peut trouver une grille assez grande contenant p points dans lequel il existe un "coin" (trois points de coordonnées (x,y), (x+h,y) et (x,y+h)).
Au cours de sa démonstration, Szemerédi démontrera un lemme sur le moment anecdotique, mais qui deviendra finalement encore plus célèbre que le théorème en lui-même : le lemme de régularité. Ce lemme/théorème deviendra central en théorie des graphes, ce qui n'est pas rien.
Le théorème de Ramsey
Si vous réunissez un nombre suffisemment grand de personnes dans un même endroit, alors
- soit il y aura un groupe de s personnes où chacun connaît tous les autres
- soit il y aura un groupe de t personnes où personne ne se connaît.
C'est ce qu'énonce le théorème de Ramsey (bien qu'il ait plutôt parlé de sous-graphes complets monochromatiques d'un graphe complet coloré)
Le nombre de personnes à réunir dépend évidemment de s et de t. Par exemple, dans le cas s=t=3, il faut réunir au moins 6 personnes :
A gauche, une réunion de 5 personnes, à droite, une réunion de 6 personnes
Deux personnes sont reliées en vert si elles se connaissent, en rouge sinon.
A gauche, il n'y a pas de triangle vert (pas de groupes de 3 où tout le monde se connaît), ni de triangle rouge (un groupe de 3 où personne ne connaît personne).
A droite, on trouvera toujours un triangle vert ou un triangle rouge. Ici, trois personnes se connaissent.
Le nombre minimal de personnes a réunir pour qu'il existe un groupe de 4 personnes dans lequel chacun se connaît ou bien personne ne se connaît (cas s=t=4) est 18. Pour s=t=5, ce nombre minimal est quelque part entre 43 et 49, et il semble très difficile d'en avoir une estimation plus précise.
Szemerédi, avec l'aide de Ajtai and Komlós, s'est attelé à chercher une bonne estimation de ce nombre dans le cas s=3 et t quelconque. Leurs conclusions ont plutôt satisfait la communauté.
Le problème des ragots
Bon, on ne va pas s'amuser à lister tous les travaux de Szemerédi, puisqu'il a écrit plus de 200 papiers, qui ont donné des choses très précieuses, comme le théorème de Szemerédi–Trotter, le théorème de Erdős–Szemerédi, le lemme de Balog–Szemerédi–Gowers ou le réseau de tri de Ajtai–Komlós–Szemerédi. Mais j'aimerais parler d'un important papier co-écrit par Szemerédi intitulé "A cure for telephone disease".
Notre prix Abel s'est donc intéressé au problème suivant :
Considérons n femmes, chacune au courant d'un scoop d'envergure mondiale. Lorsque deux femmes se téléphonent, elles se partagent l'ensemble des ragots dont elles ont la connaissance. Combien faudra-t-il au minimum de coups de fil pour que chacune soit au courant de tous les potins ?
Ainsi, si n=1, il faudra 0 coup de téléphone ;
si n=2, il faudra 1 coup de téléphone ;
si n=3, il faudra 3 coups de téléphone ;
si n=4, il faudra 4 coups de téléphone ;
si n=5, il faudra 6 coups de téléphone ;
La stratégie la plus efficace pour que 9 femmes se partagent 9 ragots (chaque arête du graphe correspond à un coup de téléphone, le nombre correspond à l'ordre dans lequel il faut les effectuer).
Ils n'ont pas tardé à déterminer la solution tant attendue : au delà de 4 femmes, il faudra 2n-4 coups de téléphone (au minimum) !
Sources :
Site officiel du prix Abel, avec un max d'informations sur Szemerédi
A cure for telephone disease - Hajnal, Milner et Szemerédi
26 février 2012
[#] Lemme de Burnside : exemples et applications
Le lemme de Burnside... Outre le fait qu'il n'est pas dû à Burnside et qu'on peut le considérer autrement qu'un lemme, ce résultat obscur de la théorie des groupes permet de faire des choses hallucinantes ! Si si ! Il permet par exemple de compter le nombre de colliers que l'on peut faire avec 3 perles rouges, 3 perles bleues et 5 perles vertes. Il permet aussi de compter le nombre de colliers que l'on peut faire avec 6 perles jaunes, 3 perles bleues, une perle verte et une perle rouge.
Il permet en fait de répondre à n'importe quel problème de dénombrement avec des perles ! (et certains problèmes sans perle : combien y a-t-il de façons de partager un paquet de Vache qui rit (aux isométries près) entre 3 personnes, combien existe-t-il de sudokus réellement différents, etc.). Le lemme de Burnside est l'exemple typique de l'énoncé abstrait d'un domaine abstrait qui trouve des applications concrètes dans des domaines concrets (pour peu que l'on aime fabriquer des colliers).
Exemple I-2
Pour réaliser de tels dénombrements, il faut seulement s'intéresser de près à la théorie des groupes agissant sur un ensemble. Au diable la théorie, passons directement à la pratique : pour cela, il nous faut un groupe et un ensemble. Pour ce premier exemple, prenons l'ensemble des colliers rouges et bleus à 5 perles :
Sept colliers bicolores à 5 perles, parmi les 32 existants
Cet ensemble contient 25 (=32) éléments (chaque perle pouvant être de deux couleurs).
Quand on regarde les exemples, on voit certains colliers sont les mêmes, à une rotation près (par exemple, le 3ème se déduisent du deuxième par une rotation d'un cinquième de tour). Puisqu'il nous faut également un groupe, c'est naturellement que l'on prend celui des rotations du pentagone.
Il existe 5 rotations (r1, r2, r3, r4 et r5) qui transforment ce pentagone en lui-même : elles forment le groupe des rotations du pentagone. Appelons ce groupe Z/5Z.
L'ensemble des 5 rotations du pentagone forment un groupe (la succession de deux rotations est toujours une rotation, et il existe une rotation neutre).
Le groupe agit sur l'ensemble : sous l'action de la rotation r2 (2 cinquièmes de tour), le collier est transformé en un collier différent. Certains colliers ne sont pas transformé sous l'effet d'une rotation (les colliers d'une seule couleur)
La question est donc de trouver le nombre de colliers différents en tenant compte que certains sont identiques (moyennant l'action du groupe Z/5Z sur l'ensemble des colliers). Pour chaque élément du groupe, certains colliers restent inchangés : par exemple, sous l'effet de la rotation r1 (un cinquième de tour), le collier tout rouge est inchangé. Le lemme de Burnside dit alors la chose suivante : le nombre que l'on cherche est la moyenne des nombres de colliers inchangés.
Procédons donc au calcul :
- la rotation r1 : elle ne fixe que deux colliers : le tout rouge et le tout bleu. (2 colliers)
- la rotation r2 : idem (2 colliers)
- la rotation r3 : idem (2 colliers)
- la rotation r4 : idem (2 colliers)
- la rotation r5 (qui est en fait une rotation neutre) : aucun collier n'est transformé par cette rotation. Elle fixe donc les 32 colliers.
La moyenne est donc : (2+2+2+2+32)/5 = 8
Il y a donc 8 colliers différents !
Exemple I-3
Deuxième exemple, un peu plus parlant : combien y a t-il de façons de partager équitablement une boîte de Vache qui rit entre 3 personnes, sachant que deux partages sont équivalents s'ils se déduisent l'un de l'autre par une rotation ou une symétrie.
On a donc besoin d'un ensemble : ça sera celui des partages de Vache qui rit entre 3 personnes (Cyan, Magenta et Jaune). Cyan prend deux parts parmi les six (2 parmi 6 = 15 possibilités), Magenta prend deux parts parmi les 4 restantes (2 parmi 4 = 6 possibilités), Jaune prend les deux dernières (1 possibilité). Au total, il y a donc 15 × 6 × 1 = 90 partages différents.
Quatre partages de Vache qui rit, parmi les 90 existants. Les deux premiers sont équivalents (par une rotation), les deux derniers également (par une symétrie axiale).
Il nous faut également un groupe. On va prendre le groupe D6, le groupe des isométries de l'hexagone. Il contient 12 éléments : l'identité (Id), 5 rotations (r1, r2, r3, r4 et r5, respectivement de 1, 2, 3, 4 et 5 sixièmes de tour) et 6 symétries axiales (s1, s2, s3, s4, s5 et s6).
Les 12 isométries du groupe D6.
De la même façon que précédemment, les isométries agissent sur les partages, et en laissent certains fixes. Voyons dans le détail :
- Id laisse fixe l'ensemble des partages (90 partages)
- r1 et r5 (rotations) n'en fixent aucun (2×0 partages)
- r2 et r4 (rotations) n'en fixent aucun (2×0 partages)
- r3 (symétrie centrale) laisse fixe les partages où les parts sont opposés (6 partages)
- s1, s3 et s5 (symétries axiales) laisse fixe les partages où les parts sont symétriques, l'axe ne coupe pas de parts (3×6 partages)
- s2, s4 et s6 (symétries axiales) laisse fixe les partages où les parts sont symétriques, l'axe coupant une paire de parts (3×6 partages)
Au final, il y a donc (90+2×0+2×0+6+3×6+3×6)/12 = 11 partages possibles !
Application I-4
On pourrait multiplier les exemples utilisant les groupes d'isométries des polygones ou polyèdres réguliers ("combien y a-t-il de façons de peindre les faces d'un cube de façon à ce que 3 faces soient rouges, 2 jaunes et 1 bleue ?"), mais on peut également répondre à l'aide de Burnside à cette question primordiale : "combien existe-t-il de sudokus réellement différents" ?
Un dénombrement minutieux (*) permet de montrer qu'il en existe 6670903752021072936960., mais on sait qu'il en existe en réalité beaucoup moins que ça : peut-on réellement considérer deux grilles de sudokus différentes si l'une est le reflet de l'autre dans un miroir ?
Deux grilles de sudokus sont donc équivalentes si on peut passer de l'une à l'autre en faisant une (ou plusieurs) des opérations suivantes :
- permutation des nombres
- permutation de deux colonnes au sein d'un même pile (bloc de 3 colonnes)
- permutation de deux blocs de colonnes
- permutation de deux lignes au sein d'un même bande (groupe de 3 lignes)
- permutation de deux blocs de lignes
- transposition (inversion des lignes et des colonnes)
- rotation
- symétrie axiale
En mettant de côté la permutation des nombres, les opérations légales ne sont que des permutations des 81 cases du sudoku.
Combien existe-t-il de grilles de sudokus équivalentes ? Le lemme de Burnside approche !
Il nous faut donc un ensemble. On ne va pas prendre les 6670903752021072936960 grilles différentes : c'est beaucoup trop. Quitte à permuter les nombres, on peut toujours se ramener à une grille dont la première région est "1-2-3/4-5-6/7-8-9". On dira que deux grilles sont semblables si on peut passer de l'une à l'autre en permutant les chiffres.
Puisqu'il existe 9! = 362880 permutations de 9 chiffres, on peut se ramener à l'ensemble des 18383222420692992 grilles de sudoku non semblables.
Il nous faut également un groupe, celui des permutations légales de la grille de Sudoku. Avec le logiciel adéquat, on peut montrer qu'il existe 3359232 opérations légales. En tenant compte des classes de conjugaison (certaines opérations se comportent de la même façon - dans l'exemple précédent, c'était le cas de r1 et r5, ou de s1, s3 et s5 ), on peut se ramener à l'étude 275 (classes de conjugaisons de) permutations de la grille de Sudoku.
La grille de sudoku est invariante (à une similitude près) sous l'opération "permutation [...] bande"
Pour chacune de ces 275 opérations, il faut trouver le nombre de grilles fixées (à une similitude près)
- Pour l'opération Id, 18383222420692992 grilles sont fixées.
- Pour l'opération "permutation des colonnes 1, 2 et 3", aucune grille n'est fixée.
- Pour l'opération "permutation circulaire des colonnes au sein de chaque pile, puis permutation circulaire des lignes au sein de la troisième bande", un dénombrement minutieux montre que 21233664 grilles sont fixées (à une similitude près).
- etc.
En appliquant alors le lemme de Burnside, on trouve qu'il existe 5472730538 grilles de sudokus réellement différentes !
Alors ?! Qui a dit que la théorie des groupes n'avait pas d'applications concrètes ?...
Sources :
Les colliers de G. Polyà, un exposé bien plus rigoureux qui parle de formule de Burnside et du théorème de Polyà.
(*) Mathematics of Sudoku I, où Felgenhauer et Jarvis montrent qu'il existe 6.7×1021 grilles de sudoku.
05 février 2012
[#] Pendant ce temps, chez les Sudokus
Il est 13h, bonjour à tous, bon week-end. Voici les titres de l'actualité de ce dimanche :
- Un week-end de grand froid sur la France. C'est la neige qui a paralysé plusieurs heures des automobilistes sur l'autoroute A26.
- Froid, encore : les températures ressenties sont plus faibles que les températures sous abri. Explications, mais sans équations.
- Froid toujours : nos envoyés spéciaux en province nous montreront comment est la neige dans les différents coins de la France.
- Point sur la fashion week : que nous réservent les créateurs de mode en matière de gants et de bonnets ?
- Science : malgré le froid, trois chercheurs ont réussi à déterminer qu'en dessous de 17 chiffres, un sudoku n'a jamais de solution unique.
- Enfin, nous terminerons par la météo, en rappelant qu'il neige en hiver.
[...]
Ouvrons donc ce sujet science, avec l'exploit du mois dernier : Gary McGuire, mathématicien irlandais, a résolu une énigme datant de plus de dix ans, en découvrant le plus petit sudoku qui existe. Pour cela, il a fallu plus de 7 millions d'heures de calculs sur un superordinateur. Explications.
Il n'existe que trois types de sudokus : ceux qui n'ont qu'une unique solution, ceux qui ont plusieurs solutions et ceux qui n'ont aucune solution. Les premiers sont intéressants, et les autres sont terriblement décevants et ne méritent pas le nom de sudoku (étymologiquement, "chiffre unique").
Marcel Bompré, amateur de sudoku, témoigne : "c'est vrai que c'est décevant quand on ne s'aperçoit qu'au dernier moment que la grille que l'on est en train de remplir possède plusieurs solutions différentes. Surtout qu'il fait froid."
En général, moins un soduku possède de cases pré-remplies, plus sa complétion sera difficile. De tous les sudokus connus, les plus dépouillés ne comportent que 17 chiffres révélés.
Marcel Bompré, amateur de sudoku, témoigne : "un jour, j'ai résolu un sudoku avec seulement 17 chiffres révélés. C'était pas facile. Surtout qu'il fait vraiment froid."
Exemple de sudoku à 17 indices.
Peut-on trouver un sudoku à 16 chiffres ? La question a longtemps été ouverte, jusqu'au 1er janvier 2012. Gary McGuire, aidé de deux collaborateurs, ont regardé attentivement les 6.7 milliers de milliards de milliards de grilles complètes existantes afin de voir s'il était possible de leur retirer plus de 64 chiffres sans les dénaturer. Leur conclusion : il n'existe pas de sudoku à 16 chiffres.
Même pour un ordinateur, vérifier une par une les 6.7×1021 grilles existantes reste quelque chose de très long. Heureusement, il est possible de réduire considérablement le nombre de sudokus à inspecter grâce à un théorème appelé "lemme de Burnside" : deux grilles sont équivalentes si l'on peut passer de l'une à l'autre en permutant les chiffres, les colonnes ou les lignes (on ne peut pas vraiment dire que deux sudokus sont différents si on intervertit les 7 et les 5, par exemple)
Équivalence des sudokus :
* permutation des chiffres
* permutation des bandes verticales
* permutation de colonnes au sein d'une même bande
* permutation des bandes horizontales
* permutation de lignes au sein d'une même bande
* inversion des lignes/colonnes
Ces opérations permettent de réduire à 5500 millions le nombre de grilles à inspecter. C'est mieux, mais ça reste long à faire. Il faut donc y aller finement.
La méthode la moins habile pour résoudre le problème est de prendre une par une les grilles complètes et de tester toutes les sous-grilles à 16 indices pour voir s'il en existe des valides. Problème : y a 33 millions de milliards de façons de garder 16 cases parmi 81. En comptant une minute par grille, il faudrait au moins 10000 ans pour arriver à bout du problème.
Les trois compères y sont donc allé un peu différemment, en cherchant les "ensembles inévitables" dans les grilles complètes. On peut illustrer le concept avec le sudoku suivant :
L'un des quatre indices en jaune est inévitable
En retirant les cases jaunes de cette grille, le sudoku aurait deux solutions différentes : il faut en garder au minimum une parmi ces quatre pour une solution unique. En raisonnant de cette façon, on peut en déduire le nombre minimal d'indices amenant à la grille complète en cherchant ces configurations "inévitables". Le reste est une affaire d'informatique : il faut programmer ce principe de manière satisfaisante pour l'appliquer aux 5.4×109 sudokus pleins. C'est ce que les trois chercheurs ont fait, en inventant un nouvel algorithme, qui pourrait d'ailleurs servir dans bien d'autres domaines de l'informatique. Dans les faits, les calculs ont duré presque un an sur le superordinateur Stokes (mais aurait duré 800 ans sur un ordinateur plus classique).
Marcel Bompré, amateur de sudoku, témoigne : "Pfffiou ! C'est long ! Surtout qu'il neige."
La quête d'un sudoku à 16 chiffres est définitivement terminé, mais le travail mathématique ne l'est pas. Tout comme pour la découverte du nombre de Dieu en juillet 2010, l'approche informatique est trop balourde pour être honnête. Il existe sans doute une approche bien plus fine qui pourrait montrer qu'il n'existe pas de sudoku à 16 indices, ni de Rubik's cube que l'on ne peut résoudre en moins de 21 coups.
Rappelons tout de même l'information principale de la journée : il fait froid en hiver.
Sources :
* There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem, l'article de McGuire en prépublication sur arXiv.
* Mathematics of Sudoku I, où Felgenhauer et Jarvis montrent qu'il existe 6.7×1021 grilles de sudoku.
* Mathematics of Sudoku II, où Russel et Jarvis montrent qu'il n'existe que 5.4×109 grilles vraiment différentes.
15 janvier 2012
[#] 2012 : le "jeu de l'année"
Défi : écrire tous les entiers de 1 à 100 en utilisant dans l'ordre les chiffres 2, 0, 1, 2 ainsi que les opérations algébriques classiques ?
En ce dimanche matin, je reprend l'idée de mathforum.org en vous proposant en français le "Jeu de l'année". Le principe du jeu reprends le principe de l'énigme des quatre quatres : écrire tous les entiers de 1 à 100 avec les chiffres de 2012 et les opérations mathématiques classiques.
Dans le détail, les règles sont les suivantes :
- Utiliser une fois (et une seule fois) les quatre chiffres 2, 0, 1 et 2. Dans l'ordre, c'est encore mieux !
- Utiliser les opérations mathématiques classiques : addition (+), soustraction/opposé (-), multiplication (×), division (/). On peut également utiliser les racines carrées (√), l'exponentiation (puissance) (^) et les factorielles (!), ainsi que les parenthèses/crochets.
- Il est permis de concaténer les chiffres de base entre eux (pour obtenir des nombres comme 20 ou 12), ou avec le point décimal (pour écrire les nombres .2, .01 ou 1.2).
Avec toutes ces règles, beaucoup de nombres restent inaccessible, d'où la nécessite d'ajouter plus de symboles. Ainsi, vous pouvez :
- Utiliser la double factorielle (n!!) : la double factorielle d'un nombre n est le produit de tous les entiers congrus à n modulo 2. Par exemple, 6!! = 6×4×2 = 48 et 5!! = 5×3×1 = 15.
- Utiliser la triple factorielle (n!!!) : même principe que la double factorielle, mais en ne gardant que les entiers congrus à 3 modulo n. En exemple, cela donne 7!!! = 7×4×1 = 28 et 8!!! = 8×5×2 = 80.
- Utiliser la n-ième factorielle (n!k). Cependant, le nombre k doit être construit proprement.
- Utiliser les racines k-ième (k√n), avec k construit proprement.
- Utiliser la fonction Gamma (Γ), défini sur les entiers par Γ(n)=(n-1)!
- Utiliser le développement décimal périodique des rationnels. Ainsi, on peut écrire .[2] pour écrire le nombre 0.2222... (=2/9) ou 2.0[1] pour le nombre 2.0111111... (=181/90).
Quelques remarques supplémentaires :
- Il est tout à fait légal d'imbriquer ses factorielles ou ses racines carrées (par exemple, (3!)! est permis).
- N'oublions pas que 0!=1.
- Le point décimal ou le développement décimal périodique ne s'utilise qu'avec les chiffres de base. Il est interdit d'écrire .(1+2) pour écrire .3. De même, .[0!] pour désigner le nombre .111... n'est pas autorisé.
- La fonction inverse n'est pas permise. On peut cependant utiliser le chiffre 1 pour écrire 1/n ou n^(-1). De la même façon, les fonctions "carré" ou "cube" ne sont pas autorisée, sauf en utilisant l'exponentiation pour écrire n^2 ou n^(1+2).
- Pas de fonction altérant l'intégrité des nombres ! Donc, pas de fonctions transcendantes (exp, cos, sin, tan, log, argcotanh, ...), ni de parties entières / parties fractionnaires.
- Dans un premier temps, on va éviter d'utiliser les fonctions combinatoires (nombres d'arrangements, de dérangements, de combinaisons avec/sans répétitions....) ou les fonctions arithmétiques (partage d'un entier, etc.)
Il est maintenant l'heure de jouer ! Pour cela, il faut se munir d'un stylo, d'une feuille de papier et de suffisamment de temps (par exemple, dans le bus, dans la salle d'attente de son ophtalmo, pendant son cours de philo, pendant un exposé très long et très ennuyeux, ...), et de chercher activement comment diable on pourrait écrire le nombre 87, ainsi que tous les autres.
Pour ajouter un peu de piment, je propose un système de points, le but étant d'avoir le plus petit nombre de point. Pour rester dans l'esprit du problème original, certaines solutions sont meilleures que d'autre : il faut éviter de désordonner les chiffres ou de les concaténer. Dans la pratique, pour chaque nombre, on gagne des points pour :
- Utilisation de +, -, ×, /, √, ^ ou ! : 0 points.
- Utilisation du point décimal : 1 point par utilisation
- Utilisation de concaténation : 10 points.
- Chiffres désordonnés : 50 points.
- Utilisation de multifactorielles, de racine n-ième : 5 points par utilisation.
- Utilisation de développement décimal périodique, de la fonction gamma : 30 points par utilisation.
- Nombre non trouvé : 500 points.
Exemple avec le nombre 42 : On peut l'écrire :
42 = 21×2+0 rapporte 60 points, car les chiffres sont désordonnés (50 points), et le nombre 21 a été obtenu par concaténation (10 points).
42 = ((2+0!)!)!!-(1+2)! rapporte 5 points, dus à l'utilisation de la double factorielle.
Le score total étant la somme du score de chacun des 100 nombres à reconstituer.
Maintenant, c'est à vous de jouer !
A l'heure où je poste cet article, mon score est de 4782 (en comptant les 6 nombres non découverts), à vous de le battre et de faire moins !
01 janvier 2012
[#] 2011+1 (Cette nouvelle année est-elle intéressante ? Episode 03)
L'année 2012 est enfin arrivée ! On y croyait plus, et pourtant, elle est là ! Une bonne raison de souhaiter à tous les lecteurs de ce blog une très bonne année...
Oui, mais... Cette année 2012 sera-t-elle plus intéressante que l'année 2011 ? Comme tous les premiers dimanches de janvier, il faut se pencher sérieusement sur la question, avec le seul arbitre digne de confiance, l'OEIS (L'On-Line Encyclopedia of Integer Sequences), l'encyclopédie de toutes les suites de nombres entiers, de la suite des nombres premiers de Mersenne [A000668] jusqu'aux nombres composés dont la somme des facteurs est première [A046363]. Si un nombre donné possède une propriété intéressante, il sera dans l'encyclopédie !
Ainsi, le nombre 2010 apparaît dans 151 suites (11 de plus que l'année dernière, l'encyclopédie est en perpétuelle évolution). Par exemple, 2010 est un nombre de la forme (n+1)(n+2)(n+3)(9n+4)/24 ([A051798]).
Le nombre 2011, quant à lui, ne possède pas moins de 349 propriétés (18 de plus), la plupart croisant sa primalité avec d'autres propriétés extravagantes. Par exemple, 2011 est le huitième plus petit nombre premier congru à 2 modulo 41 ([A142199]).
Et 2012, alors ? Plus de propriétés que 2011 ? Moins de propriétés que 2010 ? Accrochez vous à votre siège, la réponse ne sera pas agréable, car :
2012 ne possède que 101 propriétés intéressantes !
Pourquoi si peu de propriétés ? Faut-il commencer à déprimer maintenant ? Quel rapport avec le triple A ? Regardons dans le détail quelques propriétés intéressantes du nombre 2012 !
A005341 : La suite de Conway
Enigme : complétez la suite suivante :
1
11
21
1211
111221
...
Oui, bon, tout le monde la connaît, c'est la suite de Conway, où chaque ligne est la description de la ligne précédente. Il se trouve, par le plus grand des hasards, que le 27e terme de cette suite possède 2012 chiffres !
A161328 : la structure des tri-cure-dents
Bien que le nombre 2011 apparaisse dans une suite de structures en cure-dent, 2012 n'est pas en reste. L'objet de base de cette structure n'est plus le cure-dent, mais le tri-cure-dent, un trident formé par 3 segments (angle entre chaque dent : 60°) :
Structure des tri-cure-dents, étape 1 (1 trident)
Trois extrémités sont disponibles : l'étape 2 consiste donc à ajouter 3 nouveaux tri-cure-dents.
Structure des tri-cure-dents, étape 2 (4 tridents)
Cette fois-ci, il n'y a que 5 extrémités disponibles (et non 9). Pour chaque nouvelle étape, on ajoutera des tri-cure-dents aux places disponibles, sauf si les cure-dents venaient à se superposer.
Structure des tri-cure-dents, étape 3 (9 tridents), 4 (16 tridents) et 5 (29 tridents).
En continuant jusqu'à l'étape 42 cette structure, il nous faudra exactement 2012 tri-cure-dents !
A134970 : les nombres canyon
On appelle "nombre canyon" un nombre qui ressemble... à un canyon (une vallée profonde entre deux falaises). Autrement dit, c'est un nombre possédant le même premier et dernier chiffre, et ses chiffres intermédiaires sont rangés par ordre décroissant puis par ordre croissant. Le plus simple, c'est de regarder des exemples : 2012 et 32013 sont des nombres canyon :
Canyon (du catalan canyó) : vallée très encaissée résultant de l'érosion hydraulique.
Le 46ème plus petit nombre canyon (et le plus petit nombre canyon à 4 chiffres) n'est autre que le nombre 2012.
Fait intéressant : il n'y a que 116505 nombres canyons, le plus grand d'entre eux étant le nombre 9876543210123456789.
Mais 2012 a encore d'autres propriétés intéressantes. Par exemple :
- le carré du miroir de 2012 est égal au miroir de son carré (comme 2011, en fait) ([A035123]).
- le produit de 2012 et de son miroir est un palindrome : 2012 × 2102 = 4229224 (2011 vérifie la même propriété) ([A048344]).
- 2012, ainsi que 2013, 2014 et 2015, ont exactement 3 diviseurs ([A045940]).
- le nombre de chiffres de 2012! est un carré ([A006488]).
- 2012 possède un mois de février avec 5 mercredis ([A141039]) et 3 "vendredi 13" ([A190653]).
Et la santé !
25 décembre 2011
[#] Top 10 des mathématiques religieuses
Ça alors ! Je n'ai rien écrit sur ce blog depuis plus d'un mois !
Ça alors ! Aujourd'hui c'est Noël !
J'ai donc deux bonnes raisons de vous proposer en ce jour un nouveau top 10 sur ce blog. Et pour me racheter d'avoir proposé l'année dernière des tops 10 mathématiques sur la bouffe, sur les bestioles ou sur les voyages, voici aujourd'hui un récapitulatif du divin, du mystique, du pieux et du mythologique dans les mathématiques contemporaines !
Numéro 10 : La corne de Gabriel
La trompette de Gabriel (tronquée)
Le jour du jugement dernier, l'ange Gabriel soufflera dans sa corne (une corne quelconque, au détail près qu'elle est infiniment longue). Une fois pour faire peur tout le monde, puis une seconde fois pour montrer qu'il n'est pas là pour rigoler. Et après, il prendra des pots de peinture. Un premier pour remplir de peinture l'intérieur de sa corne ; puis un deuxième, pour en peindre l'extérieur. Et c'est là que l'ange Gabriel peut utiliser ses pouvoirs magiques : pour peindre l'extérieur de sa trompette infinie, il devra utiliser une infinité de peinture, mais n'utilisera pas plus d'un pot pour en remplir l'intérieur...
Au XVIIe siècle, avant même l'invention du calcul intégral, Evangelista Torricelli parvient à montrer qu'il est possible d'imaginer un solide infini possédant tout de même un volume fini. Un paradoxe en entraînant un autre, cet objet possède une surface infinie. Cet objet, c'est la corne de Gabriel (alias trompette de Torricelli), qui est la surface engendrée par la rotation autour de l'axe (Ox) de l'hyperbole d'équation y=1/x sur l'intervalle [1,+∞[
Numéro 9 : Le problème des bœufs d'Hélios
Tuer le bétail de Hélios : mauvaise idée.
Hélios, qui n'est autre que le Soleil de la mythologie grecque, possède des troupeaux de taureaux sur l'île de Trinacrie (troupeau qui sera abattu par les hommes d'Ulysse lors de ses pérégrinations). Le nombre de taureaux blancs est égal au nombre de taureaux bruns plus 5/6 du nombre de taureaux noirs. Le nombre de taureaux noirs est égal au nombre de taureaux bruns plus 5/6 du nombre de taureaux gris. Le nombre de taureaux gris est égal au nombre de taureaux bruns plus 13/42 du nombre de taureaux blancs. Le nombre de vaches blanches est égal aux 7/12 du nombre d'animaux noirs. Le nombre de vaches noires est égal aux 9/20 du nombre d'animaux gris. Le nombre de vaches grises est égal aux 11/30 du nombre d'animaux bruns. Le nombre de vaches brunes est égal aux 13/42 du nombre d'animaux blancs. Mézalors, combien Hélios a-t-il de bêtes ?
Ah, j'oubliais deux détails supplémentaires : en ajoutant le nombre de taureaux blancs et noirs, on trouve un carré parfait ; en additionnant le nombre de taureaux gris et bruns, on trouve un nombre triangulaire...
Débrouillez-vous avec ça !
Ce problème (à l'origine, un poème écrit par Archimède mettant au défi la sagacité de ses lecteurs), a été redécouvert au XVIIIe siècle dans le fin fond d'une bibliothèque. Il est peu vraisemblable que les mathématiciens antiques aient réussi à le résoudre, étant donné la taille des nombres entrant en jeu dans les équations. La première solution exacte ne sera pas publiée avant 1880.
Le problème met donc en jeu des équations diophantiennes (les solutions sont des nombres entiers). Avec un peu de patience, mais sans grande difficulté, on peut trouver que le nombre d'animaux est un multiple de 50 389 082. Il faut beaucoup plus de patience pour s'attaquer aux deux autres hypothèses (l'histoire du carré parfait et du nombre triangulaire), puisqu'il faut utiliser des résultats d'arithmétiques plus compliqués. La solution exacte apparaît alors : Hélios possède donc (au moins) 7.76×10206544 têtes de bétail (qui est donc un nombre à plus de 200 000 chiffres. A titre de comparaison, on estime à 1085 le nombre de particules dans l'Univers visible). La réponse a de quoi étonner, les nombres de l'énoncé n'étant pas si terribles que ça !
Numéro 8 : Le théorème de la chaussette de Noël
Si avec ça, le Père Noël ne passe pas chez moi, je ne comprends plus rien...
Parfois, il suffit de peu pour baptiser une propriété mathématique. Le théorème de la chaussette de Noël (alias théorème de la crosse de Hockey) en est un exemple... Il indique que, dans un triangle de Pascal (une pyramide où chaque brique est la somme des deux briques qu'elle soutient), lorsque l'on somme les premiers k premiers éléments d'une diagonale, le nombre que l'on trouve est celui du pied de la diagonale (le k-ième terme de la diagonale suivante).
Le nom du théorème vient de la ressemblance frappante entre la chaussettes que l'on laisse sur le bord de la cheminée et les cases que l'on colore dans le triangle de Pascal pour faire apparaître la relation :
Numéro 7 : Le problème de l'ange
Un ange, un démon, un échiquier infini : le combat entre le bien et le mal peut commencer !
Le problème de l'ange, casse-tête que l'on doit à Conway, met en scène un ange cherchant à fuir la fureur d'un démon vengeur. Tout ceci se déroule sur un échiquier infini, sur lequel l'ange se déplace comme le roi d'un jeu d'échec (un pas dans l'une des huit directions possibles). Dès que l'ange fait un pas, le démon détruit une case de son choix, n'importe laquelle, sauf celle où l'ange se trouve. Si l'ange se déplace intelligemment, parviendra-t-il toujours à s'échapper ? Si le démon détruit les bonnes cases au bon moment, pourra-t-il toujours enfermer l'ange ?... Il y aura forcément un gagnant, mais lequel ?
Le cas de l'ange de force 1 n'est pas si difficile que ça à résoudre. Mais qu'en est-il d'un ange de force n, qui se déplace de n pas avant que le démon ne détruise une nouvelle case ?
Le cas n=1 a vite été résolu par Conway (en 1982) : face à un démon très malin, il finira toujours par se faire enfermer. La solution implique de créer un enclos 35×35. Pour les anges plus forts, le problème est resté ouvert plus longtemps. Conway a même mis à prix son problème : 100$ pour le premier à montrer qu'un ange suffisamment fort peut toujours gagner, 1000$ pour celui qui montre que le démon peut toujours gagner contre un ange suffisamment fort.
Ce n'est qu'en 2006 que la résolution du problème (dans sa forme généralisée) apparaît, lorsque Brian Bowditch montre que l'ange de force 4 finit toujours par s'échapper. Un an plus tard, András Máthé donne la réponse attendue depuis les années 80 : oui, l'ange de force 2 peut toujours s'échapper. Le bien a gagné !
Numéro 6 : Le nombre de la bête
Le nombre de la bête est 666, et c'est comme ça.
On ne peut pas passer à côté du nombre mystique par excellence : le chiffre (sic) de la Bête. Trois 6 accolés forment donc LE nombre diabolique, le nombre 666 (surtout depuis qu'il est cité dans la plupart des traductions de l'Apocalypse de Jean).
Du coup, de nombreux concepts de numérologie en découlent :
- les nombres de l'apocalypse : un nombre qui s'écrit avec 666 chiffres (par exemple, le 3184 terme de la suite de Fibonacci).
- les nombres diaboliques : un nombre dont la somme des n premières décimales est 666. Par exemple, pi est diabolique, car la somme de ses 144 premières décimales fait 666. De la même façon, le nombre d'or ou √6 sont diaboliques. Encore plus fort : les nombres cos(666), √√√666, 666√666, π666 ou 6661/666 sont diaboliques !...
- les nombres apocalyptiques : une puissance de 2 qui contient la suite de chiffres 666. Les plus petits nombres apocalyptiques sont 2157 et 2192.
- le nombre de Legion : celui qui vaut 666666, et qui s'écrit donc avec 1881 chiffres.
- le nombre de Leviathan : celui qui vaut (10666 )! (où ! désigne la factorielle). C'est donc un nombre qui s'écrit avec approximativement 6.656×10668 ...
Numéro 5 : L'escalier du diable
Le diable ne se contente pas d'un escalier classique...
Restons dans le satanisme, avec l'escalier du diable (aussi connu sous le nom d'escalier de Cantor). En quoi cette courbe est plus diabolique que n'importe quelle autre ? Eh bien, c'est simple : d'habitude, une fonction continue dont la dérivée vaut zéro partout (donc, aucun accroissement) est une fonction constante. La fonction du diable (représentée par cette courbe en escalier) est une fonction continue dont la dérivée est nulle presque partout -nulle partout, sauf éventuellement en un négligeable de points - mais qui n'a rien de constante (puisqu'elle est quand même parfaitement croissante). Elle ne remet heureusement pas en cause le théorème, puisqu'il faudrait que sa dérivée soit nulle vraiment partout, ce qui n'est pas le cas aussi.
Numéro 4 : L'hexagramme mystique de Pascal
Mystique, non ?...
Placez six points sur un cercle (ou sur n'importe quel autre conique, comme une ellipse, une parabole ou une hyperbole), et reliez ces points. Vous obtenez alors un hexagone. Fait intéressant : les 3 points formés par l'intersection des côtés opposés de cet hexagone sont alignés ! C'est ainsi que s'énonce le théorème de Pascal (alias, théorème de l'hexagramme mystique).
Bien sûr, le théorème marche quand l'hexagone n'est pas croisé (les points d'intersection sont alors à l'extérieur de la conique), mais fonctionne aussi avec un hexagone croisé. Un hexagramme, en fait. Lorsque Blaise Pascal a découvert à l'âge de 16 ans ce théorème grâce à la figure de l'hexagramme, il l'aurait qualifié de "mystique". Le nom est resté !
Notons que le théorème de Pascal fonctionne toujours lorsque la conique est dégénérée (et qu'elle est un couple de droite). Même que c'est le théorème de Pappus.
Numéro 3 : Le théorème de l'étoile de David
Vous aurez reconnu, au travers de cette étoile de David, une partie du triangle de Pascal (avec ses colonnes et ses lignes inversées). Le théorème de l'étoile de David, découvert en 1972 par H.W. Gould, énonce donc une étonnante propriété du triangle de Pascal : le PGCD des sommets d'un des triangles est égal au PGCD des sommets de l'autre. Autrement dit :
Le théorème peut même se généraliser à une étoile plus grande, mais ça devient tordu...
Numéro 2 : Le nombre de Dieu
Le nombre de Dieu est 20. Pas plus.
Que fait Dieu lorsqu'on lui donne un Rubik's Cube à résoudre ? Eh bien, il le fait au plus vite, et passe à autre chose. L'algorithme qu'il utilise est le plus puissant de tous : c'est l'algorithme de Dieu. Pour chacune des 252 003 274 489 856 000 positions possibles du cube, cet algorithme donne la suite des mouvements à effectuer pour le ramener au plus vite en position initiale. Fait intéressant : il ne faut jamais plus de 20 mouvements pour résoudre un cube de Rubik. Ce nombre, 20, est appelé nombre de Dieu.
Ce théorème ("le diamètre du graphe du Rubik's Cube est 20") est plutôt récent, puisqu'il ne date que de juillet 2010 ! Pour le déterminer, l'équipe de mathématiciens qui s'y est collé a utilisé la force de calcul des ordinateurs de Google pour déterminer ce résultat en quelques minutes (après de longue nuits à réfléchir à la simplification du problème : partition des configurations de départ, suppression des symétries, optimisation de l'algorithme...).
Numéro 1 : La proportion divine
Dans tout dodécaèdre régulier sommeille le nombre d'or...
La première place de ce top n'est pas du tout méritée, puisqu'elle revient au nombre d'or, baptisée "proportion divine" à la Renaissance par Luca Pacioli. C'est donc dans le livre du moine franciscain De divina proportione que l'on retrouve pour la première fois un lien entre l'antique problème "du partage d'un segment en moyenne et extrême raison" et de la perfection d'un rapport qui "concorde avec les attributs qui appartiennent à Dieu". Le nombre d'or perdra progressivement son caractère divin pour devenir au XIXe siècle un incontournable de l'esthétisme...
Le plus doré de tous les nombres
J'aurais également pu parler de la croix de Saint-André, plus connue sous le nom de "croix de la multiplication", ou de la courbe du diable, une quartique ressemblant vaguement à un diabolo...
Sources :
10 - Illustration : Gabriel Horn
9 - Le problème des boeufs d'Hélios sur wikipédia
Illustration : Les Compagnons d’Ulysse volant le bétail d’Hélios, par Pellegrino Tibaldi
7 - Le problème de l'ange, et ses solutions, PLS n°354, avril 2007
Illustration : Jacob Wrestling with the Angel, par Gustave Doré
6 - Illustration : The Number of the Beast is 666, par William Blake
5 - Illustration : Cantor function
3 - Le théorème de l'étoile de David et ses généralisations, sur Mathworld
2 - Illustration : Rubik's Cube
1 - Illustration : Dodécaèdre de Platon
20 novembre 2011
[#] Miction impossible
Les mathématiciens traitent de sujet grave, comme lorsqu'ils s'interrogent sur les bornes inférieures et supérieures de la première valeur propre d'un opérateur de diffusion non-locales (1). Les mathématiciens s'occupent de sujets difficiles, comme celui du théorème de Schur-Horn pour les opérateurs à spectre fini (1). Mais les mathématiciens s'occupent surtout de sujets fondamentaux, comme celui du meilleur choix possible dans une rangée d'urinoirs (2).
Oui, ça faisait longtemps que ce blog n'avait pas eu de nouveau billet. Surtout que je me contente aujourd'hui de reprendre la dernière entrée de chez Globule et télescope. Mais n'oublions pas que ce 19 novembre, c'était la journée mondiale des toilettes, et que ce genre d'événement n'arrive qu'une seule fois dans l'année.
C'est donc avec le plus grand sérieux que deux mathématiciens (l'un canadien, l'autre américain), ont mis à profit leur génie pour répondre à la question suivante :
Étant donné une rangée d'urinoirs, lequel faut-il choisir pour maximiser le maintient de son intimité ?
Autrement dit, quel urinoir choisir pour minimiser la probabilité que quelqu’un choisisse l'urinoir d'à-côté ? Evangelos Kranakis et Danny Krizanc proposent, dans un papier de 12 pages, plusieurs éléments de réponses.
Considérons donc des toilettes classiques : une seule rangée de n urinoirs, la porte d'entrée d'un côté, le mur de l'autre. La situation est la suivante : vous êtes le premier à entrer dans ces toilettes pour un besoin pressant. On suppose également que les urinoirs sont propres. Alors, quel urinoir choisir pour une miction pérenne ?
21 urinoirs, un seul bon choix... Lequel ?!
L'instinct indique que le meilleur choix possible est l'urinoir le plus éloigné de la porte. Ainsi, si quelqu’un d'autre passe la porte des WC messieurs, il devrait choisir l'urinoir opposé, vous permettant de finir tranquillou ce que vous avez si bien commencé. Mais pour en être vraiment sûr, il faut modéliser le problème !
Dans ce modèle, nous considérerons que tout homme a ses besoins d'intimité. A moins d'y être obligé, aucun homme ne cherchera à être voisin d'un urinoir occupé. Si il y est contraint, on dira que les toilettes sont "saturées". Votre choix est primordial : il faut maximiser le temps avant la saturation ! On dit qu'un urinoir est "privé" si les deux urinoirs d'à côté sont libres.
Premier modèle : l'homme est paresseux
Pour ce premier modèle, on suppose qu'un homme entrant dans les toilettes prendra le premier urinoir privé disponible, celui le plus proche de la porte. Si le nombre n d'urinoir est pair, la configuration saturée est celle où la moitié des urinoirs sont occupés (n/2 urinoirs occupés : ceux de rang impair). Remarquons alors que le choix de l'urinoir que vous ferez (qu'il soit de rang pair ou impair) n'aura aucune incidence sur le temps de saturation.
Exemple avec 10 urinoirs : que vous choisissiez le septième ou le huitième, seule 4 personnes pourrons venir avant que les toilettes soient saturées.
Dans le cas où le nombre n d'urinoirs est impair, il ne faut impérativement choisir un urinoir de rang impair. Dans ce cas, la saturation arrivera à (n+1)/2 urinoirs occupés, au lieu de (n-1)/2 !
Exemple avec 9 urinoirs : si vous choisissiez le septième, 4 personnes pourrons venir avant que les toilettes soient saturées, elles satureront au bout de 3 si vous choisissez le sixième.
Remarquons que, une fois que les toilettes sont saturées, les nouveaux arriveront choisiront au hasard l'un des urinoirs disponibles. Pour minimiser la probabilité d'avoir un voisin de courtoisie, le mieux est de minimiser le nombre d'urinoirs voisins libres. Le meilleur choix est donc de prendre un des emplacements extrême (un seul voisin possible). Résumons ceci par des équations : si vous choisissez l'urinoir 1 ou n, le temps moyen avant d'être dérangé sera proportionnel à
et si vous choisissez un autre urinoir, le temps d'attente sera proportionnel à
Le choix est donc vite fait : les urinoirs extrémaux sont les plus sûrs !
Deuxième modèle : l'homme est pudique
Dans ce deuxième modèle, le nouvel entrant ne cherche pas à prendre le premier urinoir privé qu'il rencontre, mais cherche à maximiser la distance qui le sépare de l'homme le plus proche. Si plusieurs urinoirs maximisent la distance de sécurité, le choix est fait au hasard.
Remarquons que, quel que soit le choix que vous ferez, le prochain homme qui entrera choisira un urinoir extrémal. Appellons A(n,i) le nombre d'hommes pouvant entrer dans les toilettes avant qu'elles ne soient saturées si il y a n urinoirs et que vous choisissez le i-ème. Pour des raisons de symétrie, ce nombre est défini sans ambiguïtés.
Par exemple, pour 12 urinoirs, si vous choisissez le premier, 4 autres individus pourront venir alors que si vous choisissez le troisième, vous pourrez accueillir un homme en plus.
Expérimentalement, on peut calculer quelques valeurs de A. Ici, on voir queA(12,1)=A(12,2)=5, alors que A(12,3)=A(12,4)=6.
Avec un peu de méthode, on peut trouver l'expression de A(n,i) :
Ici, B(n) correspond au nombre d'homme nécéssaire pour saturer une rangée de n urinoirs lorsque les deux urinoirs extrémaux sont occupés.
La fonction B peut être explicitée (avec plein de logarithmes et de parties entires), mais il n'y a pas de formule donnant le i qui maximise A(n,i). Un détail : choisir un urinoir extrémal ne que rarement le choix optimal. Du coup, pour choisir le meilleur emplacement, il faut venir aux toilettes avec un ordinateur...
Allez, je suis beau joueur, je vous donne les meilleurs spots pour les plus petites toilettes (les petites valeurs de n) :
Tableau récapitulatif des meilleurs emplacements
Troisième modèle : l'homme est bourré
On peut également expérimenter un troisième modèle : un homme qui entre dans les toilettes cherche simplement un urinoir sans voisins, rien de plus. Son choix se fera uniformément parmi les urinoirs privés disponibles. Si aucun urinoir privé n'est disponible, il en choisira un au hasard parmi ceux restant.
Dans ce troisième modèle, les calculs sont un peu plus complexes, mais la conclusion est la même que pour le premier modèle : le meilleur choix est le choix de l'urinoir extrémal !
De nombreuses variantes peuvent être apportées au problème initial. On peut, par exemple, introduire la notion d'urinoir "semi-privé" (seulement 1 voisin) : à choisir, un homme préfère avoir un voisin plutôt que deux ! Il faut également réfléchir au cas où vous n'êtes pas le premier à entrer dans les toilettes (situation initiale non vide), au temps que l'on passe à uriner (situation dynamique), au cas où les hommes font pipi sur un mur plutôt que dans des urinoirs (situation continue), au cas où plusieurs rangées sont disponibles (plusieurs dimensions). Le sujet est vaste !
Le problème de l'urinoir est encore sur bien des points une question ouverte, et terriblement d'actualité !
Et la semaine prochaine, je ne parlerai pas du problème du papier toilette (3), de Donald Knuth...
Notes de bas de page :
(1) Papier pris au hasard sur arXiv : Lower and upper bounds for the first eigenvalue of nonlocal diffusion problems in the whole space et The Schur-Horn theorem for operators with finite spectrum.
(2) The Urinal Problem, par Evangelos Kranakis and Danny Krizanc
(3) The toilet paper problem, par Donald Knuth
(*) Illustration des toilettes : Norbert Nagel
