Choux romanesco, Vache qui rit et intégrales curvilignes

07 août 2014

[#] Aquitaine-Poitou-Charente-Limousin

En juillet dernier, Antoine Planchot, sur Twitter, proposait aux matheux le défi suivant :

Quand on me pose, directement ou indirectement, ce genre de question, je réagis toujours plus ou moins de la même façon 
- je lis l'énoncé en me disant que cela n'a pas l'air si difficile, et je retourne vaquer à mes occupation, 
- je libère 10 minutes de mon planning pour y réfléchir un peu plus précisément, 
- deux heures plus tard, j'enrage de ne pas encore avoir trouvé, 
- trois jours plus tard, je résous enfin le problème, maugréant qu'en fait, c'était trivial !

Pour ce problème de #RéformeTerritoriale, je suis toujours bloqué dans la phase 3, mais je suis persuadé qu'un lecteur bien plus malin que moi trouvera l'idée qui m'a échappé. Je ne suis donc pour l'instant pas encore en mesure d'aider François Hollande et son gouvernement, mais on va quand même essayer pour aujourd'hui de trouver une borne supérieure satisfaisante du nombre de cartes à envisager !

Si je compte bien, la France compte 26 régions (métropolitaine ou d'outre-mer), ainsi qu'une collectivité métropolitaine (la Corse) et 5 d'outre-mer.
Je ne crois pas qu'il ait été à un moment donné question de fusionner la Martinique avec la Franche-Compté, donc on ne prendra pas en compte les régions et collectivités d'outre-mer dans le problème. Puisque l'idée que la Corse puisse fusionner avec la région PACA a été étudiée, on prendra en compte dans le calcul 22 régions françaises.

CarteDeFrance
La France de la #RéformeTerritoriale : 22 régions, 44 frontières, 23 points triples

Les nombres de Bell
Première idée naïve : combien existe-t-il de façon de partionner un tel ensemble de 22 éléments ? De toutes ces partitions, on aura par exemple l'actuel projet de réforme territoriale :

ReformeTerritoriale
Une carte de France à 13 régions, dont la future Aquitaine-Poitou-Charente-Limousin, qu'il faudra renommer au plus vite.

Ou bien, la partition correspondant aux différents indicatifs téléphoniques locaux :

Projet06
Une carte de France à 5 régions

Mais il y aura également cette partition des régions Françaises en 3, en fonction du nombre de voyelles et consonnes dans leur nom. Cette dernière ne répond pas au problème initial, puisque les régions formées ne sont pas d'un seul tenant ("connexe"). Pas grave, on cherche pour l'instant une estimation haute du nombre de carte que l'on pourrait faire.

MauvaiseReforme4
Un redécoupage à exclure
(En bleu, les régions comptant plus de consonnes que de voyelles, en rouge les régions comptant plus de voyelles que de consonnes, et en blanc les régions égalitaires)

Le nombre de façons de partionner un ensemble à n éléments porte un nom, ce sont les nombres de Bell (du nom de Eric Temple Bell, mathématicien célèbre autant pour ses travaux en combinatoire que pour ses livres d'histoire des mathématiques ou de science-fiction). Le n-ième nombre de Bell, noté Bn, représente donc le nombre de partitions différentes d'un ensemble à n éléments.

B0 = 1 : il n'y a qu'une seule (non) façon de découper un ensemble vide.
B1 = 1 : il n'y a qu'une seule façon de découper un ensemble à 1 élément.
B2 = 2 : dans un ensemble à 2 éléments, on peut soit regrouper les deux éléments (première partition), soit ne pas les regrouper (seconde partition).
B3 = 5 : 1 partition en une seule région, 3 partitions en deux régions et 1 partition en trois régions.

GrandOuestRedecoupé
5 façons de redécouper le grand Ouest

B4 = 15. Pour trouver cette valeur, procédons méthodiquement, en rajoutant la haute-Normandie dans le grand Ouest. Après un redécoupage, 4 cas différents peuvent se produire, suivant le nombre de régions pouvant être annexées à la Haute-Normandie.
- zéroième cas : toutes les régions sont liées à la HN → 1 découpage
- unième cas : une région (parmi les 3 du grand Ouest) n'est pas annexée à la HN → 3 découpages
- deuxième cas : deux régions ne sont pas fusionnées à la HN, soit 3 paires possibles. Chacune de ces paires admet 2 découpages. Au total, on a donc 3 × 2 = 6 découpages
- troisième cas : aucune région n'est accolée à la HN. On ne compte donc que les découpages à 3 régions, soit B3 → 5 découpages.
On a bien B4 = 1 + 3 + 6 + 5 = 15.

On peut déterminer les valeurs plus grande de Bn en suivant la même trame, en fonction du nombre de région k qui ne seront pas annexées à une n+1-ième région. Parmi les n premières régions, il y a k parmi n façons de choisir ces k régions. Ces k régions admettant Bk découpages, on a donc, pour chaque k,  k parmi n×Bk découpages.

NombreDeBell

Les valeurs suivantes de Bn se calculent par récurrence


Au final, les valeurs plus grandes des Bn sont donc données par la formule de récurrence :

Formule Aitkin

Ainsi,  B5  = 1×B0 + 4×B1 + 6×B2  +4×B3 + 1×B4 = 52

Cette formule nous permet alors de savoir que, pour 22 régions, on peut compter
B22 = 4 506 715 738 447 323 (=4,5×1015) (=4,5 billiards de) partitions !

Les nombres de Bell ont des tas de propriétés fascinantes (par exemple, le n-ième nombre de Bell est la valeur en 0 de la n-ième dérivée de la fonction f(x) = exp(exp(x)-1)), mais il est inutile d'en parler davantage ici, puisque n'est de toutes évidence pas une bonne modélisation ; le nombre de partitions est bien supérieur au nombre de redécoupages.

Passage au dual
Plutôt que de chercher à fusionner les régions, cherchons donc plutôt à retirer les frontières entre régions. Ainsi, il n'y a plus aucun risque de fabriquer des régions non connexes.

La France (métropolitaine) compte 43 frontières, auquel on peut ajouter une 44e frontière P.A.C.A./Corse. Un redécoupage territorial consiste alors à choisir, pour chacune des 44 frontières, si il faut la garder ou non.
Avec cette approche, on peut donc donner une nouvelle estimation (haute) du nombre de partitions. Il y a donc (au plus) 244 = 17 592 186 044 416 (=1,8 ×1013) (=18 billions de) redécoupages !

Le problème de cette approche, c'est que plusieurs choix différents de frontières à retirer donnent un même redécoupage.

Tripoint_Problem
Autour du tripoint Haute-Normandie/Picardie/Île-de-Frane, 4 choix différents des frontières à retirer aboutissent à la fusion des mêmes régions

Ce problème apparaît pour chacun des tripoints (point où trois frontières se rejoignent), lorsque sur les trois frontières, une seule est gardée (la région formée est alors mal délimitée). Et des tripoints régionaux, il y en a 23 en France (sur les 44 frontières, 42 sont ratachées à au moins un tripoint).

Autour d'un tripoint, 3 frontières se rejoignent, ce qui devrait donner 23=8 redécoupages. Mais sur ces 8 redécoupages, 5 sont vraiment différents.
Pour dénombrer les découpages, on va partir d'un premier tripoint (par exemple, le tripoint Bretagne/Pays-de-la-Loire/Basse-Normandie), qui donne naissance à 5 découpages. On choisit ensuite un deuxième tripoint tel qu'il existe une frontière la reliant au premier tripoint (par exemple, le tripoint Pays-de-la-Loire/Basse-Normandie/Centre). On a alors deux nouvelles frontières que l'on peut garder ou non, ce qui multiplie par 2²=4 le nombre de découpages possibles. En regardant d'un peu plus près, on peut remarquer que multiplier par 3 à chaque nouveau tripoint suffit :

  • Si la frontière liant les deux tripoints est gardée, alors il faut qu'au moins une des deux nouvelles frontières soit gardée. On exclut donc un des 4 découpages, celui où les deux nouvelles frontières ne sont pas gardées.

  • Si la frontière liant les deux tripoints n'est pas gardée, il n'y a que deux possibilités pour créer des régions bien délimitées : soit on garde les deux nouvelles frontières, soit on en garde aucune.
    Dans certains cas, on multiplie par 3, dans d'autres, on multiplie par 2. Pour avoir une estimation haute, on multipliera toujours par 3.

A chacun des 22 tripoints suivant, on mutlipliera donc par 3 le nombre de découpages. Le résultat sera à multiplier par 2², pour prendre en compte les frontières sans tripoints (PACA/Corse et Nords-Pas-de-Calais/Picardie). On a donc au total :

5 × 322 × 4 = 627 621 192 180 (=6,3 × 1011) (=627 milliards de) découpages

Encore une fois, cette estimation est trop haute, pour plusieurs raisons. La première, c'est qu'on a supposé que chaque tripoint apporte deux nouvelles frontières, ce qui n'est pas toujours le cas. Suivant la façon dont on choisit le tripoint suivant, on peut avoir qu'une seule nouvelle frontière, voire aucune. Si seule une nouvelle frontière se présente, on ne multipliera le nombre de découpage que par 2 ; si un tripoint n'apporte pas de nouvelle frontière, on multipliera par 1.

La deuxième, c'est que la multiplication par 3 n'est pas optimale (on multiplie par 3 si la frontière est gardée (62% des découpages), et par 2 sinon. Un meilleur coefficient multiplicateur serait de 2,61). Les multiplicateurs 2 et 1 du paragraphe précédent ne sont eux non plus pas optimaux.

En prenant ceci en compte, cela donne * (environ) 2 000 000 000 (=2 milliards de) découpages. Cette dernière estimation a elle aussi été faite à la hache, d'autant qu'il y a encore d'autres points à prendre en compte pour parfaire le calcul. En effet, il est possible que les régions formées ne sont pas simplement connexes (si une région est enclavée à l'intérieur d'un autre), ce qui diminue encore une fois le nombre de redécoupages possibles.

En fait, la seule façon de connaître le nombre exact de redécoupages possibles serait d'écrire un programme informatique qui les énumère tous... Mais en attendant, j'estime le nombre de découpages à un milliard, et c'est mon dernier mot.


Pour les besoins des illustrations de l'article, j'ai fabriqué un petit script pour fabriquer de *jolies* cartes pour tester des réformes territoriales, disponibles sur eljjdt. En fouillant le script, vous y trouverez les données utiles pour faire un programme compteur.


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 [10]
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]
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]
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

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]
Tags : , , , ,


Fin »
Licence Creative Commons
Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 3.0 France.
ISSN 2270-129X