David Madore's WebLog: Comment faire un jeu de Tribble

Je continue sur les idées développées dans cette entrée (et dans une moindre mesure la suivante) : ma métaphorique petite sœur se plaint qu'un quadrangle généralisé ce n'est pas, nonobstant mes explications fumeuses, une structure très convaincante pour inventer des jeux de cartes, alors que le jeu de Dobble a au moins réussi à convaincre des gens de l'éditer. Si ce dernier est basé sur le principe que deux cartes quelconques ont toujours un symbole en commun, peut-on faire un paquet où trois cartes quelconques auraient toujours un symbole en commun ?

Réponse : oui, on peut, mais je crois qu'il va falloir admettre un nombre de symboles par carte un peu désagréablement élevé (ou un nombre total de cartes bien bas) :

J'ai créé ici 26 cartes portant chacune 30 symboles choisis parmi un répertoire de 130, chaque symbole apparaissant sur 6 cartes différentes, deux cartes distinctes ayant toujours exactement 6 symboles en commun, et trois cartes distinctes ayant toujours exactement 1 symbole en commun. On peut donc imaginer toutes sortes de jeux de rapidité (ou en fait, plutôt de patience) consistant à chercher le symbole en commun à trois cartes, selon des règles inspirées de celles qui servent pour Dobble. Maintenant, à vrai dire, je trouve ça surtout excessivement fastidieux : il m'a fallu plus de deux minutes pour trouver le symbole commun entre les trois premières cartes (notons que l'ordre des cartes affiché ci-dessus n'est pas aléatoire, et ce symbole est en fait commun aux cinq premières cartes et à la dernière, mais ce n'est pas un bug), et je ne trouve pas ça spécialement ludique. Mais bon, il y a plein de choses que je ne trouve pas ludique et que d'autres gens aiment, alors peut-être que ce jeu peut quand même trouver des adeptes (si quelqu'un veut un tirage physique, qu'il me fasse signe).

Ajout : Un jeu qu'on pourrait jouer avec ces cartes consiste à distribuer à chaque joueur le même nombre de cartes (le plus élevé possible) en en laissant deux face retournée sur la table ; quiconque peut montrer du doigt un symbole en commun entre une carte quelconque de sa main et les deux cartes sur la table pose sa carte sur la table et défausse l'une des deux qui y étaient déjà (de façon qu'il y en ait toujours deux) ; le jeu se continue jusqu'à ce que quelqu'un se soit ainsi débarrassé de toutes ses cartes. La particularité de cette procédure est que celui qui arrive à poser une de ses cartes gagne un avantage pour le coup suivant vu qu'il a pu déjà rechercher l'intersection entre les deux cartes sur la table.

Pour répondre à des questions naturelles : l'ordre de disposition des symboles sur une carte donnée est totalement aléatoire (j'ai commencé par essayer de trouver une logique qui me convienne, mais j'ai vite craqué et opté pour un tirage au hasard — enfin, au hasard déterministe —, au prétexte qu'il vaut mieux un chaos garanti qu'un ordre basé sur une logique douteuse) ; et la permutation des symboles à l'intérieur du répertoire l'est aussi. L'ordre des cartes affiché ci-dessus n'est pas aléatoire, mais ça n'a pas d'importance puisqu'un vrai jeu de cartes serait de toute façon mélangé avant usage. Et sinon, je sais que mon choix de symboles est certainement merdique, mais je n'accepterai de critiques que de la part de gens qui peuvent en suggérer un meilleur ; j'ai cherché à avoir une proportion raisonnable de signes d'écriture (lettres ou caractères chinois) et de dessins, j'ai voulu éviter les symboles qui se ressemblent trop (par exemple, je n'ai pas mis le ‘C’ parce qu'il est trop semblable au ‘G’, je n'ai pas mis le ‘Ш’ parce qu'il est trop semblable au ‘Щ’, etc.) même si je sais qu'il en reste, et globalement il n'y a pas trop de logique mais c'est un peu l'idée.

❦

J'explique maintenant comment construire la chose, parce que je trouve ça assez joli : pour résumer très brièvement, on peut dire que si le jeu de Dobble est basé sur l'idée que deux points distincts dans le plan (projectif, mais peu importe) déterminent une unique droite, celui-ci est basé sur l'idée que trois points distincts sur la sphère déterminent un unique cercle (cercle signifiant petit ou grand cercle, i.e., l'intersection de la sphère avec un plan ; en l'occurrence, le plan passant par ces trois points) : on imaginera les cartes du jeu comme les points de la sphère, et les symboles sur une carte comme les cercles passant par ce point. Il ne reste plus qu'à transformer ça en une structure finie en passant sur un corps fini, donc à expliquer ce que sphère et cercle veulent dire dans ce contexte. En gros, je dois parler un peu de géométrie de Möbius.

Le plus simple est sans doute de partir de la description de la sphère usuelle comme la sphère de Riemann : autrement dit, on identifie les points de la sphère unité {(u,v,w)∈ℝ | u² + v² + w² = 1} avec l'ensemble ℂ∪{∞} des nombres complexes auxquels on a adjoint le symbole ∞, l'identification étant faite par la projection stéréographique de la sphère. C'est-à-dire que pour projeter un point (u,v,w) de la sphère, on trace la droite qui le relie au pôle « nord » (0,0,1), et où cette droite rencontre le plan équatorial donnera le nombre complexe avec lequel on identifie ce point ; ce n'est pas très important, mais la formule explicite pour ce complexe est : z = (u+i·v)/(1−w) (et réciproquement : u=2Re(z)/(|z|²+1), v=2Im(z)/(|z|²+1) et w=(|z|²−1)/(|z|²+1)), avec la convention que le pôle nord lui-même est vu comme le point ∞. En quoi cette identification est-elle pertinente pour ce que je veux raconter ? D'abord, la projection stéréographique fait que les cercles de la sphère deviennent (ce n'est pas complètement évident géométriquement !) des cercles du plan complexe, ou éventuellement des droites pour les cercles qui passaient par le pôle nord (on conviendra donc que les cercles de ℂ∪{∞} sont les cercles du plan complexe usuel, ainsi que les droites de celui-ci auxquelles on a adjoint ∞). Par ailleurs, une propriété fort sympathique est que quatre points distincts z₁,z₂,z₃,z₄ de ℂ∪{∞} sont situés sur un même cercle (dans ℂ∪{∞} ou, ce qui revient au même, sur la sphère projetée stéréographiquement) si et seulement si leur birapport, défini comme ((z₁−z₃)·(z₂−z₄))/((z₂−z₃)·(z₁−z₄)) (avec les conventions assez évidentes si l'un des quatre est ∞), est un nombre réel.

En fait, cette quantité a la propriété de rester invariante quand on applique une homographie, c'est-à-dire une application z ↦ (a·z+b)/(c·z+d) où a,b,c,d sont quatre complexes tels que a·d−b·c ≠ 0, condition ici nécessaire et suffisante pour qu'il s'agisse d'une bijection ; mieux : on peut envoyer quatre points distincts sur quatre autres points distincts si et seulement si ils ont le même birapport ; comme par ailleurs les homographies transforment les cercles en cercles et peuvent même transformer tout cercle en n'importe quel autre cercle, et comme on est convenu que l'axe réel ℝ∪{∞} comptait comme un cercle, ces différentes propriétés expliquent que le birapport est réel si et seulement si les quatre points sont cocycliques.

On peut maintenant expliquer comment passer à une structure finie. Pour commencer, soit F un corps fini ayant q éléments (où q est nécessairement une puissance d'un nombre premier ; par exemple, si q est premier, F est le corps ℤ/qℤ des entiers modulo q), et soit K le corps à q² éléments ; pour mes lecteurs qui ne sont pas trop familiers avec les corps finis, disons que dans le cas particulier où q est un nombre premier congru à 3 modulo 4, on peut définir K comme l'ensemble des r+s√−1 où r,s sont des éléments de F, c'est-à-dire des entiers modulo q, et √−1 est un symbole formel, et ces expressions se manipulent exactement comme les nombres complexes (notamment, (√−1)² = −1 ; le moins évident est que l'inverse de r+s√−1 vaut (r−s√−1)/(r²+s²) comme on s'en convainc en développant). Comme je veux aussi pouvoir travailler avec q=5, je donne aussi une construction lorsque q est un nombre premier congru à 3 ou 5 modulo 8 : dans ce cas, on peut définir K comme l'ensemble des r+s√2 où r,s sont des éléments de F et √2 est un symbole formel vérifiant (√2)² = 2 (et l'inverse de r+s√2 vaut (r−s√2)/(r²−2s²)).

Il faut imaginer qu'on va refaire la même chose que la sphère de Riemann, en faisant jouer à F le rôle de ℝ et à K le rôle de ℂ. Notamment, on va appeler « sphère sur F » l'ensemble K∪{∞} obtenu en adjoignant le symbole ∞ à K. On appelle « cercle » passant par z₁,z₂,z₃ sur cette « sphère » l'ensemble formé de ces trois points et des des z₄∈K∪{∞} (différents d'eux et) tels que le birapport, défini par exactement la même formule ((z₁−z₃)·(z₂−z₄))/((z₂−z₃)·(z₁−z₄)) que ci-dessus, soit un élément de F (ou ∞, mais en fait ceci ne se produit que pour z₄ valant z₁, que j'ai écarté) ; il faut néanmoins compléter ma définition du birapport par différentes règles assez intuitives pour traiter les cas indéterminés (essentiellement, si z₁ vaut ∞, on s'autorise à simplifier ∞ au numérateur et au dénominateur et le birapport vaut juste (z₂−z₄)/(z₂−z₃)). Une autre façon de dire la même chose est que les cercles sont les images de F∪{∞} par les homographies z ↦ (a·z+b)/(c·z+d) (avec a,b,c,d quatre éléments de K tels que a·d−b·c ≠ 0). Notamment, tous les cercles ont exactement q+1 points. On peut par ailleurs montrer qu'il y a q³+q = q(q²+1) cercles au total, q²+q = q(q+1) cercles passant par un point quelconque donné et q+1 cercles passant par une paire quelconque donnée de points distincts, et exactement un par un triplet de points distincts.

Pour montrer que cette construction est assez concrète, et manipulable à la main, je prends l'exemple de q=3, c'est-à-dire que F est le corps ℤ/3ℤ = {0, 1, −1} des entiers modulo 3. Je peux construire K en ajoutant le symbole formel √−1 ou √2 (ça revient au même dès que les deux sont permis c'est-à-dire lorsque q est congru à 3 modulo 8 ; et ici c'est même exactement pareil puisque −1 = 2 modulo 3). Autrement dit, le corps K à q²=9 éléments est l'ensemble {0, 1, −1, √−1, 1+√−1, −1+√−1, −√−1, 1−√−1, −1−√−1}, où on fait les sommes terme à terme modulo 3 et les produits en développant, en utilisant le fait que (√−1)²=−1 et en travaillant toujours modulo 3 (au final, cela revient à faire sommes et produits dans les complexes et réduire parties réelle et imaginaire modulo 3). La « sphère » K∪{∞} sur F=ℤ/3ℤ a donc dix éléments (les neuf que je viens de citer, et ∞). Pour construire les cercles, on part de {∞,0,1,−1}, et on applique ad libitum les opérations consistant à translater (ajouter une même constante aux quatre éléments), homothétiser (multiplier par une même constante les quatre éléments) ou prendre l'inverse. Par exemple, en translatant le cercle {∞,0,1,−1} par −1+√−1, on obtient le cercle {∞, −1+√−1, √−1, 1+√−1} (ces deux cercles, comme ils contiennent ∞, méritent sans doute plutôt d'être appelés des droites) ; en prenant l'inverse, {0, 1+√−1, −√−1, −1+√−1} (l'ordre n'a pas d'importance : il s'agit juste d'un ensemble ; je garde juste les éléments dans l'ordre dans lequel je fais les opérations, pour aider à suivre celles-ci) ; en multipliant par √−1, on obtient {0, −1+√−1, 1, −1−√−1}, et en translatant par 1, on obtient {1, √−1, −1, −√−1}, qu'on peut appeler le cercle unité si on veut ; sur chacun de ces exemples successifs, on peut vérifier que le birapport des quatre points dans l'ordre dans lequel je les ai écrits vaut toujours −1. Avec un peu de patience, on peut déterminer les 30 cercles à travers les 10 points de K∪{∞}, et se convaincre qu'il y a bien 12 cercles à travers chaque point donné, 4 cercles à travers chaque paire de points distincts, et un unique cercle à travers chaque triplet de points distincts.

La construction du paquet de cartes de Tribble (rien à voir avec Star Trek ) est alors la suivante : on crée q²+1 cartes, une pour chaque élément de la « sphère » K∪{∞}, on choisit q³+q symboles au total, un pour chaque « cercle » tel que défini précédemment, et chaque carte porte q²+q symboles, un pour chaque cercle passant par ce point. Puisque trois points quelconques définissent un unique cercle, trois cartes distinctes auront toujours un unique symbole en commun (et deux cartes ont q+1 symboles communs). C'est ce que j'ai fait ci-dessus pour q=5 (puis j'ai randomisé la correspondance cercles↔symboles, et l'ordre des symboles sur chaque carte).

Je suppose que cette construction est (au moins approximativement) optimale en un certain sens, mais je ne sais pas en quel sens… En tout cas, ce que j'ai raconté est une construction classique (due apparemment à Witt en 1938 — je n'ai pas vérifié la référence).

On pourrait aussi se poser la question suivante. Maintenant, je veux faire un jeu de cartes dans lequel toutes les cartes portent des symboles en un certain nombre d'emplacements, le même nombre pour chaque carte (cette fois, une carte peut porter deux symboles identiques en des emplacements différents), de façon que trois cartes quelconques aient toujours exactement un emplacement commun portant le même symbole sur les trois cartes. (Formellement, donc, les cartes sont des mots de même longueur sur un certain alphabet, et on demande que trois mots quelconques aient toujours un unique emplacement auquel elles ont le même symbole.) Y a-t-il une façon intelligente, mathématiquement élégante, hautement symétrique et/ou vaguement optimale de s'y prendre ? Je sais faire avec q cartes, q symboles, et q² emplacements par carte : il suffit, si j'appelle F le corps fini à q éléments, de mettre à l'emplacement (a,b) de la carte x (où a,b,x appartiennent tous à F) le symbole ψ(x) + a·x² + b·x, où ψ:F→F est une fonction quelconque (on peut prendre 0 mais ça ne donne pas une réponse très intéressante : toutes les cartes ont juste le symbole 0 en commun à l'emplacement (0,0)). Il est facile de vérifier, en résolvant un système linéaire et en utilisant un discriminant, que si x₀,x₁,x₂ sont trois cartes quelconques, il existe a,b uniques tels que a·(x₁²−x₀²) + b·(x₁−x₀) = ψ(x₀)−ψ(x₁) et a·(x₂²−x₀²) + b·(x₂−x₀) = ψ(x₀)−ψ(x₂), ce qui est la propriété voulue. Je ne sais pas si on peut faire avec une construction plus jolie ou plus symétrique et/ou plus efficace.

Par ailleurs, il est naturel de se demander alors ce qui se passe si on veut que quatre cartes ou plus aient toujours un symbole en commun : si on ajoute la contrainte que chaque symbole apparaisse sur le même nombre de cartes, cela revient à chercher un système de Steiner, mais je ne crois pas qu'on connaisse de constructions jolies ou efficaces de familles infinies de systèmes de Steiner semblable à la construction que j'ai présentée ci-dessus ou à la construction des plans projectifs (cependant, je n'y connais essentiellement rien). Si on veut juste la propriété que r cartes quelconques aient toujours un unique symbole en commun, sans rien demander de plus, à part la construction triviale consistant à mettre un symbole en commun à toutes les cartes et éventuellement des symboles uniques par ailleurs, on peut reprendre ce que je propose au paragraphe précédent, et qui se généralise à ψ(x) + a_r·x^r + ⋯ + a₁·x, et ensuite utiliser cette valeur ainsi que les a_i eux-mêmes, pour désigner le symbole : ceci donne une construction avec q cartes, et q^r symboles par carte parmi q^r+1 ; on peut certainement faire mieux, mais comme je ne sais pas très bien ce que « mieux » veut dire, je n'irai pas plus loin.