Dobble et la géométrie finie

Piste bleue Le 10 août 2014  - Ecrit par  Maxime Bourrigan Voir les commentaires (20)

Beaucoup de mathématiciens aiment jouer : pour ne citer que deux exemples, le champion du monde d’échecs Emanuel Lasker (1868-1941) est l’auteur d’un théorème d’algèbre célèbre [1] et, plus récemment, l’un des contributeurs de ce site, saurez-vous le trouver ?, a été plusieurs fois champion de France du jeu de go.

Les rapports entre les jeux et les mathématiques passent aussi par la très sérieuse théorie des jeux, qui a notamment popularisé le dilemme du prisonnier.

Le but de cet article est d’exposer un rapport plus inattendu, où un véritable jeu de société cache une très jolie structure mathématique.

JPEG - 2 Mo

Dobble

Dobble est un petit jeu de société, édité par Asmodée et Play Factory. C’est un jeu d’observation et de rapidité, un peu à l’image du très célèbre Jungle Speed (qui, à ma connaissance, ne repose pas sur un principe mathématique) ou du moins connu Set ! (qui est beaucoup plus intéressant d’un point de vue mathématique, et mériterait lui aussi un billet).

Dobble est un jeu constitué de 55 cartes, sur chacune desquelles sont imprimés 8 symboles. Une des manières d’y jouer est la suivante : chacun des joueurs reçoit un tas de cartes, et une carte est placée au milieu de la table. Toutes les cartes sont posées face visible. Les joueurs doivent alors, le plus vite possible, identifier un symbole commun entre la carte devant eux et celle qui est au milieu de la table. Une fois que l’un des joueurs a réussi, il place sa carte au milieu de la table, par dessus la précédente, et le jeu continue jusqu’à ce que l’un des joueurs se soit débarrassé de tout son tas.

JPEG - 1.9 Mo
Une partie de Dobble
Dans la situation décrite sur la photo, je pourrais me débarasser de ma carte en disant « Taxi, » Alice à ma gauche le pourrait en disant « Sens interdit » et Juliette en disant « Œil. »

Par exemple dans la photo ci-dessus, je pourrais me débarrasser de ma carte en disant « Taxi, » Alice à ma gauche le pourrait en disant « Sens interdit » et Juliette en disant « Œil. » Le site du jeu contient une démonstration vous permettant de vous entraîner à reconnaître les symboles en commun le plus vite possible. Croyez-moi, ce n’est pas si facile !

Évidemment, si la carte d’un des joueurs n’avait aucun symbole en commun avec la carte du centre, il serait en droit de protester face à cette injustice... Et si un joueur avait deux symboles en commun avec la carte du centre, il serait deux fois plus facile pour lui d’en identifier un. Bref, pour que la course ne soit pas biaisée, il a fallu que les concepteurs du jeu respectent un principe important :

Deux cartes quelconques du jeu Dobble ont toujours exactement un symbole en commun.

On va essayer d’expliquer comment les mathématiques peuvent nous aider à construire un tel jeu, en essayant de construire notre propre version de Dobble, en modèle réduit.

Cartes et symboles, points et droites

Le principe que l’on vient d’énoncer peut faire penser à un slogan géométrique célèbre :

Par deux points quelconques du plan passe toujours exactement une droite.

L’analogie entre le principe de Dobble et notre slogan géométrique est alors assez évidente. Elle invite à voir les cartes du jeu comme des « points » et les symboles sur ces cartes comme des « droites ». Et au lieu de dire qu’une carte contient un symbole, on dit que le point est sur la droite. Cela ressemble pour l’instant à un jeu de langage un peu gratuit [2] mais on va voir qu’il nous mènera loin...

PNG - 511.1 ko

On a déjà construit, au moins en pensée, une version infinie du jeu de Dobble : il nous faut imprimer autant de cartes qu’il y a de points du plan et sur chacune d’elles imprimer la liste des droites du plan qui passent par ce point. Le principe du jeu de Dobble est respecté, mais notre solution n’est guère réalisable en pratique. [3]

Géométrie finie

On va essayer de suivre notre idée en restant dans le domaine du possible. Pour cela, utilisons une idée mathématique importante : celle des coordonnées cartésiennes.

On apprend au collège qu’on peut représenter un point du plan par deux nombres, son abscisse, souvent notée x et son ordonnée, souvent notée y.

De même, les droites du plan admettent des équations : si une droite n’est pas verticale, elle admet l’équation y = ax + b, c’est-à-dire qu’un point d’abscisse x et d’ordonnée y est sur la droite si y et ax + b ont la même valeur. Et si elle est verticale, elle admet l’équation x = c.

PNG - 12.3 ko

En tout cas, l’idée importante est qu’on peut représenter un point du plan ou une droite du plan par des nombres. Et pour faire de la géométrie, comme par exemple pour savoir si un point est sur une droite, il n’y a besoin que de faire des additions et des multiplications.

Notre espoir d’utiliser notre slogan géométrique pour construire un jeu de Dobble renaît alors : on va simplement changer de nombres ! Si on utilise un autre système de nombres qui permette quand même de faire des additions et des multiplications et qui soit fini, on pourra imprimer nos cartes-points et leurs symboles-droites pour obtenir un jeu de Dobble.

Un système fini de nombres

Il y a plusieurs manières de choisir un tel système fini de nombres, mais on va prendre le plus simple : commençons par remarquer que si l’on connaît le caractère pair ou impair de deux nombres entiers, on connaît également la parité de leur somme et celle de leur produit. Par exemple, la somme d’un nombre pair et d’un nombre impair est toujours impaire alors que leur produit est toujours pair. On peut résumer ces propriétés par des « égalités » : Pair + Impair = Impair et Pair x Impair = Pair, et ainsi de suite pour les autres cas.

Pour gagner du temps, utilisons une abréviation : puisque 0 et 1 sont les nombres pair et impair les plus simples, notons 0 à la place de Pair et 1 à la place de Impair. On obtient ainsi les tables d’addition et de multiplication suivantes, bien plus simples que celles qui figuraient au dos de mes cahiers de brouillon : [4]

+ {{0}} {{1}}
{{0}} {{0}} {{1}}
{{1}} {{1}} {{0}}
x {{0}} {{1}}
{{0}} {{0}} {{0}}
{{1}} {{0}} {{1}}

On remarquera que 0 et 1 gardent certaines des propriétés de 0 et de 1 : l’addition par 0 et la multiplication par 1 ne changent rien et la multiplication par 0 remplace tout le monde par 0. On pourra donc par exemple écrire x à la place de 1x.

On a maintenant un système de nombres fini où seuls existent 0 et 1. On peut donc maintenant parler de « points » et de « droites » avec ce système de nombres, en gardant les idées de coordonnées d’un point et d’équation d’une droite. On a donc dans notre « plan » :

  • 4 points : (0,0), (1,0), (0,1), (1,1) ;
  • 6 droites dont :
    • 2 droites verticales : x = 0 (qui contient les deux points (0,0) et (0,1)) et x = 1 (qui contient les deux autres) ;
    • 2 droites horizontales : y = 0 et y = 1 ;
    • 2 droites obliques : y = x (qui contient (0,0) et (1,1)) et y = x + 1 (qui contient les deux autres).

On peut donc fabriquer un jeu de Dobble qui contient 4 cartes-points et 6 droites-symboles. On voit que chaque point appartient à 3 droites différentes, c’est-à-dire que sur chaque carte sont imprimés 3 des 6 symboles.

PNG - 187.6 ko

Notons que dans l’image précédente, si les droites rouge et blanche semblent se couper, ce n’est qu’une illusion : elles ne se coupent pas puisque aucun point n’appartient à la fois à l’une et à l’autre.

Un dernier raffinement

On peut encore enrichir notre mini-Dobble en lui ajoutant une droite. Cette idée, qui est la base de ce que les mathématiciens appellent la géométrie projective date en fait des peintres de la Renaissance et consiste à ajouter un point (le point de fuite des peintres) pour chaque famille de droites parallèles. Ce point est alors le point d’intersection de la famille des droites. Les points de fuite sont tous alignés sur une droite, que les mathématiciens appellent « la droite à l’infini » et tous les autres « l’horizon. »

Il est possible de définir très rigoureusement ces notions, dont on a déjà parlé çà et mais nous n’entrerons pas dans les détails ici.

Dans notre contexte, deux droites sont parallèles si elles n’ont aucun point en commun, et il nous faudra donc ajouter trois points « à l’infini » : un à l’intersection des droites noire et jaune, un à l’intersection des droites bleue et verte, et un à l’intersection des droites blanche et rouge. Et ces trois points sont sur une nouvelle droite, ce qui rajoute un symbole à notre jeu.

PNG - 269.1 ko

Dans ce dessin, les « droites » correspondent aux six vraies droites et au cercle central. Il nous permet de fabriquer un jeu de Dobble à sept cartes et sept symboles, où chaque carte porte trois symboles.

Retour au « vrai » Dobble.

Mais quid du vrai Dobble, que vous pouvez acheter dans toute bonne boutique de jeux ou de jouets ? Eh bien sa construction est assez semblable, sauf qu’il est basé sur un système de nombres différent. Au lieu de n’avoir que deux nombres, 0 et 1, le système du vrai Dobble en a sept, qui obéissent à des tables d’addition et de multiplication assez semblables aux nôtres. Il est alors beaucoup plus difficile de faire des dessins, mais le principe est le même, et d’une certaine façon, l’intuition des points et des droites de la vie courante rend l’objet plus compréhensible. [5]

Quant à lui, notre mini-Dobble a 7 cartes. La première version était en effet constituée de 4 = 2 x 2 cartes (chacune représentée par deux nombres qui pouvaient être 0 ou 1). On a ensuite ajouté un point par famille de droites qui ne se coupaient pas : ces familles sont constituées des droites de la forme y = ax + b qui ont la même pente a (dans notre cas a peut être 0 ou 1) et de la famille des droites verticales. Cela explique donc qu’on ait obtenu 7 = 2 x 2 + 2 + 1 cartes en tout.

Le vrai jeu de Dobble, en digne grand frère de celui que l’on a construit, devrait pareillement avoir 7 x 7 + 7 + 1 = 57 cartes. Or, il n’en a que 55 ! Rassurez-vous, je ne vous ai pas trop menti : le jeu peut être obtenu par la recette que nous avons vue (avec un système à sept nombres et une droite à l’infini) : il suffit d’enlever deux cartes à la fin de la construction. [6] Je ne sais pas pourquoi ces deux cartes manquent (est-ce une contrainte de fabrication ? les créateurs sont-ils arrivés à la construction « à la main », oubliant deux points en chemin ?).

Si l’on rajoute les deux cartes manquantes au vrai jeu de Dobble, il partage alors des jolies propriétés avec le nôtre :

  • ils ont autant de cartes que de symboles (7 ou 57) ;
  • chaque symbole apparaît le même nombre de fois (3 fois dans notre mini-Dobble, 8 fois dans le vrai, une fois complété) ;
  • si vous choisissez deux symboles quelconques, vous pouvez trouver une carte (et seulement une) sur lesquels les deux symboles apparaissent.

Conclusion

On a vu comment la géométrie avec des ensembles de nombres finis permettait de construire des jeux vérifiant le principe de Dobble. Mais cette « géométrie finie » donne aussi naissance à des objets plus mathématiques, qui sont dignes d’intérêt pour eux-mêmes. C’est ainsi que le jeu de Dobble à sept cartes que nous avons construit est une incarnation d’un célèbre objet mathématique, le « plan de Fano » qui intervient dans des domaines assez différents des mathématiques : en combinatoire, en théorie des groupes et même en physique théorique.

D’ailleurs, les « jeux de Dobble » qui vérifient les propriétés énoncées à la fin du paragraphe précédent ont été assez étudiés et il reste des questions ouvertes à leur sujet : par exemple, le nombre de cartes qu’un tel jeu peut avoir est encore très mystérieux (le premier cas ouvert est celui d’un jeu à 157 cartes ; chaque carte aurait alors 13 symboles mais nul ne sait si une telle construction est possible).

Pour terminer, je laisse un défi aux lecteurs, dont j’ignore s’il est réalisable. Dobble permet véritablement de tenir en main une très jolie structure mathématique, ce qui est assez rare. Je trouve qu’il est un peu dommage de n’en faire « qu’un » jeu de rapidité, aussi divertissant soit-il. D’où le défi : est-il possible de trouver une nouvelle règle du jeu qui en fasse un jeu de réflexion exploitant plus la structure mathématique ? [7]

Post-scriptum :

Les symboles utilisés pour dessiner nos mini-Dobble proviennent de la bibliothèque libre OpenClipArt. Merci aux contributeurs de ce projet ! Merci également à François Brunault, niki2000, Serma, Bruno Duchesne, Clémence et Avner Bar-Hen pour leur relecture et leurs commentaires.

Notes

[1Le théorème de Lasker-Noether qui porte sur la structure des idéaux des anneaux nœthériens.

[2Et même un peu fumeux. Mais avant que cette idée ne porte ses fruits, on peut déjà se rassurer en se disant qu’on est en bonne compagnie. Outre la comparaison évidente avec certains jeux de l’Oulipo, on peut citer l’immense mathématicien allemand David Hilbert qui disait déjà que l’important dans les axiomes tels que notre « slogan » géométrique n’est pas le nom des objets (on pourrait remplacer « point » par « chaise » et « droite » par « table ») mais les relations entre ces objets.

[3Même la société qui gère l’hôtel de Hilbert refuserait probablement d’éditer notre jeu...

[4Si on compare ces tables aux tables usuelles, on remarque qu’il n’y a que deux différences : primo, on ne considère pas les nombres à partir de 2 ; secundo, 1 + 1 = 0 alors que 1 + 1 = 2. Les mathématiciens disent que l’on compte modulo 2, c’est-à-dire que l’on fait comme si 2 ne comptait pas, comme s’il valait 0. C’est tellement pratique que le mot « modulo » est entré dans la langue courante (des mathématiciens) et qu’il n’est pas rare d’entendre des phrases comme « Modulo les bouchons, j’arriverai dans un quart d’heure. »

[5Ce qui ne veut pas dire qu’elle nous permette d’identifier le symbole commun plus rapidement, hélas !

[6Si vous connaissez de la géométrie projective, identifier les cartes manquantes est un exercice amusant.

[7Par exemple, en supposant que l’on rajoute les deux cartes manquantes, saurez-vous exploiter les trois propriétés supplémentaires dont nous avons parlé ?

Partager cet article

Pour citer cet article :

Maxime Bourrigan — «Dobble et la géométrie finie» — Images des Mathématiques, CNRS, 2014

Commentaire sur l'article

Voir tous les messages - Retourner à l'article

  • Dobble et la géométrie finie

    le 27 août 2011 à 10:07, par Maxime Bourrigan

    Merci pour vos commentaires.

    Essayons d’être un peu plus précis.

    Ce que j’ai appelé « un jeu de Dobble qui vérifie les propriétés supplémentaires » s’appelle en vérité un « plan projectif fini. » C’est un ensemble fini de points (= cartes) par lesquels passent un ensemble fini de droites (= symboles) et qui vérifient les propriétés suivantes :

    • par deux points, il passe une unique droite (la règle de Dobble) ;
    • deux droites ont toujours exactement un point en commun (une de mes « propriétés supplémentaires »)
    • tous les points ne sont pas sur la même droite (ce qui ne serait pas très intéressant).

    On peut alors démontrer, ce que vous dites dans votre commentaire, que tous les droites ont le même nombre de points, que l’on note en général q+1, et même que tous les points sont sur q+1 droites. Il y a alors en tout q^2 + q + 1 points (et autant de droites). Le nombre ’q’, qui est votre n-1, s’appelle l’ordre du plan projectif.

    Ce que j’ai essayé d’expliquer dans cet article, c’est que la géométrie permettait de construire un tel plan projectif fini à partir d’un « système fini de nombres » (dont le nom officiel est « corps fini »). À partir de mon système à q=2 nombres on obtient un mini-Dobble à 7 cartes ; à partir d’un système à q=7 nombres (les entiers modulo 7) on obtient le vrai jeu de Dobble (une fois les deux cartes fantômes rajoutées). La recette que j’ai expliquée est la recette « standard » pour construire des plans projectifs finis. Ceux que l’on obtient comme ça sont appelés « arguésiens » (en anglais, Desarguesian) parce qu’ils sont caractérisés par une propriété supplémentaire qui fait écho à un théorème de géométrie dû à Desargues. Donc, dès qu’il existe un corps fini à q éléments, il existe un plan projectif d’ordre q. Un théorème classique affirme que cela se produit exactement quand q est la puissance d’un nombre premier. À ce moment du raisonnement, on a donc des plans projectifs d’ordre 2, 3, 4, 5, 7, 8, 9, 11... (c’est-à-dire à 7, 13, 21, 31, 57, 73, 91 ou 133 points) mais on ignore s’il en existe d’ordre 6, 10, 12... (c’est-à-dire à 43, 111 ou 157 points).

    Là où la situation se complique, c’est que notre recette n’est pas la seule : on sait par exemple qu’il existe des plans projectifs d’ordre 9 qui ne sont pas obtenus par notre recette (qui ne sont pas arguésiens, donc). La question ouverte à laquelle je fais allusion est la suivante : existe-t-il de tels plans projectifs non arguésiens d’ordre q où q n’est pas la puissance d’un nombre premier ? En termes plus relâchés : c’est bien beau vos Dobble bizarres, mais est-ce que ça fait des exemples avec un nombre de cartes nouveau ?

    Cette question est toujours ouverte, mais il existe des résultats (de non-existence) partiels : le théorème de Bruck-Ryser affirme que si un plan projectif d’ordre q existe et que q est congru à 1 ou 2 modulo 4, alors c’est la somme de deux carrés. Cela démontre qu’il n’existe pas de plan projectif d’ordre 6 ou 14. Une recherche exhaustive par ordinateur a par ailleurs démontré qu’il n’existe pas de plan projectif d’ordre 10. Le premier cas vraiment ouvert est donc celui où q=12, c’est-à-dire avec 157 points-cartes.

    Il doit donc y avoir un problème avec votre algorithme. 43 cartes, ce n’est pas encore tellement, il est peut-être encore possible de le détecter « à la main. » Êtes vous bien sûr que non seulement 2 cartes ont toujours un unique symbole en commun, mais qu’en outre, deux symboles sont toujours présents simultanément sur une unique carte ?

    Pour ce qui est des références, les articles wikipédia, à commencer par puis en suivant les différents liens, sont un point de départ honnête. Le livre de référence sur le sujet semble être Projective Planes de Hughes et Piper, mais il n’est pas très engageant. De manière plus générale, toutes ces questions font partie d’un écosystème plus vaste : la « design theory » (je ne connais pas de traduction française) ou « géométrie d’incidence ». Ce genre de questions est évoqué dans plusieurs ouvrages de combinatoire, comme A course in Combinatorics de van Lint et Wilson, et il y a des ouvrages qui lui sont spécifiquement dédiés, comme le Handbook of Incidence Geometry qui contient un chapitre sur les plans projectifs, écrit par Beutelspacher.

    J’espère que ça aide un peu.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM