[Rediffusion d’un article publié en 2011]

Dobble et la géométrie finie

Piste bleue Le 5 juillet 2020 - Ecrit par Maxime Bourrigan Voir les commentaires (24)
Lire l'article en

[Rediffusion d’un article publié en 2011]

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.

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.


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...

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.

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]

+	$\bf 0$	$\bf 1$
$\bf 0$	$\bf 0$	$\bf 1$
$\bf 1$	$\bf 1$	$\bf 0$

x	$\bf 0$	$\bf 1$
$\bf 0$	$\bf 0$	$\bf 0$
$\bf 1$	$\bf 0$	$\bf 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.

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 là 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.

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

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

[2] Et 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.

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

[4] Si 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. »

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

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

[7] Par 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é ?

Commentaire sur l'article

Dobble et la géométrie finie

le 4 mai 2011 à 16:30, par Jean Lecureux

Dans le même genre, il y a bien sûr Set (que l’on peut aussi s’amuser à projectiviser), qui consiste à trouver des droites dans l’espace affine sur le corps à 3 éléments. En jouant, on se pose naturellement la question suivante, qui s’avère très difficile : quel est la taille maximal d’un ensemble qui ne contient aucune droite ?

Je me demande si c’est faisable d’essayer de jouer à ce genre de jeu sur un plan projectif exotique, voire sur d’autres structures d’incidences (eg. m-gones généralisés).
Répondre à ce message

Dobble et la géométrie finie

le 23 octobre 2020 à 17:42, par Gabriel Pallier

Concernant première question sur Set, je mentionne une mise à jour : il y a eu des progrès assez importants sur la borne supérieure [1]. Pour la deuxième question, si l’on veut rester au plus proche des règles de Set, la structure à considérer semble être celle de systèmes de Steiner $(2,3,n)$. Les plus petits qui ne proviennent pas d’espaces affines ou projectifs sont d’ordre $n=13$, il y en a $2$ ; en plus de $P^4 F_2$ il y en a $79$ d’ordre $n=15$ [3]. Ceux qui ont un maximum d’automorphismes sont tous affines ou projectifs, en revanche [2].

[1] Ellenberg, J.S. and Dion Gijswijt, On Large Subsets Of ${\Mathrm{\Mathbb{F}}}_{\Mathrm{q}}^{\Mathrm{n}}$, Annals of Mathematics, vol. 185, no. 1 (2017), pp. 339—343.
[2] Key, J. D. ; Shult, E. E., Steiner triple systems with doubly transitive automorphism groups : a corollary to the classification theorem for finite simple groups, J. Combin. Theory Ser. A 36, no. 1 (1984), 105—110.
[3] Mathon, R. A. ; Phelps, K. T. ; Rosa, « Small Steiner triple systems and their properties » Ars Combin. 15 (1983), 3—110.
Répondre à ce message

Dobble et la géométrie finie

le 5 mai 2011 à 09:20, par Clément Caubel

Dans le même genre : le propriétaire fortuné d’un grand yacht organise une croisière durant tout le mois d’août, et y convie trente-et-un pipeuls. Il souhaite dîner chaque soir avec six d’entre eux, de sorte qu’il voie tous ses invités le même nombre de fois et que deux quelconques d’entre eux ne soient réunis à sa table qu’une seule fois durant le séjour (pour des histoires de haine recuite, c’est commun chez les pipeuls si l’on en croit les journaux spécialisés).

Est-ce possible et si oui comment faire ?

Indications

Comme dans l’article : on remplace « point » par « invité », « droite » par « tablée » et on travaille sur le corps à 5 éléments. Evidemment, ça ne marcherait pas en février ou en septembre...

Dresseur de plans de table pour les propriétaires de yacht fortunés : un nouveau débouché pour les mathématiciens ?
Répondre à ce message
Dobble et la géométrie finie

le 5 mai 2011 à 14:34, par Jean-Paul Allouche

Joli article ! À propos du mot modulo, ablatif de modulus, il signifie « dans le module ». Modulo 7 signifie donc « dans le module 7 ». À proprement parler utiliser ce mot dans une phrase comme « modulo les bouchons » ou « modulo les erreurs » comme on l’entend souvent, est en fait une faute que commettent bon nombre (la plupart ?) des mathématiciens...
Répondre à ce message
Dobble et la géométrie finie

le 25 août 2011 à 16:05, par simeos

L’article est très intéressant, merci.

En testant quelques solutions de jeux, je me suis demandé d’où venait le fait que « le nombre de cartes qu’un tel jeu peut avoir est encore très mystérieux » (dans la conclusion) ?
Apparemment il est possible de construire un jeu de n(n-1)+1 cartes où n désigne le nombre de symbole par cartes. J’ai essayé un algorithme assez simple construisant le jeu complet pour un nombre n donné, et la solution vérifie bien les trois conditions énoncées dans le paragraphe « Retour au “vrai" Dobble ». L’algorithme utilise juste des permutations circulaires successives pour construire le jeu.
Je pense ne pas avoir trop compris quel est précisément le problème encore ouvert. Où pourrais-je trouver des références, précisions sur ce problème ?
Merci.
Répondre à ce message

Dobble et la géométrie finie

le 19 février 2018 à 21:44, par zoblazo

Salut,
J’essaye de construire un Dooble en ce moment mais je n’y arriverai sans doute pas (à moi de m’aider avec chaque carte du jeu original) à l’aide d’un algorithme.
Peux-tu m’expliquer comment marche celui que tu as programmé ?
Merci
Répondre à ce message

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 là 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

Dobble et la géométrie finie

le 31 août 2011 à 15:37, par Sébastien Godillon

Très joli article, merci.

Je m’étais aussi intéressé au problème de dénombrement à la découverte de ce jeu sans connaître les structures mathématiques sous-jacentes. Du coup, ma curiosité a été aiguisée par ces plans projectifs finis définis seulement de manière combinatoire et qui généralisent ceux rencontrés en géométrie algébrique.

Par contre, je ne suis pas convaincu par la suffisance des trois axiomes de votre message précédent. Il me semble qu’ils n’écartent pas les cas où tous les points sauf un sont alignés sur la même droite (et pour lesquels les résultats de dénombrement ne tiennent plus).

L’article de Wikipédia propose un troisième axiome différent (il existe un sous-ensemble de quatre points tel qu’aucune droite en contienne au moins trois d’entre eux) mais je le trouve moins « naturel » que les deux premiers axiomes. En particulier, il écarte le plan projectif d’ordre 1 à trois points qui semble pourtant être le premier exemple élémentaire.

D’où ma question : n’ayant pas lu les références citées à la fin de votre message précédent, quel est l’axiome utilisé dans la littérature pour compléter la définition combinatoire des plans projectifs ?

Et je profite de ce message pour poser une autre question afin de satisfaire ma curiosité : qu’en est-il de la question de l’existence des plans projectifs non arguésiens de manière générale (je veux dire : même pour les ordres qui sont des puissances d’un nombre premier) ? Vous avez répondu par l’affirmative dans le cas q=9, mais cette question est-elle elle aussi ouverte en générale ?

Merci d’avance pour vos éclairages et merci encore pour cet article.
Répondre à ce message

Dobble et la géométrie finie

le 20 mars 2015 à 12:42, par vpnmag

Merci pour cette publication. Là au moins on a un concept de ce qu’est la double géométrie.

vpnmag
Répondre à ce message

Dobble et la géométrie finie

le 29 novembre 2011 à 15:56, par Stéphane Lamy

A propos du jeu « set » mentionné en début d’article, voici un lien vers un article (en anglais, et pas piste bleue...) de mon ex-collègue Diane Maclagan à l’Université de Warwick.
Répondre à ce message
Dobble et la géométrie finie

le 21 janvier 2012 à 17:07, par amic
Pour ceux qui cherchent les deux cartes qui manquent, elles ont été recensées ici. Apparemment c’est un problème de production (planches de 60 cartes, avec 5 cartes de règles si j’ai bien compris) qui leur a fait enlever deux cartes… Quand le business fait du tort aux mathématiques, rien ne va plus !

Mais la méthode pour les trouver est assez simple :
- Par ces deux points-cartes passe une seule droite-symbole. Ce symbole doit donc apparaître seulement 6 fois dans le jeu au lieu de 8. On trouve alors que c’est le bonhomme de neige.
- Ensuite les autres symboles qui sont dans ces deux cartes sont donc tous différents puisqu’elles n’ont que le bonhomme en commun. On a donc 14 symboles (7 par carte) qui ne se retrouvent que 7 fois dans le jeu au lieu de 8.
- Une fois qu’on les a trouvés, il reste juste à les répartir entre les deux cartes, et pour ça on utilise la dernière propriété : pour deux droites-symboles quelconques, il existe un unique point-carte d’intersection.
  On se prend donc un symbole de référence parmi les 14, et pour les 13 autres on regarde s’il existe une carte dans le jeu qui contient ce symbole et le symbole de référence, dans ce cas ces deux symboles ne doivent pas être sur la même nouvelle carte, et sinon ils sont sur la même nouvelle carte.
Questions subsidiaires :
- À partir de combien de cartes manquantes est-on fichu et n’est-on plus sûr de retrouver quelles sont les cartes qui manquent ?
- Quelle est la taille minimale d’un ensemble de cartes qui permet de reconstituer toutes les autres ?
Sinon pour le problème de trouver un autre type de jeu avec ces cartes, on pourrait imaginer un jeu des 7 familles ou le but est de faire les droites les plus complètes, ou un morpion à l’envers : le premier qui aligne 3 cartes a perdu.

Enfin il y a plein de façon de jouer à ce jeu, mais je ne sais pas vraiment si ça exploite les propriétés mathématiques.

Sinon un truc qui peut être drôle c’est de fabriquer un « Trobble » : Un ensemble de cartes telles que si l’on en prend 3 d’entre elles il y a toujours un unique symbole commun aux 3 cartes. Il suffit de prendre cette fois ci des points-cartes et des plans-symboles.

Puis on pourrait réaliser un « Quadrobble » et ainsi de suite en augmentant les dimensions.

Bref, on n’a pas fini de s’amuser.
Répondre à ce message

Dobble et la géométrie finie

le 3 janvier 2013 à 21:10, par G.B.

Je découvre cet article très longtemps après sa publication. J’ajoute quand même deux choses.

Concernant le nombre de cartes dans le jeu édité, une explication plausible est la suivante : plusieurs règles demandant de mettre une carte de côté puis de distribuer le reste d’une façon ou d’une autre entre les joueurs, le nombre 55=54+1 semble un peu meilleur puisqu’il permet un partage équitable en 3. Ce n’est qu’une hypothèse. Je doute en tout cas que les créateurs du jeu (Denis Blanchot, Guillaume Gille-Naves, Igor Polouchine, Jean-François Andreani, non mentionnés dans l’article) aient réussi à créer leur jeu par tâtonnements.

Une référence récente et extrêmement bien faite (en tout cas pour débuter) sur les plans projectifs, dont le cas fini, et sur les géométries en général : l’ouvrage Geometries de Sossinsky (chapitres 12 et 14 notamment), téléchargeable en ligne.

Enfin, je signale la parution d’un article du magazine Quadrature n°87 très complet sur la question (article grâce auquel j’ai atterri sur ce site).
Répondre à ce message

Dobble et la géométrie finie

le 3 janvier 2013 à 21:50, par Maxime Bourrigan

Tiens ? Je ne connaissais pas cet article de Quadrature...

J’aurais sans doute dû le préciser mais j’ai reçu après la publication de cet article un mail de Denis Blanchot qui tue le suspense : visiblement, le nombre de cartes total (i.e. en comptant les mini-règles du jeu) était fixé et les concepteurs ont préféré inclure plus de règles que préserver la structure projective qui, de toute façon, ne sert à rien. Comme le fait remarquer Denis Blanchot, on peut continuer à jouer à Dobble même en ayant perdu des cartes !

Et je suis sincèrement désolé de ne pas avoir cité les auteurs du jeu mais je me souviens avoir eu un peu de mal à les déterminer clairement (j’ai un peu oublié les détails mais je crois me rappeler que la contestation mentionnée par la notice wikipédia m’a un peu fait peur ; j’ai remplacé le rique de commettre une injustice partielle par la certitude d’en commettre une globale, solution dont je reconnais volontiers qu’elle n’est guère optimale).
Répondre à ce message

Dobble et la géométrie finie

le 3 janvier 2013 à 22:41, par G.B.

Merci de cette réponse.

Concernant la non-mention des auteurs, il ne s’agissait nullement d’un reproche (le « ton » de l’écrit est souvent plus sec qu’à l’oral). Je suis féru de jeux de société et je sais qu’il est souvent difficile de faire reconnaître le statut d’auteur à ceux qui les conçoivent. Je voulais simplement rendre justice à ceux de Dobble, car c’est réellement un excellent jeu, au-delà de son indéniable intérêt mathématique.

L’article de Quadrature vient juste de sortir (numéro de janvier-février-mars 2013). Ce site y est référencé. Tant que j’y suis, il est de David et Marie Hézard, pour ne pas qu’on me reproche à mon tour de ne pas citer les noms des auteurs !

Merci en tout cas pour cet article particulièrement clair et explicatif !
Répondre à ce message

Dobble et la géométrie finie

le 1er mai 2012 à 13:49, par Laurent Dietrich

Un ami m’a montré un algorithme (le plus naturel possible) qui permet pour tout n, de créer un jeu de n*(n-1) + 1 cartes (avec n symboles par carte). Aucun nombre premier ne se cache derrière tout ça, donc.

Par contre c’est purement combinatoire. Peut-on inclure ça dans une modélisation géométrique plus large qui inclurait votre cas de géométrie dans les corps finis ?

Est-ce que cette quantité n*(n-1) + 1 vous évoque quelque chose de géométrique ?
Répondre à ce message

Dobble et la géométrie finie

le 23 mai 2012 à 22:39, par Sophie Gire

Article très intéressant !

Quand j’ai réfléchi au problème (lorsque j’ai acheté le jeu à sa sortie
...) j’ai aussi réussi à créer des jeux dobble de n symboles par cartes
ayant n*(n-1)+1 cartes, mais je ne sais le faire que pour n-1 premier !
L’algorithme de l’ami ci dessus m’intéresse donc vivement !

Je n’avais jamais pensé à regarder ce problème sous l’angle de la
géométrie, je vais le faire maintenant. Merci !
Répondre à ce message

Dobble et la géométrie finie

le 19 juin 2012 à 19:32, par Laurent Dietrich

Erratum, en fait après observation un peu moins dilettante des cartes produites, ça foire effectivement si n-1 n’est pas premier...
Répondre à ce message

Dobble et la géométrie finie

le 10 juillet 2016 à 17:30, par buzhug

Bonjour

Cet article est très intéressant : merci !

Il me semble avoir trouvé un algorithme qui fonctionne mais j’avoue ne l’avoir testé que sur de faibles nombres.

Si je veux N symboles par cartes, il me faut N(N-1) +1 cartes et autant de symboles en tout.

Je vais donc noter ces symboles 1 ; 2 ; 3 … N(N-1)+1

La première carte sera
1 ; 2 ; 3 ; … N (= (N-1) +1)

ensuite
1 ; (N-1)+2 ; … ; 2(N-1)+1 -> d’où le premier cycle (N-1)+2 ; … ; 2(N-1)+1

1 ; 2(N-1)+2 ; … ; 3(N-1)+1 -> d’où le deuxième cycle 2(N-1)+2 ; … ; 3(N-1)+1

……

1 ; (N-1)(N-1) + 2 ; …… ; N (N-1) +1 -> d’où le dernier cycle (N-1)(N-1) + 2 ; …… ; N (N-1) +1

J’ai ainsi créé (N-1) cycles de valeurs pour les 2ème à Nème symboles de la carte

Le premier cycle (N-1)+2 ; … ; 2(N-1)+1 se répète toujours de la même façon

Les cycles suivant subissent des permutations circulaires +1 ; +2 ; … + (N-2)

Je donne un exemple concret sur un petit nombre : N = 4 donc 13 cartes et symboles

Les cartes sont :

1 ; 2 ; 3 ; 4

1 ; 5 ; 6 ; 7 -> premier cycle 5 ; 6 ; 7 qui sera répété à l’identique

1 ; 8 ; 9 ; 10 -> deuxième cycle 8 ; 9 ; 10 qui se verra décalé de +1

1 ; 11 ; 12 ; 13 -> troisième cycle 11 ; 12 ; 13 qui se verra décalé de +2

ce qui donne les cartes suivantes : cycles inchangés pour la première série

2 ; 5 ; 8 ; 11

2 ; 6 ; 9 ; 12

2 ; 7 ; 10 ; 13

on commence les décalages +0 ; +1 ; +2 pour les séries suivantes

3 ; 5 ; 9 ; 13

3 ; 6 ; 10 ; 11

3 ; 7 ; 8 ; 12

et la dernière série :

4 ; 5 ; 10 ; 12

4 ; 6 ; 8 ; 13

4 ; 7 ; 9 ; 11

Pour le moment, je rencontre un souci avec (N-1) non premier par exemple pour N=7 car N-1 = 6 est divisible par 3 donc le décalage +3 pose problème.
J’obtiens ainsi une carte
2 ; 8 ; 14 ; 20 ; 26 ; 32 ; 38

ainsi qu’une carte
4 ; 8 ; 16 ; 24 ; 26 ; 34 ; 42

qui ont deux nombres en commun.
Il me semble que cet algorithme devrait fonctionner pour (N-1) premier … si vous avez un algorithme qui fonctionne quelque soit (N-1), je veux bien …

Cordialement
Répondre à ce message

Dobble et la géométrie finie

le 4 janvier 2014 à 17:28, par Martin Champel

Voici qui me rassure ! Ce jeu si simple est bel et bien digne d’intérêt !

Ce « parallélisme » géométrique est très intéressant mais, compte tenu de ma myopie mathématique, j’ai un peu de mal à visualiser au delà de n =3.
A dire vrai, je m’obstinais (et m’obstine toujours) à trouver un algorithme à base de combinatoire qui permette de construire un tel jeu . Quiconque peut m’aider à construire cet algorithme fera un heureux.
Merci et bonne année.
Répondre à ce message
Dobble et la géométrie finie

le 11 septembre 2014 à 19:09, par Michel Gaillard

Merci beaucoup pour cet article, je me suis intéressé au concept mathématique caché derrière le jeu au lendemain d’une partie endiablée en famille il y a quelques mois !

A partir de là j’ai pu faire un petit programme qui génère le jeu en se basant sur un ppf d’ordre p^n avec p premier.

C’est plus compliqué pour créer le ppf si n > 1 car il faut alors utiliser l’arithmétique des polynômes modulo un polynôme irréductible de degré n...

Je me demande si l’utilisation d’un algo à base de combinatoire est vraiment possible dans l’état actuel de la technologie, on doit être rapidement confronté à une explosion combinatoire pour vérifier l’existence d’un plan projectif pour un ordre différent d’une puissance de nombre premier.
Répondre à ce message
Dobble et la géométrie finie

le 11 septembre 2014 à 19:37, par Maxime Bourrigan

Cher Michel Gaillard,

je crois en effet que la question devient très vite hors de portée. En fait, le résultat le plus récent (le fait qu’il n’existe pas de plan projectif d’ordre 10) a été traité par ordinateur en 1991 : vous pouvez en apprendre plus en lisant cet article.

Je ne sais pas du tout si des choses comme ça ont été tentées pour traiter les petits cas encore ouverts (l’existence d’un plan d’ordre 12, par exemple).
Répondre à ce message
Dobble et la géométrie finie

le 22 septembre 2015 à 15:20, par Frédéric Holic

Comme d’autres l’ont fait remarquer ici, il est très facile de prouver sans géométrie que pour n symboles, le nombre théorique maximum de cartes différentes (égal au nombre de symboles différents utilisés) est de n*n - n + 1 (ce qui fait bien 57 cartes pour 8, et 7 pour 3).

Puisque deux cartes prises au hasard n’ont qu’un et un seul symbole en commun, on peut en effet remarquer que :

1) un symbole S ne peut pas se retrouver sur plus de n cartes - ou alors toute carte comportant un symbole autre que S pris sur chacune des n premières cartes n’aura aucun symbole en commun avec la (n+1)-ème carte, et le jeu sera limité à (n+1) cartes ;

2) il ne peut pas y avoir en jeu d’autres symboles que ceux présents sur ces n cartes ayant S en commun - si l’on introduit dans le jeu une carte avec un nouveau symbole, les autres (différents de S pour ne pas retomber dans le 1) étant pris sur les (n-1) premières cartes, cette carte n’aura aucun symbole commun avec la n-ème.

Du coup, on arrive à un total théorique de n*(n - 1) + 1 symboles, qui sont reproduits n fois sur des cartes de n symboles, ce qui fait bien n*n - n + 1 cartes en tout (je ne sais pas si j’ai été clair, mais reprenez mon explication au calme, et vous verrez qu’elle se tient).

Toutefois, l’explication ci-dessus ne garantit pas que ce total théorique soit effectivement atteignable - il faut en effet exhiber un algorithme pour ça...
Répondre à ce message
Dobble et la géométrie finie

le 6 février 2020 à 02:33, par Andrés Navas

Voici les deux cartes qui manquent !
Travail en collaboration avec María José Moreno pour le Festival de Maths du Chili. .
Document joint : dobble_carta2.png
Répondre à ce message
Dobble et la géométrie finie

le 6 février 2020 à 02:34, par Andrés Navas

Pardon : voici l’autre carte...
Document joint : dobble_carta1.png
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.

Connexion | s’inscrire | mot de passe oublié ?

L'auteur

Maxime Bourrigan

PRAG à l’École Normale Supérieure

[Rediffusion d’un article publié en 2011]

Dobble et la géométrie finie

Dobble

Cartes et symboles, points et droites

Géométrie finie

Un système fini de nombres

Un dernier raffinement

Retour au « vrai » Dobble.

Conclusion

Notes

Pour citer cet article :

Crédits image :

Commentaire sur l'article