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.
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 !
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 :
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.
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 :
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 :
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 :
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 !
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 :
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 :
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.
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 :
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 !
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.
Récapitulatif des différents Dobble existants
Sources :
Dobble et la géométrie finie, sur Images des Maths
/http%3A%2F%2Fstorage.canalblog.com%2F38%2F13%2F210892%2F99552251_o.png)
/http%3A%2F%2Fstorage.canalblog.com%2F72%2F06%2F210892%2F94888148_o.jpg)
/http%3A%2F%2Fstorage.canalblog.com%2F75%2F80%2F210892%2F89993777_o.jpg)
/http%3A%2F%2Fstorage.canalblog.com%2F93%2F48%2F210892%2F89760281_o.jpg)