06 juillet 2014

Du simple au Dobble

C'est les vacances, l'occasion de sortir une nouvelle fois les jeux de société pour jouer avec beau-papa. Pas de Monopoly ou de serpents et échelles, sortons plutôt un véritable jeu moderne, comme il en existe des floppées aujourd'hui, tous plus inventifs les uns que les autres (sérieusement, allez dans les boutiques de jeu de société !). Je vais donc parler de Dobble de Asmodée, un jeu d'observation et de vitesse pour toute la famille, qui cache une structure mathématique hallucinante.  Une fois n'est pas coutume, l'article qui suit m'a été inspiré d'un des derniers épisodes de Podcast Science.

p-3700427700183_15543_3-dobble
55 cartes, 8 symboles par cartes ; deux cartes spont retournées, quel est leur symbole en commun ?...

Le concept du jeu Dobble est assez simple, surtout quand on le compare aux mathématiques qui ont été déployées pour le concevoir. Plusieurs variantes des règles du jeu existent, mais le principe reste toujours le même : deux cartes contenant chacune 8 symboles sont présentées, il faut retrouver le plus rapidement possible quel est le symbole commun aux deux cartes.

Là où les mathématiques rentrent en jeu, c'est que quel que soit le couple de cartes retournées, il y a toujours un (et un seul) symbole commun. La conception des cartes n'a donc pas du tout été faite au hasard, et n'est pas du tout évidente a priori. 

Comment fabriquer soi-même son propre jeu Dobble ? Combien faut-il prévoir de cartes ? De symboles ? Puis-je faire un Dobble à 157 cartes ? Il n'y a qu'une seule façon de résoudre le problème : comprendre ce que sont les plans projectifs finis !

Dobble d'ordre 7
Le jeu original Dobble chaque contient 8 symboles différents par cartes et 55 cartes.

La première chose à dire, c'est qu'il n'existe pas un symbole qui soit commun à toutes les cartes, puisque cela diminuerait grandement l'intérêt du jeu. Mais cette trivialité va nous permettre de dénombrer le nombre de cartes existant au maximum.
Pour cela, on prend un des symboles (disons, le morceau de fromage), et on compte le nombre de cartes où il apparaît (disons r). Ces r cartes ont des symboles tous différents.
D'après ce que l'on vient de dire, il existe au moins une autre carte sur lequel le morceau de fromage n'apparaît pas. Mais cette carte a tout de même un symbole en commun avec chacune des r cartes possédant le fromage (différent à chaque fois). Ces symboles étant tous différent, le nombre r est donc au maximum égal à 8.
Donc, au maximum, il y a 8 cartes possédant un symbole donné.

Prenons maintenant une carte au hasard. Cette carte possède 8 symboles. Pour chaque symbole, on peut compter (au plus) 7 autres cartes possédant ce symbole, ce qui donne finalement 1+8×7 = 57 cartes différentes au maximum.

En suivant le même raisonnement, on peut donc montrer qu'un jeu de Dobble avec n symboles par cartes contiendra au maximum 1+n(n-1) cartes.

Mais alors, pourquoi le jeu Dobble ne contient que 55 cartes ? La réponse est désespérement terre à terre : l'imprimeur du jeu ne permettait que de faire 60 cartes, et les auteurs ont préféré mettre 5 cartes "règles" pour diversifier le jeu, plutôt que d'en respecter la complétude (ce qui ne chagrinera que les mathématiciens, qui ne sont heuresement pas le coeur de cible du jeu...).

Dobble d'ordre 2
La règle qui régit les cartes du Dobble est 

Deux cartes possèdent toujours un (et un seul) symbole en commun

Ce qui rappelle forcément un des principes de base de la géométrie :

Par deux points distincts passe toujours une (et une seule) droite.

Du coup, on a envie de faire le rapprochement, et de se dire que les cartes d'un jeu de Dobble peuvent être les points d'un plan, tandis que les symboles seront les droites. Et ça marche plutôt bien !

PG(2,1)
Représentation géométrique du jeu de Dobble à 2 symboles par cartes (et donc, à 1+2*1 = 3 cartes)

Bien sûr, le plan contient une infinité de points, et par chaque point passe une infinité de droites, ce qui permettrait de fabriquer un jeu de Dobble possédant une infinité de cartes, chacune possédant une infinité de symboles... Le plan euclidien complet possède beaucoup trop de points !
Du coup, on va limiter notre plan à, disons, seulement 4 points (les autres points n'existent pas !), ce qui permet de fabriquer un jeu jouable comptant 4 cartes et 6 symboles :

PG(2,2,0)
On se limite ici à 4 points-cartes : les droites roses et vertes n'ont donc pas de points d'intersection. On peut même aller jusqu'à dire qu'elles sont parallèles, puisqu'elles ne se coupent pas.
Par chacun des 4 points passe donc exactement 3 droites.

D'un côté, on sait que pour n=3 symboles par cartes, il semble possible de fabriquer 1 + 3*2 = 7 cartes.
D'un autre côté, on sait que quand la géométrie est projective, les droites parallèles se coupent sur une droite d'horizon, et qu'en plus, le principe de dualité laisse entendre que si par 1 point passe 3 droites, alors on doit toujours compter sur 1 droite 3 points.

Du coup, il nous faut trouver un moyen d'ajouter 3 cartes à ce Dobble, en ajoutant des points d'intersection aux droites parallèles (violet/rouge, bleu/jaune, ainsi que rose/verte, qui sont parallèles). Pour cela, il va être nécéssaire de prendre conscience que "droite" ne fera plus référence à l'objet géométrique rectiligne, mais à un *truc* qui passe par plusieurs *points* : on peut donc courber les droites, et faire apparaître trois nouveaux points d'intersection.

PG(2,2)

Un Dobble parfait : 7 droites (symboles) et 7 points (cartes) 

Cette représentation est affreuse, d'autant qu'il existe une représentation un peu plus habituelle de ce regroupement de 7 points et 7 droites où chaque droite contient 3 points et où chaque point est à l'intersection de 3 droites, le plan de Fano :

Fano
Le plan de Fano (rien à voir avec les reliques de la mort)
Contrairement aux apparences, le cercle vert est bien une droite, et passe comme les autres par trois points

Le plan de Fano est en fait l'exemple le plus dépouillé qui existe de plan projectif, puisqu'il ne contient pas une infinité de points selon deux dimensions (comme dans la représentation basique d'un plan, qu'il soit projectif ou non), mais est composé de seulement 7 points. Les axiomes de base de la géométrie (projective) s'y appliquent cependant toujours :
- par deux points passe toujours une (et une seule) droite
- deux droites se coupent toujours en un (et un seul) point (la notion de parallélisme n'existe pas en géométrie projective, les droites se coupent à l'infini)
- il existe un quadrangle n'ayant pas trois points alignés (pour éviter les cas dégénérés)

Lorsqu'une structure respecte ces trois axiomes, elle peut prétendre au titre de plan projectif. Si, en plus, elle possède un nombre non infini de points, on parlera... de plan projectif fini. C'est le cas du plan de Fano.
Un jeu de Dobble complet (possédant les n(n-1)+1 cartes avec n symboles) est donc un plan projectif fini, puisque les trois axiomes y sont bien respectés, si on admet la convention 'point'='carte' et 'droite'='symbole' :
- deux cartes ont toujours un (et un seul) symbole en commun
- deux symboles donnés n'apparaissent ensemble que sur une seule carte
- on peut trouver quatre cartes ayant deux à deux des symboles communs différents (sinon, le jeu n'est pas intéressant)

L'exemple du jeu de Dobble à 3 cartes et 2 symboles par carte ne peut pas être qualifié de complet, à cause du dernier axiome non respecté. En rajoutant une quatrième carte, on se retrouve à construire un Dobble à 7 cartes, qui lui, est complet, puisque c'est le plan de Fano. En généralisant, l'existence d'un jeu de Dobble complet à n symboles entraîne l'existence d'un plan projectif fini à n²-n+1 points et droites, et vice versa.

Pour construire des Dobble, il suffit donc finalement de construire des plans projectifs finis, et le jeu du Dobble nous permet de donner les propriétés de ces plan projectifs :
Etant donné un plan projectif fini, il existe un entier n tel que 
- il contient n²–n+1 points
- il contient n²–n+1 droites
- chaque droite est composé de n points
- par chaque point passe n droites
Le nombre n n'est pas appellé l'ordre du plan projectif. Par contre, on appelle ordre du plan projectif le nombre q=n–1 (un plan projectif fini d'ordre q possède donc q²+q+1 points et droites, chaque droite contient q+1 points, chaque point est à l'intersection de q+1 droites).

Bref, construisons encore plus de plans projectifs finis, pour ensuite construire encore plus de Dobbles !

Dobble d'ordre 3
Pour construire des plans projectifs finis, on peut tenter de généraliser la construction du plan de Fano, qui était d'ordre 2. Pour cela, nous allons avoir besoin... des corps finis !

Un corps, c'est une structure algébrique dans lequel on peut faire des additions, soustractions, multiplications et divisions. L'ensemble infini des nombres réels est un l'exemple le plus intuitif de corps mais il y en a bien d'autres, comme par exemple le corps F3, composé des trois nombres 0, 1 et 2. Les additions et multiplications fonctionnent comme sur les entiers habituels, mais on n'y garde que le reste dans la division euclidienne par 3 :

F3
Table d'addition et de multiplication dans le corps F3
Ici, 2+2 = 1, car 4 a pour reste 1 dans la division euclidienne par 3.

Le corps F<sub>3</sub> donne naturellement naissance au plan F²<sub>3</sub>, qui possède 9 points :

F3²
Le plan (non projectif) fini F²3

Puisqu'on peut y faire additions et multiplication, on peut y faire des fonctions affines, ce qui correspondra aux équations des droites. Miracles des corps finis : chaque droite passera par exactement 3 points !

Droites de F3²
On peut ainsi écrire 12 équations de droites, réparties en 4 familles de 3 droites parallèles.
Remarquons que y = x+2, y = x -1 sont des équations d'une même droite, puisque, dans le corps F3, 2 = -1.

Par chacun des 9 points passe exactement 4 droites : on vient de fabriquer un Dobble à 9 cartes, 12 symboles et 4 symboles par cartes, en faisant correspondre un symbole à chaque droite. 
Mais on peut faire encore mieux, puisqu'on peut a priori atteindre 13 cartes, en rendant projectif ce plan. Pour cela, on admet que chaque famille de droites parallèle se coupent sur une droite à l'infini, ce qui nous donne les 3 points d'intersection manquant et la droite manquante :

Fano3
Chaque droite est composé de 4 points, par chaque point passe 4 droites
Cette structure, construite à partir du corps F3, permet de construire un jeu de Dobble à 4 symboles par cartes

En réorganisant les points, on peut obtenir une version un peu plus symétrique du plan projectif fini d'ordre 3 :

GraphePlanProjOrdre2
Plan projectif fini d'ordre 3.
On admet que le point central et les trois points extrémaux sont alignés, pour ne pas alourdir le schma avec une droite disgracieuse

Dobble d'ordre q premier
Cette construction se généralise très facilement, mais seulement pour les ordres où q est un nombre premier, puisque, dans ce cas, le corps Fq existe, et se construit à partir à partir des entiers 0, 1, 2, ..., q-1 et de la division euclidienne par q.

Du coup, en prenant q=5, on peut construire le corps F5, le plan associé à 25 points, ses 30 droites (5 par direction), puis sa version projective à 31 points et 31 droites.
Le gros problème, c'est que si on le dessine, ça sera complètement illisible... Pas grave, on va le faire seulement algébriquement : les points sont de la forme (x,y), avec x et y compris entre 0 et 4 ; les droites sont de la forme y=ax+b ou x=b, avec a et b compris entre 0 et 4, ainsi que la droite à l'infini. Chaque famille de droite donne naissance à un point à l'infini.
Il n'y a plus qu'à compléter le tableau pour avoir une idée d'un plan projectif fini d'ordre 5, et donc, d'un Dobble à 6 symboles par cartes.

PG(5,1)
Le tableau permettant de fabriquer le Dobble d'ordre 5, autrement dit, l'édition Junior du Dobble.
La notation des points à l'infini est loin d'être propre, mais la notation (∞,2∞) correspond au point à l'infini dans la direction y = 2x.

La même construction avec q=7 permet de fabriquer le Dobble à 8 symboles par cartes, autrement dit, le Dobble classique. Les joueurs invétérés fabriqueront eux même leur version du jeu à 12 symboles par carte (q=11) ou à 14 symboles par carte (q=13)...

Dobble d'ordre q quelconque
Et pour les autres valeurs de q ?... Eh bien, ça va dépendre !

Déjà, il y a les puissances des nombres premiers : 4=2², 8 = 23, 9 = 3², ...
Pour chacun de ces ordres, il existe un corps fini ayant le nombre adéquat d'éléments. Le seul soucis, c'est que la construction est un peu plus compliquée (on doit passer par des calculs avec des polynômes, que je ne vais pas détailler ici). Par exemple, le corps à 4 éléments (0, 1, u et v) ressemble à ça :

F4
Table d'addition et de multiplication de F4

Du coup, à partir de ces tables, on peut faire le même travail sur les équations des droites... Et ça marche ! 

PG(2²,1)
Sur chaque ligne et chaque colonne, on compte 5 X (donc, 5 symboles par cartes et 5 cartes par symboles)

On pourrait faire le même travail pour F8 et F9, mais après avoir fait celui de F4, je n'ai plus le courage...
La méthode des équations de droites n'est pas la seule façon de construire des plan projectifs finis. En procédant autrement, on peut tomber sur des plans fondamentalement différents. Il existe ainsi des plans projectifs finis d'ordre 9 différents de celui construit à partir de F9, mais les trois plans en question ne seront plus arguésiens (espace dans lequel le théorème de Desargues, que j'avais évoqué ici, n'est plus vrai).

Et puis, il y a les autres valeurs, celles qui ne sont pas des puissances de nombres premiers, comme 6, 10 et 12. Pour ces valeurs là, il n'y a pas de règle, mais la seule chose qui est sûre, c'est que la méthode des équations de droites ne fonctionnera pas, puisqu'il n'existe pas de corps fini ayant ce nombre d'éléments.

Pour q=6, le problème n'a aucune solution, ce qui a été démontré en 1901 par Gaston Terry, quand il a prouvé que le problème des 36 officiers d'Euler (comment placer 36 officiers de 6 régiments différents et de 6 grades différents dans une grille 6x6 sans qu'une ligne ou une colonne compte deux fois des officiers de même régiment ou de même grade) était insoluble.

Pour q=10, Clement Lam a montré qu'un plan projectif fini de cet ordre ne peut pas exister, en calculant l'ensemble des possibilités.

Pour q=12, on n'en sait rien. L'existence d'un Dobble à 13 symboles par cartes et à 157 cartes est donc encore aujourd'hui un problème ouvert. A vous de chercher ! Pour les valeurs de q non premières plus grandes (15, 18, 20, 42, ...), le problème est lui aussi toujours ouvert.

Bref, le Dobble à est mon avis la seule application des plans projectifs finis avec des dessins de bonhomme de neige et de fromages.

Resumay
Récapitulatif des différents Dobble existants


Sources :
Dobble et la géométrie finie, sur Images des Maths 

Posté par El Jj à 10:00 - Commentaires [11] - Permalien [#]
Tags : , , ,


08 juin 2014

L'énigme la plus difficile de TOUS LES TEMPS !!!!

xkcd-246-casse-tete-labyrinthe

On connaît tous l'énigme des deux portes :

Dans un labyrinthe, deux gardes protègent deux portes. L'une des deux portes mène à la liberté, l'autre à une mort certaine. L'un des deux gardes ment systématiquement, tandis que l'autre dit toujours la vérité, mais vous ne savez pas qui est qui. Pour déterminer le chemin de la liberté, vous n'avez le droit qu'à une seule question à l'un des deux gardes. Quelle question poser ?

Cette énigme, sous sa forme actuelle, a été popularisée par le film Labyrinthe (1986) de Jim Henson, avec David Bowie. Mais les problèmes de logique du style "l'un ment, l'autre dit la vérité" viennent essentiellement de l'esprit tordu du génial Raymond Smullyan, où il pose les bases en 1978 dans son livre "Quel est le titre de ce livre ?" (à feuilleter absolument !).

Pour déterminer le chemin vers la liberté, il suffit de poser à l'un des deux gardes la question :

Q : Si je demande à l'autre garde le chemin de la liberté, quelle porte m'indiquera-t-il ?

Puisque les deux gardes sont impliqués dans cette question, la réponse sera forcément un mensonge. Il suffit donc de choisir la porte qui n'a pas été indiquée par le garde pour garantir son accès à la liberté. Des questions alternatives sont possibles, notamment la suivante, qui a le mérite de ne pas faire intervenir les deux gardes dans l'histoire :

Q' : Si je vous demandais quel est le chemin de la liberté, quelle porte m'indiqueriez-vous ?

Si on pose la question "quel est le chemin de la liberté ?" au garde menteur, il indiquerait la porte de la mort. Sachant cela, il répondra donc à Q' le contraire, à savoir, la porte de la liberté. Quel que soit le garde à qui cette question est posée, la réponse que l'on obtiendra indiquera donc forcément le bon chemin (il faut admettre que les gardes raisonnent en parfaits logiciens, ce qu'il est préférable de vérifier avant de risquer sa vie en posant des questions tordues).

Ca, c'est l'énigme classique. Mais je suis tombé cette semaine sur une version alternative de l'énigme, sobrement intitulée :

L'énigme de logique la plus difficile de tous les temps
Cette énigme, attribuée à Raymond Smullyan a particulièrement été étudiée par le philosophe et logicien George Boolos. C'est dans un article du Harvard Review of Philosophy qu'il publie en 1996 l'énigme :

Trois dieux A, B et C se nomment Vérité, Mensonge et Hasard (vous ne savez pas quel dieu est qui). Lorsqu'on leur pose une question, Vérité répond toujours la vérité, Mensonge répond toujours le contraire de la vérité, et Hasard répond toujours au hasard entre la vérité et son contraire. Votre tâche est de déterminer l'identité de ces trois dieux, à l'aide de trois questions fermées.
Les dieux comprennent parfaitement le français et la logique, mais ils ne répondront que dans leur propre langue qui ne possèdent que deux mots, « da » et « ja ». Ces mots signifient « oui » et « non », mais vous ne savez pas lequel se rapporte à quoi (!).

Quelques remarques tout de même : on peut poser plusieurs questions à un même dieu (mais pas plus de 3 en tout) ; la deuxième question que l'on posera peut dépendre de la réponse « da » / « ja » obtenue à la première réponse (idem pour la troisième) ; quand on pose une question à Hasard, il jette une pièce dans sa tête, et répondra la vérité s'il obtient pile, et le contraire de la vérité sinon.

Oui, cette énigme est particulièrement horrible. Si vous ne voulez pas vous faire spoiler la solution, arrêter tout de suite la lecture de cet article, et revenez dans quelques jours. Pour les autres, voici les questions à poser, selon l'article de Boolos :

Q1, à poser à A :

Est-ce que (« da » signifie « oui » si et seulement si vous êtes Vérité) si et seulement si B est Hasard ?

Q2 à poser à B si la réponse était « ja » ou à C si la réponse était « da » :

Est-ce que « da » signifie « oui » si et seulement si Rome est en Italie ?

Q3, à poser au même dieu que lors de question 2 :

Est-ce que « da » signifie « oui » si et seulement si A est Hasard ?

Si la réponse à Q2 est « da », le dieu ayant répondu à cette question est Vérité, sinon, c'est Mensonge.
Si Vérité a répondu à Q3, la réponse « da » signifie que A est Hasard, et la réponse « ja » signifie que A est Mensonge ;
Si Mensonge a répondu à Q3, la réponse « da » signifie que A est Vérité, et la réponse « ja » signifie que A est Hasard.
On connaît maintenant l'identité des trois dieux !

Oui, mais... pourquoi ?!
Rappelons que, en logique, le "si et seulement si" (ssi) désigne l'équivalence logique : l'expression "P ssi Q" est vraie lorsque les expressions P et Q sont soit toutes les deux vraies, soit toutes les deux fausses. Ainsi, l'expression "(P ssi Q) ssi R" sera vraie dans deux cas : lorsque P, Q et R sont toutes les trois vraies, ou lorsque exactement une seule des trois propositions est vraie.
On peut donc reformuler plus clairement Q1 par :

Est-ce qu'un nombre impair des affirmations suivantes sont vraies : « da » signifie « oui », vous êtes Vérité, B est Hasard ?

Cette question n'a que un seul but : déterminer un des deux dieux qui n'est pas Hasard, afin d'être certain de ne pas s'adresser à lui lors des questions Q2 et Q3. 
Si A est Hasard, alors quelle que soit sa réponse, on sera amené à parler à B ou C lors des questions suivantes.
Dans le cas où A est soit Vérité, soit Mensonge, on peut observer 8 éventualités :

TableDesVerités

Et finalement, que l'on s'adresse à Vérité ou à Mensonge, on obtiendra les mêmes réponses :

TableDesVeritésEtMensonges

Un « da » signifie alors que B est Hasard, on s'adressera donc à C lors des questions suivantes ; un « ja » nous amenera à parler à B, qui n'est pas Hasard.

La question 2 (Est-ce que « da » signifie « oui » si et seulement si Rome est en Italie ?) nous permet de connaître l'identité du Dieu à qui l'on s'adresse.
Puisque Rome est en Italie, la réponse est « oui » si « da » signifie « oui », et est « non » sinon. Vérité répondra donc « oui » (« da ») dans le premier cas, et « non » (« da ») dans l'autre cas : au final, Vérité répondra « da » quel que soit la sens de « da ». Mensonge, quant à lui, répondra toujours « ja ». Le cas où l'on s'adresserait à Hasard ayant été exclu lors de la question 1, cette deuxième question permet d'identifier le dieu à qui l'on parle.
Remarquons que l'ajout « Rome est en Italie » n'a aucun intérêt, et qu'on peut se contenter de demander "Est-ce que « da » signifie « oui »".

Enfin, la question 3 (Est-ce que « da » signifie « oui » si et seulement si A est Hasard ?) nous permet de statuer sur la réelle identité de A, et donc, des trois dieux. En admettant que l'on s'adresse à Vérité, une réponse « da » signifie que A est bien Hasard, et « ja » signifie que A n'est pas Hasard (et que donc, c'est Mensonge). Si on s'adresse à Mensonge, on a les interprétations contraires. 

Variantes
Cette énigme de logique la plus difficile de tous les temps a longuement été analysée, si bien que plusieurs variantes de réponses ont été proposées.

Une première variante, observée en 2001 par Tim Roberts, est d'utiliser des questions s'inspirant de l'énigme des deux portes, c'est à dire, des questions de la forme :

Si je vous demandais Q, me répondriez-vous « da » ?

Si la réponse logique à la question embarquée Q est « oui », la réponse sera « da », que l'on s'adresse à Vérité ou à Mensonge ; sinon, la réponse sera « ja ». Ce "lemme de la question embarquée" a pour conséquence de simplifier grandement l'énigme, au point que cela revient à ignorer le fait que les dieux puisse mentir et qu'ils répondent dans une langue inconnue.
On peut alors reformuler les questions :

  • Q1' (à A) : Si je vous demandais « B est-il Hasard » , me répondriez-vous « da » ?
  • Q2' (à B « ja » à Q1', à C sinon) : Si je vous demandais « Êtes-vous Vérité » , me répondriez-vous « da » ?
  • Q3' (au même qu'à Q2') : Si je vous demandais « A est-il Hasard » , me répondriez-vous « da » ?

Une autre variante, proposée par Brian & Landon Rabern, est de confronter les dieux au paradoxe logique du menteur (« Je mens »). Imaginons que l'on pose à A la question Q1'' suivante : 

Si je vous demandais Q*, me répondriez-vous « da » ?
où Q* est la question :
« Est-ce que : [(Vous allez répondre « ja » à la question Q1'') et (B est Vérité)] ou (B est Mensonge) »

Trois réponses peuvent arriver :

  • Si A répond « da », c'est que la réponse à Q* est oui. Donc soit B est Mensonge (ce qui est envisageable), soit B est vérité et A a répondu « ja » (ce qui serait paradoxal, donc impossible). Donc B est Mensonge.
  • Si A répond « ja », c'est que la réponse à Q* est non. B est donc ni Mensonge, ni Vérité (car « Vous allez répondre « ja » la question Q1'' » est vrai). Donc B est Hasard.
  • Si B est Vérité, alors la question Q* se ramène à la question paradoxale «Vous allez répondre « ja » à la question Q1''». La tête de A explose, et on en déduit que B est bien vérité.

En une seule question, on a pu déterminer l'identité de B. Un seconde question permet alors simplement de clarifier l'identité de A et C. Il reste alors une question en rab, que l'on pourra poser à Vérité afin d'avoir une réponse définitive à « P=NP ? », « l'hypothèse de Riemann est-elle indécidable ? » ou tout autre question existentielle.


Sources :
Georges Boolos, The Hardest Logic Puzzle Ever
Brian Rabern & Landon Rabern, A simple solution to the hardest logic puzzle ever

Posté par El Jj à 10:00 - Commentaires [7] - Permalien [#]
Tags : , , ,

25 mai 2014

DRH Simulator

Il y a le problème des cartes Panini : à quel moment faut-il arrêter d'acheter au hasard ses cartes à collectionner et les acheter à l'unité, quitte à les payer plus cher ? J'en avais parlé dans cet article.
Il y a le problème du parking avant un concert : faut-il se garer dès la première place disponible et avoir à marcher jusqu'à la salle, ou bien faut-il tenter de se rapprocher au maximum de l'entrée, quitte à perdre du temps en ayant à faire demi-tour ?
Il y a aussi le problème de la meilleure station-service : faut-il s'arrêter prendre de l'essence à la grande surface avant de partir, ou bien s'arrêter à l'une des stations sur le trajet, en espérant y trouver de meilleurs prix ?
On trouve des questions équivalentes dès qu'il s'agit d'investir en bourse ou de poursuivre l'exploitation d'une machine usée plutôt que de la remplacer... Bref, dans une situation qui fait la part belle au hasard, à quel moment faut-il arrêter de tenter le diable ? Un tel problème est un problème d'arrêt optimal, et c'est du plus célèbre d'entre eux que je souhaite parler aujourd'hui : le problème du gogol, aka problème du mariage, aka problème de la dot, aka problème du casting aka...

Queuing
Qui sera le meilleur secrétaire ?...

Le problème des secrétaires
En bon chef d'entreprise que vous êtes, vous avez décidé d'engager un (et un seul) nouveau secrétaire. Vous organisez donc une série d'entretiens, où n candidats se présentent (vous connaissez à l'avance ce nombre n de postulants). Les candidats seront interviewés tour à tour, l'ordre étant aléatoire. A l'issue de chaque entrevue, vous n'avez que deux possibilités : le candidat est embauché ou bien rejeté. S'il est embauché, vous ne poursuivez pas les entretiens ; si il est rejeté, vous n'aurez plus l'occasion de le revoir. Attention : si vous rejetez tous les candidats, vous devrez impérativement garder le dernier (La France est en crise, il faut réduire le chômage, quitte à embaucher n'importe qui). La question est donc : à quel moment est-il préférable d'arrêter les entretiens ? 

Pour faire le meilleur choix, vous ne pouvez vous baser que sur un seul critère : le candidat est-il oui ou non meilleur que tous ses prédécesseurs (on suppose ici que l'on peut classer l'ensemble des postulants du moins bon au meilleur, sans ex aequo possibles). Mais comment peut-on faire pour maximiser les chances de tomber sur LE meilleur des candidats ?

La modélisation du problème est critiquable : un bon responsable des ressources humaines se gardera toujours la possibilité de rappeler un candidat après interview ("on vous rappellera"). De plus, il s'agit rarement de trouver le meilleur candidat, mais celui qui est qualifié pour le poste, quitte à ne garder au final aucun candidat. De plus, on peut imaginer que tous les candidats ne sont pas comparables deux à deux. Le problème des secrétaires connaît de très nombreuses variantes prenant ou non en compte ces objections, ce qui fait que le problèmes d'arrêt optimal forment une catégorie de problèmes particulièrement étudiés.

Cas n = 4
Prenons un premier exemple, avec n = 4 candidats : A (d'un niveau assez bon), B (d'un bon niveau), C (niveau très bon) et D (niveau excellent). L'objectif est donc de choisir D.
L'ordre étant aléatoire, on dénombre 24 possibilités : ABCD, ABDC, ACBD, ACDB, ADBC, ADCB, BACD, BADC, BCAD, BCDA, BDAC, BDCA, CABD, CADB, CBAD, CBDA, CDAB, CDBA, DABC, DACB, DBAC, DBCA, DCAB et DCBA.

Stratégie 0 : Une première stratégie envisageable est de choisir le premier candidat, quoi qu'il arrive. On obtient alors une stratégie qui fonctionne avec une chance sur 4 (25%).

Stratégie 1 : Une autre stratégie envisageable est de s'entrenir avec le premier candidat, sans le garder. Ensuite, on gardera le premier des candidats à se présenter qui sera meilleur que le candidat n°1. Plusieurs cas sont envisageables :
- le premier candidat est D : il sera éliminé, tant pis.
- le premier candidat est C : le seul candidat meilleur que C est D, qui sera donc forcément choisi quand il se présentera -> 6 possibilités sur 24
- le premier candidat est B. Sous cette condition, on prendra le premier des candidats C ou D à se présenter -> 3 possibilités sur 24
- le premier candidat est A. Sous cette condition, le candidat n°2 sera choisi, soit une chance sur trois de tomber sur D -> 2 possibilités sur 24.
Au final, cette stratégie donne 11 chances sur 24 (46% de chances) de tomber sur D, le meilleur candidat. On peut aussi vérifier que l'on choisira C avec une probabilité de 7/24, B avec une probabilité de 4/24 et A avec une probabilité de 2/24.

Stratégie 2 : Une autre stratégie envisageable est de s'entrenir avec les deux premiers candidats sans les garder, puis de choisir le candidat n°3 s'il est meilleur que les deux premier, et le n°4 sinon.
Dans ce cas, D sera choisi systématiquement si les premiers candidats sont AC, BC, CA ou CB. Si les premiers candidats sont AB ou BA, D sera choisi dans la moitié des cas. Sinon, c'est que D est parmi les deux premiers candidats, et donc éliminé. On en déduit alors que D sera choisi avec une probabilité de 10/24 (soit 42%). Pour C, la probabilité est de 6/24, pour B et A, elle est de 4/24.

On peut oublier la stratégie 3 consistant à ne pas sélectionner les trois premiers candidats pour ne garder que le dernier, qui fait retomber la probabilité d'embaucher D à 1 chance sur 4.

En appelant "stratégie k" la stratégie consistant à faire passer les k premiers candidats sans les garder, puis sélectionner le premier des candidats meilleur que ces k premiers, on vient de vérifier que dans le cas n = 4, la stratégie optimale est la stratégie 1. Le meilleur des candidats sera sélectionné avec une probabilité d'environ 46%.

Cas n = 5
On peut procéder à la même analyse pour le cas n = 5, en envisageant les 120 ordres possibles pour 5 candidats. Les probabilités d'obtenir le meilleur candidat, suivant les différentes stratégies envisageables, sont alors :

Stratégie 0 : p = 20 %
Stratégie 1 : p = 41.7 %
Stratégie 2 : p = 43,3 %
Stratégie 3 : p = 35 %
Stratégie 4 : p = 20 %

Bref, la meilleure stratégie consiste ici à laisser passer les deux premiers candidats.

Mais pour les valeurs plus grande ? Il existe forcément une stratégie meilleure que les autres, mais laquelle ? Et la solution est plutôt simple : même si vous devez auditionner 100 000 secrétaires, il existe toujours une stratégie permettant de trouver le meilleur avec une probabilité supérieure à 36% ! Cette stratégie, c'est la stratégie n/e : il faut laisser passer le premier tiers (36.79% des candidats, pour être un peu plus précis) des candidats, puis prendre le premier des candidats meilleurs. Et on va le prouver !

Le jeu du gogol
Le problème des secrétaires trouve ses origines dans la rubrique Mathematical Games de Martin Gardner dans le numéro de février 1960 du Scientific American. Le problème y est présenté sous la forme du "jeu du gogol" : un joueur écrit sur des feuilles des nombres quelconques, arbitrairement grands ou petits (d'où le nom du jeu : on peut y écrire des nombres aussi grand qu'un gogol, ie, 10100), le but étant pour l'autre joueur de les retourner successivement, mais de s'arrêter sur le plus grand d'entre eux. La question de la stratégie optimale à suivre pour le deuxième joueur revient à résoudre le problème des secrétaires.  La solution arrivera dans la même rubrique du magazine, le mois suivant. On retrouvera plus tard le même problème sous le nom de "problème du mariage" (un Don Juan fait défiler des candidate pour son mariage, jusqu'à faire un choix), ou sous d'autres appellations tout aussi sexistes (problème de la dot, problème du concours de beauté, ...).

Les origines du problème semble cependant remonter au XVIIe siècle, après que l'astronome allemand Johannes Kepler a perdu sa première femme à cause du choléra. Bien décidé à en trouver une nouvelle, il a cherché à ne pas faire la même erreur que pour son premier mariage, qui lui avait été arrangé. Pour ce faire, il a consacré deux ans de sa vie à chercher la femme idéale, et 11 ont répondu à l'appel. De nombreuses lettres de Kepler relatent son processus de décision pas tout à fait au point. Le problème se termine bien : il finira par choisir la cinquième, ils se marièrent et eurent beaucoup (7) d'enfants.
En fait, Kepler n'a pas réellement inventé le problème des secrétaires (la plupart des hypothèses du problème ne sont pas respectées, puisqu'il s'est autorisé à revenir sur ses choix), mais il a quand même énoncé le premier problème d'arrêt optimal, en inventant au passage le principe du speed-dating (qui dure deux ans).

Cas général
Revenons au problème général, avec n secrétaires. Les informations que l'on a à notre disposition limitent pas mal les différentes stratégies possibles. En fait, les seules stratégies envisageables sont les stratégie k (k ∈ [0 ; n-1]) : on interroge les k premiers candidats pour se donner une idée de leur niveau en les rejetant systématiquement, puis, parmi les n-k candidats suivants, on choisit le premier à être meilleur que les k premiers. Reste à savoir quelle est, en fonction de n, la valeur de k idéale.

Notons j la position de ce mystérieux candidat meilleur que les autres. La probabilité que j soit une valeur fixée à l'avance est de 1/n.
Si j ≤ k, alors le candidat n°j sera ignoré, et donc, non choisi.
Si j = k+1, c'est que le meilleur candidat arrive pile au bon moment : il est choisi.
Si j ≥ k+2, le candidat n°j sera sélectionné seulement s'il n'y a pas de candidat opportuniste (meilleur que les k premiers) entre la position k+1 et j-1. Ceci n'arrivera qu'avec une probabilité de k/(j-1) : la probabilité que le meilleur des (j-1) premiers soit dans les k premiers (formellement, c'est la probabilité de choisir le j-ième candidat sachant que c'est le meilleur).

La probabilité que la stratégie k permette de trouver le meilleur candidat est donc :

ProbaSecretaire1

En simplifiant :

ProbaSecretaire2

Pour des petites valeurs de n, on peut calculer ces probabilités pour toutes les valeurs de k afin de déterminer la stratégie optimale :

Pour n = 3, P est maximal pour k = 1 (P = 0.5)
Pour n = 4, P est maximal pour k = 1 (P = 0.458)
Pour n = 5, P est maximal pour k = 2 (P = 0.433)
Pour n = 6, P est maximal pour k = 2 (P = 0.428)
Pour n = 7, P est maximal pour k = 2 (P = 0.414)
Pour n = 8, P est maximal pour k = 3 (P = 0.410)
Pour n = 9, P est maximal pour k = 3 (P = 0.406)
Pour n = 10, P est maximal pour k = 3 (P = 0.398)
En poursuivant les calculs, on peut se convaincre que n/k tend vers e.

Pour des valeurs de n plus élevées, on va plutôt déterminer une valeur approchée de Pn,k. Un peu de calcul intégral permet de voir que

ProbaSecretaire3

La probabilité de succès de la stratégie k est donc environ égale à Pn,k = (k/n) ln(n/k). Il n'y a plus qu'à chercher pour quelle valeur de k cette probabilité est maximale. 
Posons x = (k/n). La fonction f(x) = x ln(1/x) est maximale (si si, je vous l'assure) lorsque x = 1/e ≈ 0.368, ce qui signifie que la probabilité est maximale quand le rapport entre k et n vaut approximativement 36.8 %.
La meilleure stratégie, pour un nombre de candidat n, est donc la stratégie n/e. Cette stratégie offre une probabilité de succès valant f(1/e) = 1/e ≈ 0.368.

Il y a des tas d'autres problèmes d'arrêt optimal, comme celui du jeu d'Arthur "à prendre ou à laisser". Puisqu'il paraît que le jeu revient à la télé à la rentrée, ça me fera une bonne excuse pour faire d'autres articles sur le sujet !


Sources :
Who solved the secretary problem, Thomas S. Ferguson

Illustration : Queue

Posté par El Jj à 10:00 - Commentaires [5] - Permalien [#]
Tags : , ,

13 avril 2014

La dualité. Mesdames et messieurs.

Il n'y a pas que les physiciens quantiques et les philosophes qui ont le monopole de la dualité. Les mathématiciens ont aussi leur mot à dire, et ils ne se sont pas privés : dual d'un polyèdre, dual d'un graphe, dual d'un espace vectoriel, dualité de Poincaré...

Ma dualité préférée est celle de la géométrie projective, le domaine de la géométrie qui étudie les notions de perspectives. Cette dualité permet sans effort de fabriquer plein de nouveaux théorèmes de géométrie. Mais pour cela, il faut comprendre dans ses très grandes lignes la géométrie projective, en admettant ses deux axiomes suivants :

  1. Par deux points distincts passe toujours une droite (et une seule).
  2. Deux droites distinctes se coupent toujours en un point (et un seul).

Le premier axiome, on le retrouve dans notre bonne vieille géométrie euclidienne, il ne va pas nous étonner. Par contre, le deuxième axiome a l'air manifestement faux, puisque deux droites parallèles ne se coupent a priori en aucun point. Mais ça, c'était avant : en géométrie projective, des droites parallèles se coupent quand même, mais en un point "à l'infini", sur la ligne d'horizon.

En fait, ces deux axiomes peuvent tout les deux se résumer sous la forme :

  • Deux machins distincts se schtroumpfent toujours en un truc

Ces machins-trucs que sont les droites et les points sont en quelque sorte en dualité : en les inversant dans un axiome, on obtient l'autre.

Mais on peut faire encore plus fort. Partons de l'idée qu'un plan, c'est juste un ensemble de droites et des points. Alors on peut imaginer un nouvel espace où l'on appellerait "points" les droites du premier espace, et inversement (on se moque de savoir à quoi ressemble ce plan, ce n'est pas la question qui nous intéresse). Ce nouveau plan, on peut l'appeller "dual" du premier.
Mais ce plan dual vérifie toujours les deux axiomes de départ : il y a de bonnes raisons à le considérer comme un plan projectif comme les autres...

En fait, on peut mathématiser proprement la construction de ce plan projectif dual ; en le faisant, on s'aperçoit qu'il ressemble étrangement au plan de départ. Du coup, puisque ces objets passent au dual, on peut démontrer que les propriétés qui les définissent aussi.

Par exemple :

  • Un point P du plan devient une droite (p) du dual ; une droite (d) du plan devient un point D du dual
  • Dans le plan, deux droites (d) et (e) se coupent en un point P
    => dans le dual, deux points D et E forment une droite (p)
  • Dans le plan, trois points alignés P, Q et R forment une droite (d)
    => dans le dual, trois droites concourantes (p), (q) et (r) forment un point D

Plan_et_son_dual
Une configuration du plan : trois droites (d), (e) et (f) concourantes en P, et trois points P, Q et R alignés sur (d).
La même configuration dans le dual : trois points D, E et F alignés sur (p), et trois droites (p), (q) et (r) concourantes en D.

Du coup, si un théorème de géométrie ne fait appel qu'à des notions d'alignements de points ou de concourances de droites, on peut les dualiser afin d'obtenir un nouveau théorème. C'est l'outil parfait pour doubler le nombre de théorèmes existants ! Place aux exemples !

Le théorème de Pappus
Parmi les théorèmes de géométrie injustement méconnus, il y a le théorème de Pappus (que l'on doit à Pappus d'Alexandrie) :

Théorème de Pappus :
Soit A, B et C trois points distincts alignés sur une droite (d),
soit A', B' et C' trois points distincts alignés sur une droite (d'), 
Notons (p)=(AB'), (p')=(A'B), (q)=(AC'), (q')=(A'C), (r)=(BC') et (r')=(B'C)
Alors, les points E = (p')∩(p'), F = (q)∩(q') et G = (r)∩(r') sont alignés

Pappus

Ce théorème peut se dualiser, en inversant "droite" et "point", et en inversant "concourant" et "alignés". On obtient alors un tout nouveau théorème :

Théorème dual de Pappus : 
Soit (a), (b) et (c) trois droites distinctes concourantes en un point D, 
Soit (a'), (b') et (c') trois droites distinctes concourantes en un point D', 
Notons P=(a)∩(b'), P'=(a')∩(b), Q=(a)∩(c'), Q'=(a')∩(c)R=(b)∩(c'), R'=(b')∩(c)

Alors, les droites (E) = (PP'), F=(QQ') et G=(RR') sont concourantes

 Pappus_dual

Ce théorème est loin d'être aussi élégant que son dual, mais il a le mérite d'exister. (Bon, en réalité, il décrit exactement la même configuration que dans le théorème de Pappus !...)

Le théorème de Desargues
Le théorème phare de la géométrie projective, c'est le théorème de Desargues, conséquence de celui de Pappus. On le doit au français Girard Desargues, que l'on peut considérer comme le père de la géométrie projective. Il indique :

Théorème de Desargues (*)
Soit deux triangles (non aplatis) ABC et A'B'C'
Si les droites (AA'), (BB') et (CC') sont concourantes
alors les points P = (AB)∩(A'B'), Q = (AC)∩(A'C') et R = (BC)∩(B'C') sont alignés

Desargues

Encore une fois, le passage au dual permet de fabriquer un nouveau théorème. Enfin, presque nouveau, puisque ce n'est autre que la réciproque du théorème précédent. La seule différence est la surcomplexification inutile de son énoncé...

Réciproque du théorème de Desargues
Soit deux triangles (non aplatis) de côtés (a), (b) et (c), et de côtés (a'), (b') et (c') 

Si les points (a)∩(a'), (b)∩(b') et (c)∩(c') sont alignés
alors les droites (p) = (ab;a'b'), (q) = (ac;a'c') et (r) = (bc;b'c') sont concourantes
(en notant (ab;a'b') la droite passant par ab=(a)∩(b) et a'b'=(a')∩(b'))
Desargues_dual

 

Le théorème de Pascal
Un autre théorème qui passe parfaitement au dual est celui de l'hexagramme mystique de Pascal, qui parle de coniques (ellipses, hyperboles, paraboles, ...) :

Théorème de Pascal
Soit A, B, C, A', B' et C' six points distincts sur une conique
Notons (p)=(AB'), (p')=(A'B), (q)=(AC'), (q')=(A'C), (r)=(BC') et (r')=(B'C)
Alors, les points E = (p)∩(p'), F = (q)∩(q') et G = (r)∩(r') sont alignés

Pascal

On peut voir que ce théorème est une généralisation de celui du théorème de Pappus, puisqu'un couple de droites n'est qu'un cas particulier de conique dégénéré.

L'hexagramme de Pascal peut également être dualisé, en ajoutant deux nouvelles correspondances entre le plan et son dual :

  • Une conique dans le plan reste une conique dans le dual
  • Un point sur une conique dans le plan devient une droite tangente à une conique dans le dual

Théorème de Brianchon
Soit (a), (b), (c), (a'), (b') et (c') six droites distinctes tangente à une conique
Notons P=(a)∩(b'), P'=(a')∩(b), Q=(a)∩(c'), Q'=(a')∩(c), R=(b)∩(c'), R'=(b')∩(c)

Alors, les droites (E) = (PP'), F=(QQ') et G=(RR') sont concourantes


Pascal_dual

Le théorème de Pascal est vrai quel que soit l'ordre des points A, B, C, A', B', C' que l'on considère. La droite orange obtenue dépend donc de l'ordre des points. Puisqu'il y a 60 façons de dessiner un hexagone à partir de 6 points, on peut obtenir une famille de 60 droites, les droites de Pascal. Cet énoncé passe au dual, ce qui entraîne l'existence de 60 points particuliers, les points de Kirkman (points de concourance des droites de Pascal).

Droites_de_Pascal
(Une partie de) Les 60 droites de Pascal et les 60 points de Kirman
Oui, c'est n'importe quoi.


(*) Note de bas de page : à première vue, le théorème de Desargues n'est qu'un amas sans fond ni forme de points et de cercles. Pour le visualiser (et le mémoriser), on peut penser à cette figure : il faut imaginer que ABC et A'B'C' sont des coupes transversales parallèles d'une même pyramide. Ces coupes étant parallèles, les côtés se prolongent et se coupent deux à deux sur la même ligne d'horizon : ces points de concours sont donc alignés.


Sources :
Wikipedia, essentiellement
Pascal Lines, sur MathWorld

Posté par El Jj à 10:00 - Commentaires [6] - Permalien [#]
Tags : , , , ,

06 avril 2014

Mokshû Patamû

Après une partie contre des banquiers véreux qui n'ont jamais voulu échanger votre Faubourg Saint-Honoré contre leur Boulevard Malesherbes, vous avez choisi de renoncer définitivement à ouvrir cette boîte de ce jeu de l'enfer qu'est le Monopoly. Mais à quoi jouer avec beau-papa en ce dimanche après-midi ? Une partie de Scrabble ? des colons de Catanes ? des Aventuriers du Rail ? Non ! Revenons aux bases, et ouvrons la boîte pleine de poussière qui renferme un vénérable plateau de Serpents et échelles !

Bon, finalement, vous avez débuté le jeu, et vous n'avez maintenant plus qu'une seule envie : que cela se termine ! Mais au fait, combien de temps dure en moyenne une partie de Serpents et échelles ?!

320px-Snakes_and_ladders2

Pour les quelques-uns qui n'ont jamais perdu des heures à tomber en boucle sur la même gueule de serpent, voici ce qu'il faut savoir sur ce jeu :

  • Le plateau de jeu est composé de 100 cases, numérotées de 1 à 100.
  • Les joueurs, chacun leur tour, lancent le dé, puis déplacent leur pion du nombre de cases indiqué.
  • Des serpents et des échelles sont disséminés sur le plateau de jeu. Lorsqu'on arrive au pied d'une échelle, on la monte ; inversement, lorsque l'on tombe sur une tête de serpent, on descend jusqu'à sa queue.
  • Le premier joueur à atteindre (ou dépasser) la 100e case est déclaré vainqueur, et félicité pour sa chance au jeu.
  • A l'origine, ce jeu est une métaphore indoue du chemin spirituel pour atteindre le Nirvana.

De nombreuses variantes de plateaux de jeu existent, je vais me baser sur la version Hasbro, dont le plateau comporte 9 échelles et 7 serpents, et qui ressemble à ceci :

Plateau

Au nom de la loi de X
En détaillant un peu le plateau, on peut voir que la centième case peut être atteinte en seulement 7 lancés de dés, en empruntant 3 échelles (l'échelle 1 -> 38, la 51-> 67 et la 71 -> 91). Cependant, il n'y a pas de nombre maximum de coups permettant d'atteindre la dernière case. Heureusement, ce cas est presque impossible.

Finalement, quel est le temps moyen permettant d'atteindre cette centième case ? Les chaînes de Markov sont là pour nous aider à appréhender la situation. Pour comprendre, observons ce qu'il se passe lancé par lancé.

Au début du jeu, les pions sont en dehors du plateau. Au premier lancé de dé, 6 cases sont atteignables (38 (si on obtient 1 au dé, grâce à l'échelle), 2, 3, 14 (4 au dé), 5 ou 6). La probabilité d'atteindre chacune de ces cases après le premier lancé de dé est donc de 1/6 (≈0.17).

proba_ees_lance_1

Pour ce qui est du deuxième lancé de dé, il faut envisager les 6 cas précédents :

  • depuis la case 38, on peut atteindre 39, 40, 41, 42, 43, 44
  • depuis la case 2, on peut atteindre 3, 14, 5, 6, 7, 8
  • depuis la case 3, on peut atteindre 14, 5, 6, 7, 8, 31
  • depuis la case 14, on peut atteindre 15, 6, 17, 18, 19, 20
  • depuis la case 5, on peut atteindre 6, 7, 8, 31, 10, 11
  • depuis la case 6, on peut atteindre 7, 8, 31, 10, 11, 12

Puisqu'il y a 36 façons de lancer deux fois le dé, chacune de ces cases a pour probabilité 1/36 d'être atteinte par le chemin indiqué. On peut alors remarquer, par exemple, que :

  • il n'y a qu'une seule façon d'atteindre la case 42 en deux lancés de dé : sa probabilité est de 1/36 (≈0.03).
  • il y a 4 façons d'atteindre la case 6 en deux lancés de dé : la probabilité de cette case est donc de 4/36 (≈0.11).

proba_ees_lance_2

On pourrait suivre le même raisonnement pour le troisième lancé de dé, mais le décrire entièrement serait trop long. Heureusement, les matrices vont venir prendre le relai. Pour cela, on a besoin de la matrice de transition M du plateau, qui donne la probabilité d'atteindre une case sachant que l'on est sur une autre case.

Pour être plus précis, le coefficient de la ligne I et de la colonne J correspond à la probabilité d'atteindre la J-ième case sachant que l'on se trouve sur la I-ème. A titre d'exemple, le coefficient ligne 2 colonne 3 est 1/6 car il y a une chance sur 6 d'atteindre la case 3 en partant de la case 2.

matrice_ligne23_echelles_et_serpents

La matrice finale M contient donc une très grand nombre de 0, beaucoup de 1/6 et quelques valeurs un peu plus grandes (le coefficient ligne 52 colonne 53 vaut 2/6, car il y a deux façons d'atteindre la case 53 depuis la 52). Graphiquement, la matrice ressemble à ceci.

matrice_echelles_et_serpents

Cette matrice nous permet de calculer la probabilité de chacune des cases pour un nombre de lancé choisi, en utilisant le fait que

U(n+1) = U(n) × M
où U(n) la matrice-ligne qui donne la probabilité de chacune des 100 cases lors du n-ième lancé de dé.

On peut notemment calculer la distribution des probabilités pour 6 ou 7 lancés, ce qui confirme la remarque initiale : il est théoriquement possible de gagner en 7 lancés de dés, mais la probabilité est excessivement faible (0.2 %). Après 7 lancés, on se retrouve plus facilement en case 26...

proba_ees_lance_6_7

Le temps d'en finir
Tout ceci ne nous dit pas encore combien de temps on doit se farcir les serpents et les échelles pour en finir avec le jeu. Il ne reste en fait plus qu'à chercher la probabilités d'atteindre la 100e en exactement n lancés de dés, pour toutes les valeurs de n. Aussitôt dit, aussitôt fait :

proba_case100

Ce graphique (et quelques calculs autour des données) nous apprend des choses essentielles :

  • Le plus probable est d'atteindre la centième case en 20 lancés de dés
  • En moyenne, il faut 36 lancés de dés pour gagner
  • Il y a 50% de chances de finir en moins de 29 mouvements
  • Il y a 98% de chances d'en finir en moins de 100 mouvements

Oui, mais...
D'aucun me diront que, dans les règles officielles du jeu, il faut atteindre exactement la case 100, sinon la règle "tu dépasses, tu recules" s'applique. Ca change tout !

Qu'il en soit ainsi, je modifie la matrice tout de suite :

matrice_echelles_et_serpents_2

Ce qui nous donne ce chouette graphique :

proba_case1002

En détaillant en peu les chiffres, on découvre que...

  • Le plus probable est d'atteindre la centième case en 22 lancés de dés (et la probabilité est bien plus faible que dans le cas précédent)
  • En moyenne, il faut 43 lancés de dés pour gagner
  • Il y a 50% de chances de finir en moins de 34 mouvements
  • Il y a 94% de chances d'en finir en moins de 100 mouvements

Mouais... Finalement, cette règle supplémentaire a surtout pour effet de rallonger la traîne de la courbe : le cas le plus probable ne change pas, mais les événements très rares le deviennent un petit peu moins.


 

Sources :
Analysis of Chutes and Ladders, sur DataGenetics

Images :
Snakes_and_ladders
 

Posté par El Jj à 10:00 - Commentaires [5] - Permalien [#]
Tags : , , , ,



30 mars 2014

Made in Sinaï

Le prix Abel 2014 a été annoncé le 26 mars dernier, et l'heureux lauréat est russe ! C'est donc le mathématicien (et un peu physicien) Iakov Sinaï qui décroche cette année le prix Nobel des maths (parce que, non, la médaille Fields n'est pas l'équivalent d'un Nobel, c'est encore plus prestigieux). Il est récompensé pour l'ensemble de son œuvre : des travaux sur les systèmes dynamiques, sur la théorie ergodique et en physique mathématique. Son nom restera surtout associé aux systèmes dynamiques, grâce au billard de Sinaï et à l'entropie de Sinaï-Kolmogorov. A quoi ressemblent ces bêtes là ? Quelques éléments de réponse.

174px-Yakov_G_Sinai_photo
Iakov (Yakov ?!) Sinaï

Le billard de Sinaï
On appelle système dynamique un processus évoluant au cours du temps qui ne fait absolument pas intervenir le hasard (autrement dit, déterministe). L'objet préféré des gens qui étudient les systèmes dynamiques, c'est le billard. Enfin, pas n'importe quel billard : un billard sans trou et qui se joue avec une seule boule (infiniment fine). Une fois lancée, la boule ne s'arrête plus, et suit les loi de la physique lorsqu'elle rebondit sur les parois. En fait, le billard des mathématicien est surtout une façon simple de modéliser le comportement d'un particule d'un gaz.

Dans un tel billard, une fois que l'on connaît la position précise de la balle et sa direction initiale, les lois de la physique nous permettent de prédire avec exactitude la trajectoire qu'elle suivra. Cette trajectoire est donc parfaitement déterministe.

Billard_1
Je lance ma boule selon la direction bleue : elle rebondit, tout est normal.

Si je modifie un peu la position ou la direction initiale de la balle, la trajectoire change. Mais pas tant que ça. En déplaçant la balle et en conservant la même direction, la balle aura une trajectoire parallèle à sa trajectoire initiale ; si c'est la direction que l'on change, la balle déviera de plus en plus de sa trajectoire initiale avec le temps, mais rien de très inquiétant.

Billard_non_chaotique
à gauche, un changement de position initiale
à droite, un changement de direction initiale
De petits changements entraînent de petites déviations

Par contre, quand Sinaï joue au billard, il n'hésite pas à rajouter un gros cylindre en plein milieu de sa table. La physique permet toujours de prédire la trajectoire de la balle, ce système dynamique est toujours parfaitement déterministe.

Billard_Sinaipng
Le véritable "billard de Sinaï" est carré, mais l'idée est la même

La grosse différence d'avec le premier billard, c'est que la trajectoire devient difficile à prévoir lorsque l'on modifie un peu les conditions initiales. En déplaçant, même légèrement, la position de départ de la balle, la trajectoire devient très rapidement complètement différente. Même remarque si l'on modifie un peu sa direction.

Billard_Sinai_chaotique
Avec un petit changement des conditions initiales, la trajectoire change du tout au tout.

Bien que les trajectoires soient complètement prévisible, puisque déterministe, il est en fait impossible de les prévoir sans passer par l'essai. On peut alors qualifier ces trajectoires comme "chaotique" : une petite modification des conditions initiales change très rapidement l'aspect global de la trajectoire. Il existe de très nombreux exemple de systèmes chaotiques, je vous invite plutôt à écouter le dernier épisode de Podcast Science sur le sujet.

Assez paradoxalement, bien qu'il soit impossible de prévoir le comportement d'une trajectoire sans connaître précisément ses conditions initiales, il est quand même possible d'y prévoir des choses. Par exemple, (sauf cas particuliers), les trajectoires seront ergodiques : si on choisit un point sur le bord du billard, la balle finira forcément par passer à un moment ou à un autre près de ce point (et même, aussi près de ce point que l'on veut, si l'on accepte d'attendre longtemps).

Sinaï a en fait produit cet exemple de billard pour montrer qu'il existe un système qui soit à la fois chaotique ("d'exposant de Lyapounov positif") et ergodique, dans le cadre d'un problème sur le comportement physique du mouvement de gaz.

L'entropie de Sinaï-Kolmogorov
Finalement, certains systèmes dynamiques sont faciles à prévoir à court comme à long terme, d'autres le sont à court terme mais pas à long terme, d'autres encore ne le sont plus à moyen terme... Il faut trouver quelque chose pour mesurer tout ça ; ce quelque chose, c'est l'entropie.

Cette entropie n'a pas de rapport direct avec l'entropie des physiciens, mais plutôt avec celle des théoriciens de l'information, à travers l'entropie de Shannon. La définition de l'entropie de Shannon permet de dire qu'une suite de caractère possédant une forte entropie est riche en informations.

Par exemple, les deux phrases "six fois sept égale quarante-deux" et "6×7=42" apportent exactement la même information, mais la deuxième compte sensiblement moins de caractère que la première. La quantité d'information par caractère contenu dans la première phrase est donc très faible, par rapport à l'autre ; son entropie est donc plus petite.
Du coup, quand on commence à écrire "six fois se...", on peut sans trop se tromper penser que les caractères suivants seront "p" et "t" : il est facile de prédire le futur d'une phrase de faible entropie. C'est en s'appuyant sur cette idée que Sinaï produit une notion d'entropie pour certains systèmes dynamiques, en s'appuyant sur les travaux de Kolmogorov (son directeur de recherche).

L'entropie de Sinaï-Kolmogorov permet donc de quantifier la complexité d'un système dynamique, et offre un moyen parfait pour mesurer le chaos. Un système à forte entropie est difficile à prévoir, tout comme il est difficile de prévoir quel sera le mot suivant d'une phrase très riche en information (forte entropie, au sens de Shannon). Si l'on s'accorde à dire que le désordre est riche en information, on peut aussi la relier à l'entropie des physiciens.

Finalement, le mathématicien Iakov Sinaï s'est inspiré de la théorie de l'information pour décrire mathématiquement des systèmes dynamiques issus de la physique. Celui qui a écrit un article intitulé "Mathematicians and Physicists = Cats and Dogs ?" a en fait passé son temps a relier les deux milieux.


Sources :
Site officiel du prix Abel

Images :
Yakov G Sinai photo

Posté par El Jj à 10:00 - Commentaires [0] - Permalien [#]
Tags : , , ,

23 février 2014

Cravate club

L'info a largement été relayée dans les médias, il existerait 177 147 façons de nouer une cravate, et c'est une équipe de mathématiciens et d'informaticiens suédoise qui vient de le publier. Cette étude fait suite à une autre étude qui n'avait compté *que* 85 nouages de cravates différents. 

Mais concrètement, comment ont-ils compté tout ces nœuds de cravate ? Et quel est le rapport entre le film Matrix et cette histoire de cravates ? Détaillons un peu leur méthode.

Les 85 nœuds de Fink et Mao
Thomas Fink et Young Mao, deux physiciens anglais, sont les premiers à s'être formellement penché sur l'épineux problème du nœud de cravate en 1999. 

Pour aborder le problème, pensons cravate. Pour avoir une belle cravate, selon Fink et Mao :
- c'est la partie large de la cravate que l'on manipule
- on commence en plaçant cette partie large du côté gauche du corps (au-dessus ou en dessous de la partie fine, selon le nœud)
- on la passe alternativement au dessus et au-dessous du nœud.
- on termine en passant ce bout à l'intérieur du nœud, pour le "fermer".

La plus simple des variantes est le nœud "quatre en main", qui s'élabore en 4(+1) étapes, de la façon suivante :

Quatre mouvements pour un quatre en main

- on commence en plaçant la partie large de la cravate au-dessus et à gauche de l'autre partie (Li)
- on passe la partie large en-dessous et à droite de l'autre partie (Ro)
- on passe la partie large au-dessus et à gauche de l'autre partie (Li)
- on passe la partie large en-dessous du nœud et on la fait sortir par le col (Co)
- on passe la partie large dans le nœud de la cravate (U)

Les opérations que l'on peut finalement faire, c'est passer la partie large en-dessous (noté o) et au-dessus (noté i) de l'autre partie ; on peut, selon les situations, faire ressortir ce bout du côté droit de la cravate (R), gauche (L) ou au niveau du col (C). La dernière opération faisable, c'est celle qui consiste à passer la partie large dans le nœud de la cravate (et qui n'interviendra qu'une seule fois, à la fin) : la fermeture, notée U.

Bref, il y a 7 opérations possibles : Ro Ri Lo Li Co Ci et U. Un nœud de cravate sera alors complètement défini par une suite de ces opérations, en respectant tout de même certaines règles :

  • Règle 1 : on commence par Lo ou Li (commencer par Ro ou Ri entrainerait des nœuds miroirs, oublions-les).
  • Règle 2 : on ne peut pas faire successivement deux opérations R, L ou C identiques
  • Règle 3 : les opérations o et i doivent être alternées.
  • Règle 4 : la fermeture U n'intervient qu'à la fin, et seulement après les opérations Ro Li Co ou Lo Ri Co (car la cravate doit venir par le dessous du nœud, en passant par le côté col)

Ainsi, la succession de mouvements Lo Ri Lo Ri Co Li Ro Li Co U est tout à fait convenable (et il s'agit du nœud Grandchester, le #44 de la liste de Fink, qui requiert 9 mouvements). 

En traduisant les conditions par un graphe, on peut voir qu'une succession de mouvements qui donne un beau nœud de cravate correspond à un chemin sur le graphe ci-dessous, qui commence à D et se termine en U.

Cravate_simple

On peut alors voir qu'il y a un seul nœud faisable en 3 mouvements (Lo Ri Co U, le nœud oriental), un nœud en 4 mouvements (Li Ro Li Co U, le nœud quatre en main présenté plus haut) et 3 nœuds en 5 mouvements (les nœuds Kelvin, Nicky et Pratt). 
En notant an le nombre de nœuds faisables en n mouvements, on peut remarquer que l'on a an+2 = an+1 + 2 an. En se limitant à 8 mouvements au maximum, on dénombre alors 85 nœuds de cravate différents (le mouvement U final n'intervient pas dans le décompte).

85_noeuds

La notation WTU de Vejdemo-Johansson
Sauf qu'en 2003, toute la théorie a sauté, puisque le film Matrix Reloaded est sorti au cinéma. On ne retiendra qu'une seule chose du film : la cravate porté par Lambert Wilson, qui interprète Le Mérovingien, est nouée de façon à ce que la partie large de la cravate termine en-dessous de la partie fine ! Incroyable ! Luke Housego se dépêche de créer un tutoriel sur Internet, et baptise ce nœud le nœud Edeity.

Noeud_Merovingien
Le nœud Mérovingien, ou nœud Edeity, porté avec classe par Lambert Wilson
Séquence : Lo Ci Lo Ri Co Ri Lo Ci U

En 2008, c'est un nouveau nœud qui apparaît sur Youtube, le nœud Eldredge. Tous les tabous de la cravate sautent : ce n'est pas la partie large de la cravate qui est manipulée mais sa partie fine, celle-ci passe plusieurs fois dans le nœud et, ultime affront, elle termine sa course dans le col de son porteur !

Noeud_eldredge
Le nœud Eldredge
Séquence : Li Ro Ci Lo Ri Co Li Ro U Ci Lo Ci Ro U

Les règles imposées par Fink et Mao sont clairement trop restrictives, en particulier la règle n°4. Pour englober davantage de nœuds (dont le nœud Eldredge), disons plutôt que :

  • Règle 4' : le mouvement U peut intervenir n'importe quand, même après un mouvement L ou R, à condition qu'au moins deux mouvements au moins le précède. De plus, sous certaines conditions d'existence, on autorisera le mouvement UU (ou U²) consistant à rentrer la cravate dans deuxième couche du nœud, et, de manière générale, Uk qui consiste à rentrer la cravate dans la k-ième couche du nœud. Un tel mouvement est possible qu'après au moins 2k autres mouvements.

Il faut alors adapter les règles 2 et 3, en précisant qu'un mouvement U n'influence pas le fait que deux mouvements R, L ou C ne peuvent se succéder à l'identique, même chose pour o et i.

D'ailleurs, la notation o et i est complètement superflue. En effet, une fermeture U ne peut exister qu'après un mouvement o, où la cravate passe sous le nœud. Du coup, l'alternance o/i permet de retrouver les directions d'une séquence RLC de mouvements donnée.

Par exemple, la suite de mouvements du nœud Trinity est LCLRCRLCURLU. Le L qui précède le dernier U ne peut être qu'un mouvement de type Lo, et donc, en remontant, on peut retrouver que le mouvement initial est Li :

Noeud_Trinity
Le nœud Trinity (aucun rapport avec Matrix)
Li Co Li Ro Ci Ro Li Co U Ri Lo U

On peut donc se restreindre à seulement 4 symboles pour décrire le nouage de la cravate : L, R, C et U.
Enfin... Pas tout à fait, puisque l'on a pris pour hypothèse que l'on commence toujours à gauche (mouvement L). Il est donc inutile de le noter dans la liste. Comme deux mouvements L, R et C ne peuvent se succéder à l'identique, on peut se contenter de dire si le prochain mouvement est un mouvement dans le sens des aiguilles d'une montre (noté T - comme Turnwise) ou dans le sens inverse (noté W - comme widdershin).

  • T : tourner dans le sens des aiguilles d'une montre (sens indirect) : R -> L, L -> C ou C -> R.
  • W : tourner dans le sens inverse des aiguilles d'une montre (sens direct) : L -> R, R -> C ou C -> L.

Par exemple, la suite de mouvement WTWTWUTTU du nœud Floating Spiral débute, comme tous les nœuds, par L. Puisque le premier mouvement est de type W, la région suivante est R. On peut ainsi en déduire la séquence complète :

Noeud_Floating_Spiral
Nœud Floating Spiral
Li Ro Li Ro Li Ro U Li Co U

Les 177 147 nœuds de Vejdemo-Johansson
Il est temps de dénombrer les différents nœuds de cravate. Pour cela, l'équipe de Vejdemo-Johansson a remarqué que les nœuds de cravate de 1ere espèce (où la cravate ne peut passer que sous la couche la plus récente crée au dessus du nœud) obéissent toujours au schéma ⟨préfixe⟩ ⟨développement⟩ ⟨fermeture⟩, sachant que

  • le préfixe peut être T ou W (ou rien).
  • le développement est constitué d'une suite (pouvant être vide) de paires (TT, TW, WW ou WT) et de fermetures (TTU ou WWU)
  • la fermeture finale est obligatoire (TTU ou WWU).

Ainsi, WWU et TTU sont des nœuds possibles (correspondant respectivement à un nœud de cravate oriental, et à un nœud où la cravate est mise comme une écharpe autour du cou...). Le nœud T.WW.WW.WWU (Windsor) correspond lui aussi parfaitement à cette description.

Ce schéma peut alors se traduire par un graphe, où les nœuds de cravates valides correspondent à un chemin débutant et terminant sur la case centrale :

Graphe_cravates

Avec un peu de théorie des graphes, on peut remarquer que le nombre de nœuds de 1ere espèce de longueur n et ne comportant qu'une seule fois l'opération U est de 2n-1. En se limitant à au plus 11 mouvements (nécéssaires pour Eldredge), on compte un total de 2048 nœuds de référence fondamentalement différents, auquels s'ajoutent les variantes comptant plusieurs fois l'opération U.

On peut alors les répartir en trois classes, selon la position finale de la cravate (CU, LU ou RU), les nœuds classiques recensés par Fink et Mao sont alors ceux de la première classe, (où la différence entre le nombre de W et de T est de 2 modulo 3).

2046_noeuds
Répartition des 2046 nœuds de référence (Le U final ne rentre pas de le décompte des mouvements)

Mais ces 2046 nœuds et leurs variantes ne représentent qu'une petite portion des 177 147 différents nœuds de cravate recensés. Il faut en effet ajouter toutes leurs variantes de fermetures pour obtenir les nœuds de seconde espèce. Les conditions d'existence de ces variantes s'appuient sur des considérations sur le nombre de W et T précédant les différentes fermetures U. A titre d'exemple, TTWTUU est une séquence valide de 2nde espèce, même si elle n'obéit pas au schéma présenté plus haut.

Au final, les 2046 nœuds engendrent 177 147 nœuds de cravate, ce qui est prodigieusement... beaucoup. Ce que la théorie ne dit cependant pas, c'est le caractère esthétique de chacun de ces nœuds, point qui avait été abordé par Fink et Mao. Du coup, il est aujourd'hui impossible de savoir si nous sommes passé à côté d'un nouage de cravate inédit mêlant élégance et originalité. En attendant, vous pouvez toujours tenter de reproduire l'un des nœuds obtenu à partir du générateur !


Sources :
D. Hirsch, M. L. Patterson, A. Sandberg, M.Vejdemo-Johansson, More tie than we though (d'où provient le dernier graphe)
M.Vejdemo-Johansson, Random tie knots
T. Fink, Encyclopedia of tie knot - donne la liste des 85 nœuds de Fink et Mao
T. Fink, Y. Mao, Designing tie knots by random walks (d'où provient la première illustration)

Posté par El Jj à 10:00 - Commentaires [4] - Permalien [#]
Tags : , , , ,

08 février 2014

Just another Huffman tree

La nétiquette, c'est un ensemble de règles à suivre pour être un gentleman des internets, une charte implicite que tout le monde se devrait de suivre. Par exemple, dans son point 2.1.1 relatif aux bonnes règles d'usage du courrier électronique, la nétiquette requiert :

« Soyez conscient de la longueur des messages que vous envoyez. Annexer de grands fichiers, tels que des documents en Postscript ou des programmes, peut rendre vos messages si grands qu'ils peuvent ne pas être transmis ou au moins consommer une part exagérée de ressources. Une bonne règle sera de ne pas envoyer de fichier dépassant les 50 Ko. Comme alternative, réfléchissez au transfert de fichier, ou à découper le fichier en morceaux plus petits et à les envoyer séparément. » netiquette.fr

Il faut d'autant plus faire attention que 50 ko, c'est très vite atteint !... Bon, la nétiquette date de 1995, un temps où les modems 56k chantaient de la dubstep.
Mais il faut se souvenir qu'un gentleman n'envoie pas de fichier trop lourd à ses amis. Non, il commencera par le compresser à l'aide d'un logiciel adéquat, en s'assurant que son ami sache comment décompresser ce fichier.

Mais d'ailleurs, comment ça marche, la compression de fichiers ? De nombreuses méthodes existent aujourd'hui, mais la première d'entre toutes, c'est quand même la méthode de Huffman, qui n'a aujourd'hui rien perdu de sa superbe. En ce dimanche, parlons de Huffman et de ses arbres.

Saut ASCII
Je souhaite stocker, dans la mémoire de mon ordinateur, la phrase suivante « je ne suis qu'une phrase d'exemple mais j'ai quand même un cœur ». Et comme je suis exigent, je veux le faire de la façon la plus économique possible. Le gros problème, c'est que la seule chose qu'il est réellement possible de stocker dans la mémoire d'un ordinateur, ce sont des petits bouts d'information, des 0 et des 1 (les bits). Ma phrase d'exemple, elle, contient quand même 21 caractères différents, ce qui est sensiblement plus grand que 2.

Du coup, la première idée géniale est de regrouper les bits par groupe de 8 (les octets). Avec 8 bits, on peut fabriquer tout de même 256 nombres. Il suffit d'associer à chaque caractère un des 256 octets possibles, et le tour est joué.

On va dire que le « j » est codé par 01101010, que le « e » est codé par 01100101 ou que l'astérique est codé par 00101010 !

C'est ce que se sont dit dans les années 60 les créateurs de la convention de codage ASCII, histoire d'uniformiser tout ce qui prééxistait. Au final, le codage ASCII permet de coder 127 caractères, dont 95 caractères effectivement affichables, chacun codable sur 7 bits seulement, ce qui est bien suffisant pour les américains de l'époque. On se garde de côté le huitième bit de l'octet, il pourra nous servir à l'occasion.

La phrase « je ne suis qu'une phrase d'exemple mais j'ai quand même un cœur » se codera en ASCII (presque) par 

01101010 01100101 00100000 01101110 01100101 00100000 01110011 01110101 01101001 01110011 00100000 01110001 01110101 00100111 01110101 01101110 01100101 00100000 01110000 01101000 01110010 01100001 01110011 01100101 00100000 01100100 00100111 01100101 01111000 01100101 01101101 01110000 01101100 01100101 00100000 01101101 01100001 01101001 01110011 00100000 01101010 00100111 01100001 01101001 00100000 01110001 01110101 01100001 01101110 01100100 00100000 01101101 00111111 01101101 01100101 00100000 01110101 01101110 00100000 01100011 00111111 01110101 01110010

L'ASCII est cependant incapable de coder des caractères farfelus comme « ê » ou « œ ». Tant pis, ils auront été codé par 00111111 (« ? »).

Au final, avec ce codage, on s'en sort avec un texte codé sur 63 octets, soit 504 bits (ou 441 bits si on enlève tous les '0' inutiles au début de chaque octet). C'est quand même beaucoup. En plus, on s'est fait flouer, puisqu'on a perdu deux caractères essentiels à l'intégrité de la phrase.

Ce qui serait parfait, c'est de compresser cette série de bits, mais sans perdre aucune information sur la phrase.

De l'inégalité patente entre les caractères
La norme ASCII est profondément égalitariste : que l'on soit un caractère cool comme le « », une caractère fréquent comme le « e » et l'espace, ou un caractère inutile comme le «|», on est logé à la même enseigne, sur 8 bits. Une idée géniale, ça serait de coder sur peu de bits les caractères très utilisés, et sur plus de bits les caractères superflus.

C'est en fait le principe du code Morse : une lettre fréquente est codée par un signal rapide (le « e » est codé par « · »), alors qu'une lettre rare est codée par un signal plus long (« y » est codé par « — · — —») .

Faisons ça, toujours sur la même phrase d'exemple. L'espace et le « e » sont fréquent, on les code sur un seul bit ; le « x »  et le « c » sont rares, on les code sur 4 bits :

Code_pas_pratique

Ainsi codée, la phrase sera :

01110011 01000001 10010000 01000011 01010000 11011101 01110101 00011000 10101011 00001100 11000110 10110010 10000110 11110000 00100001 00001000 11010000 110

On s'en sort maintenant avec seulement 139 bits ! Le progrès est énorme ! Oui, mais... Comment on va décoder ça ? Les 4 premiers bits sont 0111, qui peuvent se traduire par « je », mais aussi par « na » ou par « _eee ». Impossible de trancher, on a fait tout ça pour rien.
Pour ne pas avoir ce soucis d'ambiguïté, il nous faut un "code préfixe" ; autrement dit, un système de codage binaire où le code d'un caractère ne doit pas pouvoir être prolongé de façon à former le code d'un autre caractère. Ainsi, si l'on décide que l'espace est codé par 0, le codage d'aucun autre caractère ne doit pouvoir commencer par zéro.

C'est sur ce principe que se base la norme UTF-8 (la norme de codage de caractère la plus utilisée) : un caractère sera codé sur un ou plusieurs octets. Si le premier octet commence par 0, c'est qu'il est codé sur un seul octet selon la norme ASCII, dans le cas contraire, le caractère est codé sur plusieurs octets, et il faut se référer à la base de donnée idoine.

Compression de Huffman
Il me faut donc un code préfixe pour coder « je ne suis qu'une phrase d'exemple mais j'ai quand même un cœur » en utilisant le minimum de bits. La construction d'un tel codage, on la doit à David Albert Huffman, qui a mis au point l'algorithme qui suit lors de sa thèse de doctorat en 1952.

Pour cela, on commence par trier par ordre croissant de présence les caractères qui nous intéressent :

etape0étape 0

Puis, on prend les deux arbres de plus petit poids (ici, « l » et « œ », chacun de poids 1), puis on les réunis de façon à former un arbre binaire, qui sera alors de poids 1+1 = 2. L'arbre ainsi formé est alors remis à sa place, selon l'ordre croissant des poids.

etape1étape 1

On poursuit le processus, en réunissant à chaque étape les deux caractères (ou arbres précédemment formés) de plus petit poids sous une même bannière, dont le poids est la somme des deux poids :

etape2
étape 2

etape3
étape 3

(...)

etape15
étape 12

Finalement, après 19 étapes, on obtient un arbre complet, où les feuilles sont les caractères que l'on cherchait à coder. Le code, il est tout trouvé : en partant du haut de l'arbre, on codera '0' si l'on descend à gauche, et '1' sinon.

♫ And all that I can see is just a yellow Huffman tree ♫

L'arbre codant / décodant

Ainsi, 001 codera « u » ou 01101 codera « j ». Par construction de l'arbre, les caractères les plus fréquents seront au plus prêt de la racine et demanderont une chaîne courte de bits, tandis que les caractères les plus rares seront codés par une chaîne plus longue.

Finalement, ma phrase initiale peut être codée sans aucune ambiguité (grâce à l'arbre) sur 249 bits (32 octets) par 

01101110 11110111 10111101 00010001 10101110 11000010 00000110 11110111 01111010 10101110 10011010 11011101 00100001 10010100 11010000 11110100 00110111 10001001 00011010 11101101 00001001 00011110 11000011 00110110 10011111 00001011 11000110 11100110 11111010 11001000 10010111 0

Cela représente tout de même un gain de 50% par rapport au codage ASCII. Il est d'ailleurs impossible de le coder sur moins de bit avec un code préfixe. merci Huffman !

Si je dois déchiffrer cette séquence de bits, il suffit de la lire en suivant l'arbre. Les premiers caractères étant 01101, ils ne peuvent que coder le « j ».

Bon, il a quand même un hic : si je compresse ma phrase et que je la garde telle quelle, j'aurai du mal à retrouver la phrase initiale si je ne garde pas l'arbre de décodage quelque part. L'arbre doit être rattaché au fichier pour qu'il puisse être décompressé, et cet arbre a un poids : au moins 40 octets !
Finalement, mon message compressé pèsera environ 52 octets, ce qui ne représente plus vraiment un énorme gain par rapport au poids du message initial (63 octets). On peut éviter ce problème en utilisant un arbre générique, spécifique à la langue du texte que l'on code (voir commentaires de l'aticle). Il n'y a alors plus besoin de transmettre l'arbre, mais la compression sera forcément moins importante.
Cependant, le surplus représenté par le codage de l'arbre devient négligeable dès que les fichiers deviennent imposant (à partir de quelques ko).

L'algorithme de Huffman est utilisé par la plupart des logiciel de compression (WinZip, 7-Zip, WinRar...), mais il est le plus souvent couplé à un algorithme de compression de type LZ, qui commence par chercher et éliminer les redondances dans le fichier que l'on cherche à compresser.

Je terminerai par un fait tout à fait intéressant qui n'a rien à voir avec le sujet de l'article. David Albert Huffman ne s'est pas intéressé qu'à la compression de données, il a aussi découvert des méthodes d'origami tout à fait inédites en marge de ses travaux de topologie. Le résultat est particulièrement élégant :

Un bel origami
Pavage origami, mis au point par Huffman.
Il est cependant déconseillé de le compresser.


Sources :
D.A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, l'article original de Huffman
E. Davis & friends, Reconstructing David Huffman's Origami Tessellations, d'où provient l'illustration de l'origami

Posté par El Jj à 10:00 - Commentaires [7] - Permalien [#]
Tags : , ,

19 janvier 2014

24 jours après le Big Bang

Devinette ! Complétez la suite logique suivante :

3
13
1113
3113
132113
...

Ok, tout le monde la connaît, celle-là. Le terme qui suit, c'est 1113122113, car il s'agit de la suite "look and say" (abrégée LS) inventée en 1987 par Conway : chaque terme de la suite s'obtient en lisant les chiffres du terme précédent. Ainsi, la ligne 3113 peut se lire "un '3' puis deux '1' puis un '3'", ce qui donne 132113.

On pourrait s'arrêter au simple constat "ok, elle est marrante ta suite logique, mais t'es gentil, je regarde le match, là". Mais je me dois d'en dire plus, puisque cette suite possède de nombreuses propriétés. La plus merveilleuse d'entre elle a été intitulée "théorème cosmologique" et, résumé par son auteur, nous apprend que "24 jours après le Big Bang, l'ensemble des éléments exotiques ont disparu" ! Il faut dire que derrière cette suite se cache John Conway, qui baptise toujours ses découvertes par des noms improbables, comme le jeu de la vie, les nombres surréels ou le jeu "Sprouts"...
J'avais déjà écrit un article sur ce sujet en 2007, il est temps de le réactualiser.

Évidemment, on peut changer de terme initial pour former d'autres suites LS, comme

3333
43
1413
11141113
...

Il y a également le cas particulier de la suite 22, qui donne :

22
22
22
22
...

Théorème du jour 1 & théorème du jour 2
Avant que vous me trouviez des contre-exemples, mettons nous d'accord sur une chose : le chiffre 0 n'existe pas, tout comme les nombres supérieurs à 9. Si jamais ils venaient à exister, on les écrira quand même avec un seul chiffre. Par exemple, la chaîne qui suivra 1111111111 n'est pas 101 mais ⁂1 (où ⁂ est le chiffre que je viens d'inventer pour désigner le nombre 10) :

1111111111
⁂1
1⁂11
111⁂21
311⁂1211
...

Quelques définitions : on appellera "graine" la chaîne initiale d'une suite LS. Tous les termes qui suivent sont ses descendants : on dira que le premier est âgé de 1 jour, le suivant de 2 jours, etc.
La graine d'une suite LS peut être aussi compliquée que l'on veut, le terme suivant répondra quand même à quelques propriétés.

Du coup, on peut énoncer le théorème du jour 1 : une chaîne âgée de 1 jour...

  • ne peut pas débuter par yxzx (où x, y et z désignent trois chiffres différents - ou pas), ni contenir une telle chaîne dans une position paire.
  • ne peut pas contenir le même chiffre répété 4 fois ou plus (conséquence de la propriété précédente)
  • ne peut pas contenir la chaîne xxxyyy

En conséquence du théorème du jour 1, on a le théorème du jour 2 : une chaîne âgée de 2 jours...

  • ne peut pas faire naître un nouveau 4 (ou tout autre chiffre supérieur)
  • ne peut pas contenir la chaîne 3x3

Il n'est fait aucune mention d'un théorème du jour 3, mais je reviendrai plus tard sur celui du jour 24.

Théorème de séparation
Le point central de la théorie des suites LS est l'idée qu'elles puissent se scinder, dans le sens où il arrive qu'à partir d'une certain étape, la partie gauche de la chaîne n'interfère plus avec la partie droite. Prenons par exemple la suite débutant par 42 :

4·2
14·12
1114·1112
3114·3112
...

D'après le théorème du jour 2, aucun nouveau '4' ne peut apparaître, en particulier à droite du chiffre '4' déjà présent. De ce fait, il ne peut y avoir que un seul '4' à une étape donnée, ce qui le transformera inexorablement en '14' à l'étape suivante, n'interférant pas sur les chiffres qui suivent. On notera par "·" cette scission. 

Il existe dix cas (et pas plus) dans lesquels une chaîne se scinde (c'est le théorème de séparation). Par exemple, une chaîne contenant ...XY... (avec X≥4 et Y≤3) se scindera sous la forme ...X·Y..., ce qui est le cas dans l'exemple précédent . De la même façon, une chaîne contenant ...2111... se scindera en ...2·111... (voir [1] si vous voulez la liste en détail).

Évidemment, les sous-chaînes obtenues peuvent elles aussi se scinder, donnant au fil des étapes de nombreuses sous-chaînes indépendantes.

Il existe alors des sous-chaînes qui ne peuvent pas se scinder : on les appelle les "éléments" (ou "atomes"). Parmi ces éléments, certains finissent inexorablement par apparaître, quelle que soit la graine de la suite (sauf si c'est 22). Ces éléments particuliers (les "éléments communs") sont au nombre de 92, si bien que Conway les a nommé à partir des 92 éléments chimiques existant naturellement, allant de l'hydrogène H1 = 22 jusqu'à l'uranium U92 = 3, en passant par exemple par le carbone C6 = 3113112211322112211213322112 (tous les éléments communs ne sont pas aussi simples que H1 ou U92). Puisque ces éléments ont la fâcheuse tendance à se désintégrer les uns en les autres, Conway les a baptisé "éléments audioactifs".

On ajoute à cette liste les deux éléments transuraniens Np93 et Nu94, les deux seuls éléments comprenant un chiffre supérieur à 3. De ce fait, ces deux éléments existent sous une infinité de versions (leurs "isotopes"), autant que de chiffre supérieur à 4 possibles.

Enfin, il existe une infinité d'éléments 'exotiques', comme 1, 2 ou 4443333444, qui ne peuvent pas apparaître en tant qu'atome après plusieurs étapes.

Du coup, on peut ranger ces 94 éléments communs et transuraniens dans leur tableau périodique :

Tableau périodique des éléments audioactifs

Le tableau périodique des 94 éléments audioactifs de Conway (click doit / ouvrir dans un nouvel onglet, pour voir en encore plus grand !)

A titre d'exemple, l'élément Sm62 = 311332 devient après un jour 13212312, qui se scinde sous la forme 132·12·312 = Pm61·Ca20.Zn30. : Du coup, on peut réécrire la suite de graine 311332 sous la forme suivante :

Sm62
Pm61·Ca20.Zn30
Nd60·K19·Cu29
Pr59·Ar18·Ni28
Ce58·Cl17·Zn30·Co27
...

Ainsi, si la graine de la suite est un élément commun ou transuranien, tous ses descendants seront uniquement composés d'éléments communs et transuraniens. D'ailleurs, si la graine est composée d'éléments communs et/ou transuraniens (et n'est pas H1 = 22), il arrivera tôt ou tard un descendant composé d'au moins une fois les 92 éléments (plus éventuellement des éléments transuraniens) !

L'ordre des éléments a été choisi de façon à ce qu'un élément n soit le descendant direct de l'élément n+1 . Ainsi, en partant d'une graine U92, on aura après 91 génération l'élément H1, au milieu de beaucoup d'autres. Il en fait 6 autres façons de ranger les 92 éléments en suivant cette règle, le tableau ci-dessus correspond à la liste originale dressée par Conway (voir [2] pour les détails).

Le théorème cosmologique
On arrive au théorème le plus important de la théorie des suites LS, le théorème cosmologique :

Quelle que soit la graine choisie, il arrivera une étape où les descendants seront composés uniquement d'éléments communs et transuraniques. Ceci arrivera en au plus 24 étapes !

Ce théorème prouve en particulier qu'un élément exotique ne pourra pas le rester éternellement. Par exemple, si on choisit la graine 1 (élément exotique), on fini par tomber (après 7 étapes) sur le composé Hf72·Sn50 :

1
11
21
1211
111221
312211
13112221
11132·13211 = Hf72·Sn50
311312·11131221 = Lu71·In49
...

La borne des 24 étapes est optimale, puisqu'il existe un élément exotique demandant les 24 jours pour se scinder en élément commun. Cet élément est 22333222114, découvert et baptisé Mathusalum par Mike Guy, collègue de Conway.

La démonstration de ce théorème est particulièrement difficile, si bien que Conway nous a fait le coup de la démonstration perdue. Du coup, la preuve complète la plus récente du théorème cosmologique date seulement de 2003, et, à l'image du théorème des quatre couleurs, comporte une grande partie de calcul informatique.

La constante de Conway
Entre deux termes consécutifs d'une suite LS (quelle que soit sa graine), le nombre de chiffres est en moyenne multiplié par λ = 1.303678... Autrement dit, en notant un le nombre de termes d'une suite LS, on a :

limite_suite_LS

Ce nombre n'est autre que l'unique solution réelle de l'équation

x71 - x69 - 2x68 - x67 + 2x66 + 2x65 + x64 - x63 - x62 - x61 - x60 - x59 +
2x58 + 5x57 + 3x56 - 2x55 - 10x54 - 3x53 - 2x52 + 6x51 + 6x50 + x49 + 9x48 - 3x47 +
- 7x46 - 8x45 - 8x44 + 10x43 + 6x42 + 8x41 - 5x40 - 12x39 + 7x38 - 7x37 + 7x36 + x35 +
- 3x34 + 10x33 + x32 - 6x31 - 2x30 - 10x29 - 3x28 + 2x27 + 9x26 - 3x25 + 14x24 - 8x23 +
- 7x21 + 9x20 + 3x19 - 4x18 - 10x17 - 7x16 + 12x15 + 7x14 + 2x13 - 12x12 - 4x11 +  
- 2x10 + 5x9 + x7 - 7x6 + 7x5 - 4x4 + 12x3 - 6x2 + 3x - 6 = 0

Il s'agit donc de la racine d'un polynôme de degré 71 ! (D'autant que le polynôme est irréductible, ce qui fait de λ l'un des nombres algébriques ayant le plus haut degré de toute la littérature mathématique)

Pour comprendre d'où sort ce polynôme, regardons plutôt la suite suivante, où chaque terme est obtenu à partir du précédent en transformant a en ab, et en transformant b en a :

b
a
ab
aba
abaab
abaababa
...

On peut remarquer que le nombre de caractères des termes de cette suite correspondent à (Fn), la suite de Fibonacci (1, 1, 2, 3, 5, 8, ...), où le rapport des termes consécutifs converge vers le nombre d'or φ :

limite_suite_Fibo

Une façon de démontrer ceci est de remarquer que le nombre an et bn de a et de b à la n-ième ligne de la suite vérifie :

matrice_Fibo

Dans une telle situation, on peut montrer (avec ce qu'il faut d'algèbre linéaire) que les rapports Fn+1/Fn convergent vers la plus grande valeur propre (en module) de la matrice (et indépendamment du terme initial), qui n'est autre φ. Autrement dit, ce rapport converge vers la plus grande racine du polynôme caractéristique de la matrice, qui est X² - X - 1.

Pour les suites LS, l'idée est la même, sauf que la matrice est un tantinet plus compliquée, puisqu'elle est de taille 92×92 ; mais sa plus grande valeur propre est effectivement λ. Voir [3] pour davantage de détails sur le calcul de la matrice et de son polynôme caractéristique.

 

Bref, la prochaine fois qu'un petit malin vous met au défi de compléter la suite de Conway, n'hésitez pas à lui dire que derrière cette bête devinette se cache un bestiaire chimico-mathématique étonnant et une complexité hallucinante !


Sources 
[1] Oscar Martin, Look-and-Say Biochemistry: Exponential RNA and Multistranded DNA, dont l'introduction est très complète
[2] Henry Bottomley, Seven complete sequences for the Conway Look and Say elements
[3] Nathaniel Johnston, A Derivation of Conway’s Degree-71 “Look-and-Say” Polynomial
[4] John Conway, Weird and wonderful chemistry of audioactive decay

Posté par El Jj à 10:00 - Commentaires [6] - Permalien [#]
Tags : , , , ,

12 janvier 2014

Ordre et désordre

Un dernier verre, peut-être ? Venez, ma mie, je vous invite pour un dernier chocolat chaud. Installez-vous sur le canapé, je reviens dans un instant. Ne faites pas attention à cette pile de papiers sur la table et faites comme si les affaires qui traînent par terre, c'est normal. Ignorez également la vaisselle entassée dans l'évier, toute comme cette casserole dans lequel il reste un fond de... euh... ce que j'ai mangé la semaine dernière. Comment ça, cet appartement est mal rangé ? Absolument pas ! D'ailleurs, le désordre total ne peut pas exister ! Ce n'est pas moi qui dit ça, c'est la théorie de Ramsey... Et n'allez pas croire que je me cache derrière les maths... Eh, revenez, je n'ai pas terminé le chocolat chaud !...

La théorie de Ramsey est la suivante : dans une structure contenant beaucoup d'éléments, on finit toujours par retrouver une propriété donnée. La question qui se pose alors, c'est la valeur numérique de ce "beaucoup", qui, pour certain exemple, peut être démesurément grand. On résume plus souvent la théorie de Ramsey par "le désordre total n'existe pas".

Le principe de base de la théorie de Ramsey est le principe des pigeons (alias principe des tiroirs de Dirichlet). Par exemple, à partir de combien de personnes peut-on être sûr d'en trouver deux possédant le même signe du zodiaque ? Puisqu'avec 12 personnes, on peut avoir le zodiaque au complet, la propriété "au moins deux personnes possèdent le même signe astrologique" devient vraie à partir de 13.

Théorème de Ramsey
Le problème central en théorie de Ramsey (et, de façon plus générale, en combinatoire) est celui du théorème de Ramsey. On présente souvent ce théorème par le célèbre problème des six amis.

Vous invitez un groupe d'amis pour une occasion quelconque (soirée foot à la télé, soirée puzzle ...). Parmi ces invités, certains se sont déjà rencontrés auparavent, d'autres se rencontrent pour la première fois. Mais à partir de combien d'invités peut-on être sûr qu'il y ait
- soit trois invités qui se connaissent deux à deux
- soit trois invités qui ne se connaissent pas deux à deux.
Ce nombre, on le notera R(3).

K5

Graphe de la situation.
Deux invités sont reliés par une arête bleue si ils se connaissent, en rouge sinon.
Pour 5 invités, il n'existe pas forcément de trio qui se connaissent ou qui ne se connaissent pas
Ce contre-exemple prouve R(3) ≥ 6.

La réponse est 6, et je peux le prouver ! On suppose que 6 invités sont là, et que David en fait partie (il y a toujours un David dans les invités). Parmi les 5 autres invités, soit il y en a 3 qui le connaissent, soit 3 ne le connaissent pas (par le principe des tiroirs). Sans pertes de généralité, on peut supposer que ces trois invités connaissent David, et qu'ils s'appellent respectivement Karen, Natalie et Billy. Deux possibilités alors : soit ces trois invités ne se connaissent pas (et on a notre trio gagnant), soit il y en a au moins deux qui se connaissent, et ils forment avec David le trio gagnant. CQFD.

Ce problème se reformule dans la théorie des graphes : si les arêtes d'un graphe complet d'ordre 6 sont colorés à l'aide deux couleurs, alors il existe un triangle unicolore.

Friends_strangers_graph

On peut lister l'ensemble des graphes bicolores complets à 6 noeuds.
Ils admettent tous un sous-graphe complet unicolore.

Mais le problème se généralise : combien faut-il réunir d'invités pour être sûr que, parmi eux, il existe un groupe de k invités se connaissant mutuellement, ou ne se connaissant pas du tout ? Ce que nous dit le théorème de Ramsey, c'est que ce nombre existe toujours. Ce que ne nous dit pas le théorème, c'est sa valeur exacte.

Pour k = 4, on peut montrer R(4) = 18, en raisonnant de façon similaire (en trouvant un graphe contre-exemple à 17 sommets, puis en montrant que cela marche bien dès que n=18).
Pour k = 5, les choses se compliquent. Tout ce que l'on sait dire aujourd'hui, c'est que R(5) est strictement compris entre 42 et 50.
Pour k = 6, cela empire : on ne sait pour l'instant dire qu'une seule chose, c'est que le nombre R(6) est quelque part entre 102 et 165...

A ce sujet, Erdõs a imaginé ce qu'il se passerait si une armée d'aliens belliqueux nous déclarait la guerre, à moins qu'on leur fournisse la valeur de R(5). Dans un tel cas, on pourrait mettre à profit l'ensemble des ordinateurs et des mathématiciens de la planète pour calculer ce nombre. Cependant, si ils nous réclamaient R(6), les ordinateurs et mathématiciens disponibles seraient plutôt réquisitionnés pour mettre au point une stratégie permettant de mettre hors d'état de nuire ces extraterrestres...

Le problème de la fin heureuse
Dès qu'un problème cherche le nombre minimal d'objets à réunir pour qu'une propriété soit vérifiée, on peut l'inclure dans la théorie de Ramsey. Un autre problème représentatif est le problème du Happy ending (parce que, à la fin, ils se marièrent et eurent beaucoup1 d'enfants). Ce théorème nous annonce que :

Etant donné (au moins) 5 points du plan (jamais alignés ni confondus),
il y existe toujours quatre points formant les sommets d'un quadrilatère convexe.

Un quadrilatère (ou n'importe quelle figure géométrique) est convexe quand il ne possède aucun creux. Par exemple, le quadrilatère rouge en dessous n'est pas convexe.

HappyEnding

A gauche : un exemple où 4 points ne forment pas un quadrilatère convexe.
A droite, plusieurs dispositions de 5 points. Dans tous les cas, il existe toujours (au moins) un quadrilatère convexe. L'enveloppe convexe des groupes de 5 points est représentée en jaune.

Pour démontrer ce fait, il suffit d'envisager tous les cas possibles, selon l'enveloppe convexe des 5 points (l'enveloppe convexe, c'est le polygone que l'on obtient quand on place un élastique autour de l'ensemble de ses points. Par essence, une enveloppe convexe est convexe).
- si l'enveloppe convexe est un pentagone, il suffit d'en retirer un point pour retrouver le quadrilatère tant cherché.
- si l'enveloppe convexe est un quadrilatère, inutile d'aller chercher plus loin
- si c'est un triangle, alors les deux points à l'intérieur forment un quadrilatère convexe avec au moins l'un des côté (avec le côté qui ne coupe pas la droite formée par les points intérieurs). CQFD.

Cette histoire de quadrilatère convexe est le problème original du happy ending, découvert et démontré en 1933 par Esther Klein. Elle demande alors a ses collègues si l'un d'eux a une idée pour généraliser la question : étant donné un grand nombre de points, y existe-t-il toujours un pentagone/hexagone/n-gone convexe. George Szekeres revient une semaine plus tard avec sa réponse : oui !

Théorème de Erdös-Szekeres : Étant donné un ensemble suffisamment grand de points du plan (jamais alignés ni confondus), il y existe toujours N points formant les sommets d'un polygone convexe.

HappyEnding5
9 points suffisent pour y trouver un pentagone convexe

Si Erdös a accolé son nom a celui de Szekeres, c'est qu'il a pas mal étudié la question lui aussi. C'est d'ailleurs Erdos qui a surnommé ce théorème "happy ending" en 1937, puisque c'est celui-ci qui a mené Esther Klein et George Szekeres à se marier en 1937 !

On peut être un peu plus précis sur la valeur de "suffisamment grand" :
- si on cherche les triangles convexes, 3 points suffisent (puisqu'on les suppose ni alignés, ni confondus)
- si on cherche les quadrilatères convexes, 5 points suffisent.
- si on cherche les pentagones convexes, il faut au moins 9 points.
- si on cherche des hexagones convexes, c'est 17 points qu'il est suffisant d'avoir. Ceci n'a été démontré qu'en 2006 (Szekeres, Peters)
- pour les polygones plus grand, rien n'est encore sûr. On sait qu'il faut au moins 1+2N-2 points pour y trouver à coup sûr un N-gone convexe, on conjecture que cette borne est optimale.

Le problème du polygone vide
Le théorème de Erdös-Szekeres serait encore plus élégant si, en plus d'être convexe, le polygone pouvait être vide (aucun point à l'intérieur). Pour 5 points, pour peu que l'on modifie légèrement la démonstration, on peut montrer qu'il existe toujours un quadrilatère convexe vide. Pour 9 points, il n'existe pas forcément de pentagone convexe vide, mais il suffit de 10 points pour rendre cette assertion vraie. Mais existe-t-il toujours un hexagone convexe vide dans un ensemble assez grand de points ?

La réponse est oui, mais il a fallu attendre 2007 pour en être sûr. Le nombre exact de points suffisant n'est pas connu exactement, mais on sait quand même qu'avec 463 points, on est sûr d'avoir un hexagone convexe vide.

HexagoneCache

463 points au hasard. Il y existe forcément (au moins) un hexagone convexe vide
Avec moins de 463 points, rien n'est sûr...

Je prèfère ne pas trop évoquer le cas de l'heptagone convexe vide, puisqu'il contredit la théorie de Ramsey : même avec un nombre arbitrairement grand de points, on ne peut pas être sûr d'y trouver d'heptagone convexe vide...

Le nombre de Graham
Un dernière exemple de problème de la théorie de Ramsey, le problème de Graham :

Considérons un hypercube de dimension n où chaque arête et diagonale est coloré en rouge ou en bleu.
Y existe-t-il toujours un plan unicolore défini par 4 sommets coplanaires ?
Si non, à partir de quelle dimension n est-ce toujours vraie ?

Exemple, avec n = 3. On a donc un cube (on ne peut plus classique, en 3D), on colore en rouge/bleu ses 28 arêtes et diagonales. Parfois, on peut y trouver un plan unicolore :

GrahamCube

Et parfois, non :

GrahamCube2
Impossible de trouver un plan unicolore passant par 4 points dans ce cube

A partir de quelle dimension peut-on être sûr d'en trouver ? Les spécialistes conjecturent qu'il suffit de chercher dans un hypercube de dimension 13. Mais entre ce que l'on conjecture et ce qu'on l'on arrive à démontrer il y a un gouffre, ce problème en est le plus gros exemple. Ce que Graham est parvenu à démontrer, c'est que la dimension recherchée est un nombre grand. Très grand. Ce nombre est tellement grand que je ne peux l'écrire sur ce blog. Je ne peux même pas écrire le nombre de chiffres qui le compose, pas plus que le nombre de chiffres qui compose son nombre de chiffresCe nombre est tellement grand que si je l'utilise dans une blague de "ta mère", on pourrait penser que j'exagère un peu. A l'heure d'aujourd'hui, cette borne supérieure reste la pire qui existe de toute l'histoire des démonstrations mathématiques. Et pourtant, grâce à cette démonstration, on peut quand même dire qu'il est vrai que la propriété de Graham est vraie en grandes dimensions...

Ce nombre N*, c'est le 64e terme de la suite
u1 = 4
u2 = 3 ↑ 3
u3 = 3  3 3
... où n désigne la flèche (itérée n fois) de Knuth (voir ce vieil article)

Certaines personnes ont du mal à penser en dimension 3, la plupart des gens sont incapable de penser en dimension 4. Il ne me semble pas que quiconque sur Terre soit capable de réfléchir en dimension N*. 


Sources :
Une démonstration du calcul de R(4)
, et plein d'autres articles intéressants sur cut-the-knot
Colorie-moi le ciel, qui parle aussi du théorème de Ramsey infini
Le désordre total n'existe pas..., Pour la Science N°376 - fevrier 2009

Images :
Friends strangers graph


1 : Encore une fois, la théorie de Ramsey ne nous donne pas la valeur exacte de ce "beaucoup".



  1  2  3  4  5    Fin »