Dobble simplifié : 7 cartes, 3 symboles chacune

Swingmustard

Bonjour

Soit $E=[\![1,7]\!]=\lbrace1, 2, 3, 4, 5, 6, 7\rbrace$ et $\mathscr{P}_3(7)=\mathscr{P}_3(E)$ l'ensemble des parties de $E$ à trois éléments.

Appelons Dobble toute partie $D\subset\mathscr{P}_3(7)$ telle que $\#D=7$ et $\forall A, B \in D, \#A\cap B=1$.

Par exemple, $D_0=\lbrace123, 145, 246, 347, 167, 257, 356\rbrace$ est un Dobble.

Pour $A=123$ et $B=347$,on a $\#A\cap B=\#\lbrace3\rbrace=1$.

Deux questions indépendantes.

1) Soit $\sigma$ le 7-cycle $(1234567)$, qui change 1 en 2, 2 en 3, etc ... et 7 en 1.
Trouver les $\lbrace a, b, c\rbrace\subset E $ tels que $\lbrace abc,\, \sigma(abc),\, \sigma^2(abc),\, ... ,\, \sigma^6(abc)\rbrace$ soit un Dobble.

2) Puisque $5\times7=35=\begin{pmatrix}7\\3\end{pmatrix}=\#\mathscr{P}_3(7)$, j'ai eu envie de chercher une partition de $\mathscr{P}_3(7)$ en cinq Dobbles.
Inutilement. Montrer qu'il n'existe même pas trois Dobbles disjoints deux à deux.
Amicalement,
Swingmustard

Math Coss

3) il existe 168 permutations des 7 points qui stabilisent les cartes du Dobble. (Suggestion : écrire les entiers de $\mathcal D_0$ en base deux.)

Swingmustard

Merci @Math Coss, you made my day !

$D_0=\lbrace123, 145, 167, 246, 257, 347, 356\rbrace$

1, 2 et 3 peuvent rester inchangés par l'identité, par des doubles transpositions comme $(45)(67)$.

$123$ reste stable par des doubles 3-cycles comme $(123)(465)$, et des permutations comme $(12)(4576)$.

$123$ peut être transformé en $145$ par des 7-cycles comme $(1425673)$.

Je crois dénombrer ainsi $1+21+56+42+24=144$ permutations.

Tu peux me donner un coup de main (quels sont mes 24 oublis ?) et le coup de grâce : quel rapport avec la base 2 ?

Amicalement,

Swingmustard

Math Coss

Une tout autre façon de compter : 1 peut être envoyé sur n'importe quel point ; 2 sur n'importe quel autre point -- on a ainsi 42 choix et l'image de 3 est déterminée -- et il reste à trouver deux choix entre deux pour terminer la description de la permutation.

Swingmustard

Je n'avais pas oublié de catégorie, mais comme on pouvait s'y attendre, les $24$ 7-cycles se languissaient de leurs $24$ inverses, d'où $$1+21+56+42+48=168$$

Bravo pour ton point de vue $$7\times6\times1\times4\times1\times1\times1=168$$ dont je ne comprends pas encore le $4$ ("deux choix entre deux", dis-tu ?) Je le valide, bien sûr ... plutôt 5040 fois qu'une !!!

(L'idée géniale de départ : laisser gambader 1 et 2 où bon leur plaît.

Se rappeler à l'ordre du Dobble et de ta contrainte, qui fixe l'image de 3 avec celles de 1 et 2 dans un seul élément du Dobble.

Retour au batifolage pour l'image de 4 : que tu aies su que les 4 points restants étaient vraiment possibles, c'est ça qui m'échappe.

Image de 5 : fixée par celle de 145 par exemple, comme celle de 3 l'était par celle de 123.

Pareil pour celles de 6 et 7.)

1) Quel rapport avec la base 2 ?

2) Aurais-tu des lumières pour ma question 2 initiale : j'aimerais bien, là aussi, une méthode moins bourrin que la mienne, peut-être avec quelque chose comme le principe des tiroirs, pour travailler plus sur les cardinaux que sur les éléments de Dobbles.

Amicalement,

Swingmustard

GaBuZoMeu

Bonsoir,

On peut avantageusement penser au plan de Fano, le plan projectif sur $\Z/2\Z$. Un Dobble est une structure de plan de Fano (les éléments du Dobble sont les droites du plan). Une transformation du plan de Fano qui conserve l'alignement (autrement dit le stabilisateur du Dobble) est une homographie, et le groupe des homographies du plan de Fano est $\mathrm{GL}_3(\Z/2\Z)$, dont on sait qu'il est d'ordre 168. Rappelons aussi qu'une homographie du plan est déterminée par les images de quatre points dont aucun n'est aligné avec deux autres, qui peuvent être quatre points quelconques pourvu qu'aucun ne soit aligné avec deux autres

Math Coss

Voici une représentation efficace de ce « mini-Dobble » avec deux numérotations des sommets : une en base dix, l'autre en base deux (avec des zéros à gauche pour avoir trois chiffres en tout). On va interpréter ces triplets comme des éléments de $\mathbf{F}_2^3$.

Cette structure combinatoire est connue sous le nom de plan de Fano. Elle est formée de toutes les droites de l'espace vectoriel $\newcommand{\F}{\mathbf{F}}\F_2^3$ de dimension $3$ sur le corps à $2$ éléments $\F_2$. Vu que sur $\F_2$ il n'y a qu'un élément non nul, une droite est simplement un vecteur non nul (et le vecteur nul)... Les cartes du mini-Dobble sont les plans de $\F_2^3$, représentées ici par les « droites » du dessin (trois côtés, trois médianes et un cercle circonscrit). Relation clé (due à la coplanarité) : sur chaque « droite », un vecteur est la somme des deux autres. Propriété des droites : par $2$ points (parmi les $7$) passe une unique droite (qui contient $3$ points). Cela fait du plan de Fano un système de Steiner $S(2,3,7)$.

Pour ce qui est des permutations qui préservent la structure, voici deux visions.

La plus élémentaire : on envoie $1$ sur le point que l'on veut (par exemple $1$...) puis $2$ sur un point différent du premier (par exemple $2$) : l'image de $3$ est forcée : c'est le troisième point de la droite passant par $1$ et $2$ (dans l'exemple : $3$). Partant, il faut déterminer les images des quatre derniers points. L'image de $6$ est l'un d'entre eux. Ceci choisi, $7$ est le dernier point de la droite $(16)=\{1,6,7\}$ donc l'image de $7$ est déterminée ; $5$ le dernier de $(36)=\{3,5,6\}$ donc son image est déterminée ; $4$ est le dernier point de $(26)=\{2,4,6\}$ donc son image est déterminée. Au maximum, $7\times6\times4$ possibilités. On se convainc comme on peut que toutes fonctionnent.

Plus élaboré : toute application linéaire bijective de $\F_2^3$ dans lui-même permute les vecteurs non nuls et donc les cartes du mini-Dobble. Pour déterminer une telle bijection linéaire, il suffit de choisir une base, c'est-à-dire les colonnes de la matrice de ladite application. Pour cela, on choisit la première colonne au hasard ($7$ choix) ; on choisit la deuxième colonne non colinéaire à la première, c'est-à-dire différente de la première ($6$ choix) ; on choisit enfin la troisième colonne hors du plan engendré par les deux premiers (lequel contient $|\F_2^2|=4$ éléments donc trois éléments non nuls, ce qui laisse $7-3=4$ choix). Au bilan : $|\mathrm{GL}_3(\F_2)|=7\times6\times4=168$.

GaBuZoMeu

Bonsoir @Math Coss,

Une coquille dans ta dernière ligne : lire $7\times 6\times 4$.

(coquille corrigée pendant que j'écrivais).

Math Coss

Pour résumer, l'action de $\mathrm{GL}_3(\F_2)$ sur les $7$ vecteurs non nuls de $\F_2^3$ donne un morphisme vers $\mathfrak{S}_7$ qui est une surjection sur les permutations qui préservent le mini-Dobble.

Je n'ai pas d'idée particulière pour la question 2 mais voici une interprétation intéressante des éléments d'ordre $7$ (les $7$-cycles dans la version permutation). Un espace vectoriel intéressant de dimension $3$ sur $\F_2$, c'est « le » corps $\F_8$ à huit éléments (avec des guillemets parce qu'il y a plein d'ensembles que l'on peut munir d'une structure de corps à huit éléments mais que tous ces corps sont isomorphes). Une réalisation de ce corps est $\F_2[X]/(X^3+X+1)$. Si on note $b$ la classe de $X$, on a donc $b^3=b+1$ (ne pas oublier que $-1=1$) et les éléments de $\F_8$ possèdent une unique expression $a_0+a_1b+a_2b^2$ avec $(a_0,a_1,a_2)\in\F_2^3$. La multiplication par $b$ est $\F_2$-linéaire et c'est une permutation d'ordre $7$ : \begin{align*}b^k&\hphantom{\;=}\;\text{expression}\ *b^2+*b+*&\text{coordonnées}&&\text{numéro}\\1&=1&(0,0,1)&&1\\b&=b&(0,1,0)&&2\\b^2&=b^2&(1,0,0)&&4\\b^3&=b+1&(0,1,1)&&3\\b^4&=b^2+b&(1,1,0)&&6\\b^5&=b^3+b^2=b^2+b+1&(1,1,1)&&7\\b^6&=b^3+b^2+b=b^2+1&(1,0,1)&&5\\b^7&=b^3+b=1&(0,0,1)&&1\end{align*}En résumé, la multiplication par $\beta$ induit le $7$-cycle $(1243675)$.

Math Coss

Merci @GaBuZoMeu pour la coquille et une version rapide de ce que j'étais en train d'écrire.

Quant au Dobble normal, c'est la même chose en remplaçant le corps à $2$ éléments par le corps à $7$ éléments.

Swingmustard

@Math Coss, @GaBuZoMeu : merci pour vos messages. 
Je me familiarise avec l'aspect algèbrique de l'histoire, en écrivant les matrices des permutations que j'ai recensées.
J'ai pris pour base 4, 2, 1, pour sa ressemblance avec la base canonique 100, 010, 001 de $\mathbb{F}_2^3$.
La double transposition $(45)(67)$ ?
Confectionnons sa matrice avec les trois images de 4, 2, 1, qui sont 5, 2, 1.
Pour être assuré du résultat, j'applique la matrice aux quatre autres points. (Il faut juste s'apprendre à lire la base 2 verticalement.)
$\begin{pmatrix}1&0&0\\0&1&0\\1&0&1\end{pmatrix}\begin{pmatrix}1&1&0&1\\1&0&1&1\\0&1&1&1\end{pmatrix}=\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&1&0\end{pmatrix}$ : 6, 5, 3, 7 ont bien pour images 7, 4, 3, 6: ça roule.
$(123)(465)$ ? La matrice a pour colonnes 6, 3, 2.
$\begin{pmatrix}1&0&0\\1&1&1\\0&1&0\end{pmatrix}\begin{pmatrix}1&1&0&1\\1&0&1&1\\0&1&1&1\end{pmatrix}=\begin{pmatrix}1&1&0&1\\0&0&0&1\\1&0&1&1\end{pmatrix}$.
$(12)(4576)$ ? Colonnes images de 4, 2, 1 : 5, 1, 2.
$\begin{pmatrix}1&0&0\\0&0&1\\1&1&0\end{pmatrix}\begin{pmatrix}1&1&0&1\\1&0&1&1\\0&1&1&1\end{pmatrix}=\begin{pmatrix}1&1&0&1\\0&1&1&1\\0&1&1&0\end{pmatrix}$.
$(1425673)$ ? Les images de 4, 2, 1 sont 2, 5, 4.
$\begin{pmatrix}0&1&1\\1&0&0\\0&1&0\end{pmatrix}\begin{pmatrix}1&1&0&1\\1&0&1&1\\0&1&1&1\end{pmatrix}=\begin{pmatrix}1&1&0&0\\1&1&0&1\\1&0&1&1\end{pmatrix}$.
Déjà un peu au courant de l'aspect géométrique de l'affaire, je pense qu'une des raisons pour lesquelles l'indication "base deux" de Math Coss n'a quand même pas fait tilt dans mon esprit est que $|\mathbb{F}_2^3|=8$ me paraissait "un de trop". C'est ballot de ma part.
De beaux dessins de Tilman Piesk dans l'article de Wikipédia sur le plan de Fano illustrent le Groupe des symétries et confirment mon laborieux classement.
Pour info et si on arrive un peu à suivre en allemand, taper DorFuchs Dobble : même initiation à la géométrie projective, et un lien que je n'ai pas rencontré ailleurs (par exemple dans le papier d'Images des mathématiques) avec les carrés gréco-latins.
Toujours pas d'aide pour (2) : Montrer qu'il n'existe même pas trois Dobbles disjoints ?
Amicalement,
Swingmustard

Math Coss

Une remarque vaguement amusante : pour un bloc $\{a,b,c\}$ codé par les entiers entre $1$ et $7$, on a $a+b=c$ si on numérote convenablement ($c$ = le plus grand) ; si on code par un triplet dans $\F_2^3$, on a $a+b=c$ ou, ce qui revient au même, $a+b+c=0$ pour toute numérotation.

Swingmustard

Prends-tu un bloc dans $D_0$ ?
Si oui, 356 ?
Amicalement,
Swingmustard

Math Coss

Ah ben oui, flûte, ça marchait presque mais pour calculer $3+5$, c'est-à-dire $11+101$, il y a une retenue qui fait planter la remarque. C'est précisément la clé de la remarque (même si elle se révèle fausse) : à cette exception près (me semble-t-il), les additions en jeu n'ayant pas de retenue (en base deux), elles se font à l'identique dans $\Z$ et dans $\F_2^3$.

Swingmustard

Bonjour,

4) Combien existe-t-il de Dobbles ?

(Ceux que @Math Coss appelle mini-Dobbles : éléments de $\mathscr{P}_3(7)$.)

Indication : leur nombre est inférieur à 35.

Amicalement,

Swingmustard

GaBuZoMeu

Ça c'est très facile : $30= 7!/168$.

Swingmustard

1) Merci @GaBuZoMeu !

Pour moi qui suis allé jusqu'à en redouter $35\times18\times2=1260$,

avant une cure amaigrissante $5\times6=30$, ce ne le fut pas ...

Pour toi, "Il n'existe pas trois Dobbles disjoints deux à deux", est-ce facile ou très facile à démontrer ?

Mes cogitations concernant les intersections entre les trente ont mené à ce dessin.

On y voit les 35 cartes disponibles pour fabriquer des Dobbles.

Des patates permettraient sûrement de visualiser les trente Dobbles, mais je ne m'y suis pas encore risqué.

Non coloriées : les $3\times4=$ douze cartes qui ne seront dans aucun Dobble contenant 123.

Huit parce qu'elles ont une paire commune avec 123, quatre parce qu'elles sont disjointes avec 123.

En jaune : les $35-5-12=18$ que l'on peut rencontrer dans un Dobble contenant 123.

Un triplet intérieur, comme 147, 247, 356, est commun à des Dobbles contenant les extrémités de la grande branche sur laquelle il se trouve, et le sommet "opposé" : je veux dire 126, 125 et 123, plus faciles à voir qu'à décrire.

Un triplet extérieur, comme 145, 245, 367, est commun à des Dobbles contenant 123, 126 = son adjacent après le triplet, et 127 = le sommet opposé à 123 et 126.

Ça me paraît une bonne base pour achever, mais je vois que je n'y arrive pas sans aide.

2) Tant que j'y suis, un lemme dont @Math Coss ou toi pourriez me donner votre avis sur la démonstration.

Soit $D$ un Dobble. Toute partie à deux éléments est présente dans exactement une des 7 cartes qui constituent $D$.

Démonstration.

Chaque carte (= combinaison de trois entiers distincts) contient trois paires.

Deux cartes quelconques de $D$ ont, par définition du Dobble, exactement un entier en commun, donc jamais une paire d'entiers en commun.

Puisque $D$ est constitué de 7 cartes, celles-ci contiennent un total de $7\times \begin{pmatrix}3\\2\end{pmatrix}=21$ paires distinctes.

Or dans $[\![1,7]\!]$, il n'y a que $\begin{pmatrix}7\\2\end{pmatrix}=21$ paires distinctes.

Le "donc" délicat pour moi (évidence ? Bergers ? Tiroirs ?) : "donc" toute paire est présente dans $D$.

Amicalement,

Swingmustard

Math Coss

Le fait que toute paire intervienne dans $D$ est une propriété d'auto-dualité du système de Steiner $S(2,3,7)$, qui est un plan projectif.

La version combinatoire, tu l'as : il y a $21$ paires distinctes qui apparaissent sur une des cartes parmi les $21$ paires qui existent : toute paire existante apparaît donc – deux ensembles finis emboîtés l'un dans l'autre et qui ont le même cardinal sont égaux (ont les mêmes éléments).

Pour la version algébrique, il faut se rappeler que les points sont les droites vectorielles (privées de l'origine ; c'est une façon compliquée de dire les choses parce qu'une droite contient seulement un vecteur non nul... mais c'est utile) et les cartes correspondent aux plans (un plan dans $\F_2^3$, ce sont trois vecteurs dont l'un est la somme des deux autres). Or un plan a une équation. Par exemple, la carte $145$ correspond au plan contenant $001$, $100$ et $101$ ; si on numérote les coordonnées, il a pour équation $y_2=0$ ; on peut aussi le représenter par l'équation \[\begin{pmatrix}y_1\\y_2\\y_3\end{pmatrix}\cdot\begin{pmatrix}0\\1\\0\end{pmatrix}=0,\quad\text{où}\ \begin{pmatrix}y_1\\y_2\\y_3\end{pmatrix}\cdot\begin{pmatrix}z_1\\z_2\\z_3\end{pmatrix}=y_1z_1+y_2z_2+y_3z_3.\] L'orthogonalité par rapport à cette forme bilinéaire permet d'identifier les plans et les vecteurs de $\F_2^3$. Un petit tableau : \[\begin{array}{c|c|c|c|c}\text{carte}&\text{vecteurs}&\text{équation}&\text{vecteur orthogonal}&\text{numéro}\\\hline123&001,\ 010,\ 011&y_1=0&100&4\\145&001,\ 100,\ 101&y_2=0&010&2\\246&010,\ 100,\ 110&y_3=0&001&1\\347&011,\ 100,\ 111&y_2+y_3=0&011&3\\167&001,\ 110,\ 111&y_1+y_2=0&110&6\\257&010,\ 101,\ 111&y_1+y_3=0&101&5\\356&011,\ 101,\ 110&y_1+y_2+y_3=0&111&7\end{array}\]Pour tous $k$ et $l$, le vecteur $k$ appartient à la droite $l$ SSI le vecteur $l$ appartient à la droite $k$ (ici, droite = « droite » au sens de ce message). En effet, cela se traduit par l'orthogonalité du vecteur correspondant à $k$ et de celui correspondant à $l$.

Bref : dans un Dobble, on sait que deux cartes ont exactement un symbole commun ; dualement deux symboles appartiennent à une et une seule carte. C'est le propre des plans projectifs sur les corps finis. Il existe par ailleurs des plans projectifs finis non auto-duaux.

Swingmustard

Merci beaucoup @Math Coss .

Je ne soupçonnais ni l'orthogonalité ni l'existence de plans projectifs finis non auto-duaux.

Et l'inclusion de deux ensembles finis de même cardinal est bien ce que je cherchais à formuler.

Je réalise que je voudrais écrire la formule de Poincaré pour les Dobbles.

Est-il possible que la première différence soit négative ?

Par "première différence", j'entends : la somme des cardinaux privée de la somme des cardinaux des intersections de deux ensembles.

Je demande cela car il serait dommage de continuer si j'ai déjà une erreur de calcul.

$$|\bigcup_{i=1}^{30} D_i|=\sum_{1\leqslant i\leqslant 30}|D_i|-\sum_{1\leqslant i<j\leqslant 30}|D_i\cap D_j|+\textrm{etc}...$$

Secret espoir : que la formule s'arrête quand on prend l'intersection de 6 Dobbles, qui est de une carte, et ce quelle que soit la carte.

Auquel cas on aura peut-être bien $$35=30\times7-\sum_{1\leqslant i<j\leqslant 30}|D_i\cap D_j|+...-...+...-35$$

Je renomme $D_0$ en $D_1$, et j'appelle $\mathscr F=\lbrace D_1, D_2, ... , D_6 \rbrace$ la famille des six Dobbles qui contiennent la carte 123.

Je range les $D_i$ en 5 familles : de 123, 124, 125, 126, 127.

a) J'ai constaté à la main qu'à l'intérieur de $\mathscr F$, les intersections de $D_1$ avec chacun des membres donnent 3 fois 3 cartes, 2 fois 1 carte.

Je me dis que ça nous fait $\dfrac{(3\times3+2\times1)\times6}{2}=33$ cartes, à multiplier par 5 familles.

b) Comptons les intersections de deux Dobbles venant de familles distinctes.

Je commence par les intersections de $\mathscr F$ avec $D_7$ (membre de la famille de 124).

Je trouve 1 fois 3 cartes, 3 fois 1 carte, 2 fois 0 carte.

Vu les symétries de la situation, j'en déduis $(1\times3+3\times1)\times6=36$ cartes d'intersection pour les paires de Dobbles dont l'un est dans $\mathscr F$ et l'autre dans cette deuxième famille.

J'arrive à mon problème d'intuition heurtée par $30\times7-(33\times5+36\times\begin{pmatrix}5\\2\end{pmatrix})=210-(165+360)<0$.

Faut-il : dire "la formule n'est pas terminée, d'autres termes vont redresser la barre", ou plutôt chercher l'erreur ?

Amicalement,

Swingmustard

Math Coss

Le calcul brutal semble donner $525=165+360$ pour le terme incriminé.

Swingmustard

Merci pour la confirmation, @Math Coss.

a) Je me suis convaincu que mon "intuition qu'une première différence (dans König) ne peut être négative"  est erronée, à l'aide de $\lbrace12, 13, 14, 15, 16, 17\rbrace$, qui donne $2\times6-\begin{pmatrix}6\\2\end{pmatrix}+\begin{pmatrix}6\\3\end{pmatrix}-\begin{pmatrix}6\\4\end{pmatrix}+\begin{pmatrix}6\\5\end{pmatrix}-\begin{pmatrix}6\\6\end{pmatrix}=12-15+20-15+6-1=7$ avec $12-15=-3<0$.

Est-ce que quelqu'un propose un exemple avec la même simplicité, mais où l'on ne serait pas obligé d'aller si loin dans les intersections ?

b) En  tout cas, "la formule n'est pas terminée, d'autres termes vont redresser la barre", et ces termes vont me faire transpirer, je crains.

Actuellement pour la réunion de deux familles $\mathscr F$ et $\mathscr {F'}$, j'en suis à $$84-102+76-39+12-2$$ confirmé par le fait que ces deux familles font appel à $29$ cartes.

Amicalement,

Swingmustard

P. S. Pour affronter les intersections de trois Dobbles, j'ai numéroté les cartes ainsi : 123 = A, 124 = B, 125 = C, 126 = D, 127 = E, 145 = 1 etc... jusqu'à 567 = 30. Sauf erreur, j'obtiens ceci pour trois des cinq familles, appelées désormais $\mathscr F_A$, $\mathscr F_B$ et $\mathscr F_C$.

\[\begin{array}{c|ccccccccc|ccccccc}D_1&A&1&2&3&4&5&6&~~~~~~~~~~~~~~~~~~~~~&D_7&B&2&4&5&19&20&21\\D_2&A&1&2&7&8&9&10&\phantom{aaaaaaaaaaaaaa}&D_8&B&2&8&9&19&22&23\\D_3&A&3&4&11&12&13&14&\phantom{aaaaaaaaaaaaaa}&D_9&B&8&13&18&22&24&25\\D_4&A&5&6&15&16&17&18&\phantom{aaaaaaaaaaaaaa}&D_{10}&B&5&16&18&21&24&26\\D_5&A&7&8&13&14&17&18&\phantom{aaaaaaaaaaaaaa}&D_{11}&B&9&12&16&23&26&27\\D_6&A&9&10&11&12&15&16&\phantom{aaaaaaaaaaaaaa}&D_{12}&B&4&12&13&20&25&27\end{array}\]

\[\begin{array}{c|ccccccc}D_{13}&C&2&7&10&20&21&28\\D_{14}&C&2&3&6&22&23&28\\D_{15}&C&10&11&16&21&24&29\\D_{16}&C&3&11&13&22&24&30\\D_{17}&C&6&16&17&23&27&29\\D_{18}&C&7&13&17&20&27&30\end{array}\]

Swingmustard

Bonsoir,

Sur deux familles, les $76$ cartes-intersections de trois Dobbles venaient de $$\begin{pmatrix}6\\3\end{pmatrix}\times2+3~\textrm{intersections}~\times6~\textrm{Dobbles de la deuxième famille}~\times(2\times1)~\textrm{arrangements des 2 familles}~=40+36$$ qui dénombre celles venant de trois dobbles d'une même famille, puis celles pour deux dans une, un dans l'autre.

À l'équivalent pour six familles $$\begin{pmatrix}6\\3\end{pmatrix}\times6+3\times6\times(6\times5)~\textrm{arrangements des 2 familles}~=120+180~\textrm{HALTE ! Double erreur}$$

EDIT Corrigeons, avec le bon nombre cinq de familles, pas six. $$\begin{pmatrix}6\\3\end{pmatrix}\times5+3\times6\times(5\times4)~\textrm{arrangements des 2 familles}~=100+360$$ Pfff, en plus le $3\times6\times(6\times5)\neq180$ ! EDIT

il convient d'ajouter les intersections venant de trois familles distinctes. Je regarde les tableaux : EDIT 3 $2$ EDIT, $13, 16$ jouent le jeu (vérifions : il s'agit de $167, 267, 345$ qui, effectivement, n'ont rien d'incompatible avec $123, 124, 125$. Présents dans deux Dobbles par famille (pour les trois familles énumérées), tous trois contribuent chacun pour $2^3=8$ "3-combinaisons de Dobbles" .

Ce $3\times8=24$ est à multiplier par $\begin{pmatrix}5\\3\end{pmatrix}=10$ combinaisons de familles.

Je mise donc sur 120+180+240=540 EDIT $100+360+240=\boxed{700}$ EDIT comme troisième terme dans la formule de König.

1ère bonne raison d'arrêter ici : l'intersection de 4 Dobbles me paraît encore plus pénible que ce que je viens de m'infliger, halte au masochisme.

2ème bonne raison : peut-être @Math Coss ou un autre artiste de l'algèbre, de la combinatoire et ou de la programmation peut-il/veut-il nous donner un coup de main pour achever la formule (et la corriger, si besoin).

3ème bonne raison : si par hasard la formule de König est d'une quelconque utilité pour répondre à ma question initiale ("Non existence de trois Dobbles deux à deux disjoints ?"), les intersections de plus de trois Dobbles ne semblent franchement pas pertinentes.

 Amicalement,

Swingmustard

Math Coss

Je n'ai rien d'intelligent à dire mais la force brute peut suffire. Le code suivant doit montrer qu'il n'existe pas de triplets de Dobbles deux à deux disjoints.

sage: D0 = [[1,2,3],[1,4,5],[2,4,6],[3,4,7],[1,6,7],[2,5,7],[3,5,6]]
sage: G = SymmetricGroup(7)
sage: H = PGL(3,2)
sage: H.is_subgroup(G)
True
sage: C = G.cosets(H)
sage: Cr = map(lambda u: u[0],C)
sage: len(Cr)
30
sage: DD = [map(lambda d: sorted([s(k) for k in d]),D0) for s in Cr]   # les 30 Dobbles
sage: DD
[[[1, 2, 3], [1, 4, 5], [2, 4, 6], [3, 4, 7], [1, 6, 7], [2, 5, 7], [3, 5, 6]],
 [[1, 2, 3], [1, 4, 5], [2, 4, 7], [3, 4, 6], [1, 6, 7], [2, 5, 6], [3, 5, 7]],
 [[1, 2, 3], [1, 4, 6], [2, 4, 5], [3, 4, 7], [1, 5, 7], [2, 6, 7], [3, 5, 6]],
 [[1, 2, 3], [1, 4, 6], [2, 4, 7], [3, 4, 5], [1, 5, 7], [2, 5, 6], [3, 6, 7]],
 [[1, 2, 3], [1, 4, 7], [2, 4, 5], [3, 4, 6], [1, 5, 6], [2, 6, 7], [3, 5, 7]],
 [[1, 2, 3], [1, 4, 7], [2, 4, 6], [3, 4, 5], [1, 5, 6], [2, 5, 7], [3, 6, 7]],
 [[1, 2, 4], [1, 3, 5], [2, 3, 6], [3, 4, 7], [1, 6, 7], [2, 5, 7], [4, 5, 6]],
 [[1, 2, 4], [1, 3, 5], [2, 3, 7], [3, 4, 6], [1, 6, 7], [2, 5, 6], [4, 5, 7]],
 [[1, 2, 4], [1, 3, 6], [2, 3, 5], [3, 4, 7], [1, 5, 7], [2, 6, 7], [4, 5, 6]],
 [[1, 2, 4], [1, 3, 6], [2, 3, 7], [3, 4, 5], [1, 5, 7], [2, 5, 6], [4, 6, 7]],
 [[1, 2, 4], [1, 3, 7], [2, 3, 5], [3, 4, 6], [1, 5, 6], [2, 6, 7], [4, 5, 7]],
 [[1, 2, 4], [1, 3, 7], [2, 3, 6], [3, 4, 5], [1, 5, 6], [2, 5, 7], [4, 6, 7]],
 [[1, 2, 5], [1, 3, 4], [2, 3, 6], [3, 5, 7], [1, 6, 7], [2, 4, 7], [4, 5, 6]],
 [[1, 2, 5], [1, 3, 4], [2, 3, 7], [3, 5, 6], [1, 6, 7], [2, 4, 6], [4, 5, 7]],
 [[1, 2, 5], [1, 3, 6], [2, 3, 4], [3, 5, 7], [1, 4, 7], [2, 6, 7], [4, 5, 6]],
 [[1, 2, 5], [1, 3, 6], [2, 3, 7], [3, 4, 5], [1, 4, 7], [2, 4, 6], [5, 6, 7]],
 [[1, 2, 5], [1, 3, 7], [2, 3, 4], [3, 5, 6], [1, 4, 6], [2, 6, 7], [4, 5, 7]],
 [[1, 2, 5], [1, 3, 7], [2, 3, 6], [3, 4, 5], [1, 4, 6], [2, 4, 7], [5, 6, 7]],
 [[1, 2, 6], [1, 3, 4], [2, 3, 5], [3, 6, 7], [1, 5, 7], [2, 4, 7], [4, 5, 6]],
 [[1, 2, 6], [1, 3, 4], [2, 3, 7], [3, 5, 6], [1, 5, 7], [2, 4, 5], [4, 6, 7]],
 [[1, 2, 6], [1, 3, 5], [2, 3, 4], [3, 6, 7], [1, 4, 7], [2, 5, 7], [4, 5, 6]],
 [[1, 2, 6], [1, 3, 5], [2, 3, 7], [3, 4, 6], [1, 4, 7], [2, 4, 5], [5, 6, 7]],
 [[1, 2, 6], [1, 3, 7], [2, 3, 4], [3, 5, 6], [1, 4, 5], [2, 5, 7], [4, 6, 7]],
 [[1, 2, 6], [1, 3, 7], [2, 3, 5], [3, 4, 6], [1, 4, 5], [2, 4, 7], [5, 6, 7]],
 [[1, 2, 7], [1, 3, 4], [2, 3, 5], [3, 6, 7], [1, 5, 6], [2, 4, 6], [4, 5, 7]],
 [[1, 2, 7], [1, 3, 4], [2, 3, 6], [3, 5, 7], [1, 5, 6], [2, 4, 5], [4, 6, 7]],
 [[1, 2, 7], [1, 3, 5], [2, 3, 4], [3, 6, 7], [1, 4, 6], [2, 5, 6], [4, 5, 7]],
 [[1, 2, 7], [1, 3, 5], [2, 3, 6], [3, 4, 7], [1, 4, 6], [2, 4, 5], [5, 6, 7]],
 [[1, 2, 7], [1, 3, 6], [2, 3, 4], [3, 5, 7], [1, 4, 5], [2, 5, 6], [4, 6, 7]],
 [[1, 2, 7], [1, 3, 6], [2, 3, 5], [3, 4, 7], [1, 4, 5], [2, 4, 6], [5, 6, 7]]]
sage: D0perp = [D for D in DD if all(d not in D0 for d in D)]
sage: D0perp
[[[1, 2, 4], [1, 3, 6], [2, 3, 7], [3, 4, 5], [1, 5, 7], [2, 5, 6], [4, 6, 7]],
 [[1, 2, 4], [1, 3, 7], [2, 3, 5], [3, 4, 6], [1, 5, 6], [2, 6, 7], [4, 5, 7]],
 [[1, 2, 5], [1, 3, 6], [2, 3, 4], [3, 5, 7], [1, 4, 7], [2, 6, 7], [4, 5, 6]],
 [[1, 2, 5], [1, 3, 7], [2, 3, 6], [3, 4, 5], [1, 4, 6], [2, 4, 7], [5, 6, 7]],
 [[1, 2, 6], [1, 3, 4], [2, 3, 5], [3, 6, 7], [1, 5, 7], [2, 4, 7], [4, 5, 6]],
 [[1, 2, 6], [1, 3, 5], [2, 3, 7], [3, 4, 6], [1, 4, 7], [2, 4, 5], [5, 6, 7]],
 [[1, 2, 7], [1, 3, 4], [2, 3, 6], [3, 5, 7], [1, 5, 6], [2, 4, 5], [4, 6, 7]],
 [[1, 2, 7], [1, 3, 5], [2, 3, 4], [3, 6, 7], [1, 4, 6], [2, 5, 6], [4, 5, 7]]]
sage: [D for D in D0perp if all(d not in D0 and d not in D0perp[0] for d in D)]
[]
sage: all([D for D in D0perp if all(d not in D0 and d not in D0perp[0] for d in D)] == [] for k in range(8))
True

Swingmustard

Tu nous fais rêver !

Il faut absolument que je m'instruise, au lieu de gribouiller d'interminables listes.

Encore merci, @Math Coss et chapeau pour la fausse modestie ;-)

En conclusion provisoire, je m'étais fait ma conviction sur la presque démonstration suivante.

(Tellement j'espérais un raisonnement sur les cardinaux ... que je n'ai pas voulu rédiger les "éliminations" à fond.)

À une permutation près, un premier Dobble est $$\lbrace 123,\, 14a,\, 1bc,\, 24b,\, 2ac,\, 34c,\, 3ab\rbrace$$Je pense qu'une autre permutation peut ramener (sauf que c'est peut-être un peu gonflé, d'affirmer ça *) un Dobble disjoint du premier à $$\lbrace 124,\, 13b,\, 1ab,\, 23a,\, 2bc,\, 34b,\, 4ac\rbrace$$ Par éliminations (trop de ratures pour recopier, c'est pas malin), un troisième candidat commençait par $12b,\, 134,\, 1ac,\, 23c,\, 24a$.

Et se terminait par $3ab,\, 4bc$, avec le problème que $3ab$ fait déjà partie du premier Dobble.

* Ou pas. Exhiber deux Dobbles disjoints est déjà un peu délicat, mais quand on en trouve deux, je me sens assez à l'aise (tant il y a de symétrie dans l'histoire) pour prétendre qu'ils peuvent être considérés comme représentatifs de toutes les paires disjointes de Dobbles.

Amicalement,

Swingmustard

P. S. Enhardi par la force brute de @Math Coss, et parce qu'avec @GaBuZoMeu, ils m'ont bien fait transpirer sur les permutations, je me demande quelle jolie phrase mieux tournée que "moyennant quelques permutations, le problème est résolu" pourrait accompagner le tableau suivant, qui part du principe que si trois Dobbles sont candidats à être deux à deux disjoints, le minimum syndical consiste à ce que les deux premiers soient disjoints (ici $D_1$ et $D_9$), et à appartenir à trois familles distinctes, par exemple celles de A, B, C.

\[\begin{array}{c|ccccccc|c}D_1&A&1&2&3&4&5&6&D_1\cap D_i \neq \emptyset\textrm{ ou } D_9\cap D_i\neq \emptyset\\D_9&B&8&13&18&22&24&25&\textrm{à cause de}\\\hline D_{13}&C&2&7&10&20&21&28&2\\D_{14}&C&2&3&6&22&23&28&2,\, 3,\, 6,\, 22\\D_{15}&C&10&11&16&21&24&29&24\\D_{16}&C&3&11&13&22&24&30&3,\, 13,\, 22,\, 24\\D_{17}&C&6&16&17&23&27&29&6\\D_{18}&C&7&13&17&20&27&30&13\end{array}\]

GaBuZoMeu

Bonjour,

Sauf erreur, étant donné un Dobble, il n'y en a que 8 qui sont disjoints de lui (autrement dit, 22 y compris lui-même qui partagent au moins un élément). J'obtiens ça par la formule du crible.

Swingmustard

Bonjour @GaBuZoMeu ,

Dans un (a), j'ai dit qu'à l'intérieur d'une famille, il n'y a pas de Dobbles disjoints. Puis :

b) Comptons les intersections de deux Dobbles venant de familles distinctes.

Je commence par les intersections de $\mathscr F$ avec $D_7$ (membre de la famille de 124).

Je trouve 1 fois 3 cartes, 3 fois 1 carte, 2 fois 0 carte.

J'arrive donc au même résultat que toi en disant "il existe $4$ familles qui ne contiennent pas $D_7$, d'où $4\times2=8$ Dobbles disjoints avec lui".

Si tu veux bien, deux questions.

1) Je trouverais insuffisante ma démonstration, tant que je n'invoquerais pas les permutations. Comment rédigerais-tu cette partie (le recours aux permutations pour généraliser une observation limitée) ?

2) Comment est-ce que tu "obtiens ça par la formule du crible" (= de Poincaré, je sais qu'on parle de la même formule) ?

D'ailleurs, si tu l'as en entier, ne nous fais pas languir ;-)

Ah, je réalise que tu n'as pas dit sur quelle réunion d'ensembles tu l'appliques : peut-être autre chose que les trente Dobbles.

EDIT - Je voulais dire  : "autre chose que les trente-cinq cartes" - EDIT

EDIT rageur - non, je ne devais pas me corriger : la famille d'ensembles que je considère est bien celle des trente Dobbles.

J'ai seulement été troublé (et ai encore appris quelque chose, merci) en voyant, dans le message suivant, @GaBuZoMeu travailler sur une famille à laquelle je ne m'attendais pas : je crois que ses ensembles sont, une fois son Dobble fixé : l'ensemble des Dobbles avec au moins une droite donnée en commun, l'ensemble des Dobbles avec au moins deux droites données en commun, l'ensemble des Dobbles avec trois droites données au moins en commun. Je crois qu'il n'a pas besoin de préciser "concourantes", car si elles ne le sont pas, seul le Dobble fixé réussit à avoir autant en commun. Je trouve d'autant plus intéressante sa manière de faire, que d'ordinaire on calcule P(vide) par P(au moins 1), et que là il réussit à faire plutôt l'inverse, grâce au crible. EDIT

Amicalement,

Swingmustard

GaBuZoMeu

Je fixe un Dobble.

Je compte les Dobbles différents qui partagent une droite donnée : 5

Je compte les Dobbles différents qui partagent deux droites données : 1

Je compte les Dobbles différents qui partagent trois droites concourantes données : 1

Et c'est tout.

Formule du crible : $7\times 5 - 21\times 1 + 7\times 1 = 21$.

Swingmustard

Merci de recauser droites : j'en tire une présentation plus courte de mon $5\times6=30$ Dobbles.

$123,\, 124,\, 125,\, 126,\, 127$ engendrent cinq familles distinctes.

Dans le triangle+médianes+cercle qui représente si joliment le plan de Fano, alignons sur l'horizontale les nombres $1$, $2$ et $3$.

Ensuite il FAUT certes placer $4$, mais peu importe où : dans les quatre positions libres, il sera "alignable" avec $1$, $2$ et $3$.

Le placement de $4$ ne fixe rien pour la suite, raison pour laquelle on comptera $1$ choix,

et non pas $4$ choix comme les quatre positions libres nous incitent à le faire.

Quant à placer $5,\, 6,\, 7$, on a désormais $3!=6$ positions, qui donnent des Dobbles distincts.

D'où le nombre de Dobbles : $5\times1\times3!=30$ Dobbles.

Illustrons le "peu importe la position de $4$" : on a ci-dessous trois (parmi les 6 qui prennent 123 pour horizontale) représentations du même Dobble.

               

Amicalement,

Swingmustard

Swingmustard

Bonjour,

Pour Poincaré, j'avais abandonné trop tôt.

D'une part, content de corriger le message du 3 avril  120+180+240=540 avec le bon décompte $100+360+240=\boxed{700}$ des cartes contenues dans exactement EDIT AU MOINS EDIT trois Dobbles.

D'autre part, mon intuition qu'on arrivait à une partie "cas particulier de la formule du crible, lorsque tous les $A_k$ ont le même nombre $N_k$ de points communs" était bonne (même si ce n'est pas tout-à-fait la bonne manière de le dire), et le $700$ pouvait s'obtenir tellement plus simplement, de la manière suivante.

Crible des 35 cartes par les trente Dobbles :

$$30\times7-525+35\begin{pmatrix}6\\3\end{pmatrix}-35\begin{pmatrix}6\\4\end{pmatrix}+35\begin{pmatrix}6\\5\end{pmatrix}-35\begin{pmatrix}6\\6\end{pmatrix}=35$$

Amicalement,

Swingmustard

P.S. Je maintiens le $30\times7$ pour me rappeler que les ensembles dont je "cherche" le cardinal de la réunion sont les $D_i$.

Je maintiens le $525$ en l'honneur de nos calculs avec @Math Coss

Mais quand je réalise qu'ils sont aussi $$35\begin{pmatrix}6\\1\end{pmatrix}-35\begin{pmatrix}6\\2\end{pmatrix}$$ je ne sais plus s'il faut rire ou s'inquiéter

Swingmustard

Bonsoir,

Puisque j'ai encore du mal à visualiser le Dobble (simplifié, pourtant !), réduisons encore le nombre d'éléments.

Je médite sur ces (au moins) deux manières d'écrire une même formule du crible.

Quatre ensembles à huit éléments chacun.

C'est marrant, mon premier réflexe est encore une fois de compliquer le décompte : j'ai d'abord répondu $$8\times4-\left(\begin{pmatrix}2\\2\end{pmatrix}\times6+\begin{pmatrix}3\\2\end{pmatrix}\times4+\begin{pmatrix}4\\2\end{pmatrix}\times1\right)+\left(\begin{pmatrix}3\\3\end{pmatrix}\times4+\begin{pmatrix}4\\3\end{pmatrix}\times1\right)-1=32-(6+12+6)+(4+4)-1=15$$ Bam. La version à laquelle je n'ai pas pensé en premier est, cette fois-ci (avec les Dobbles, c'est tout de même plus tordu), exactement la version "naturelle" (les cardinaux des intersections deux à deux et trois à trois sont clairement 4 et 2): $$\begin{pmatrix}4\\1\end{pmatrix}\times8-\begin{pmatrix}4\\2\end{pmatrix}\times4+\begin{pmatrix}4\\3\end{pmatrix}\times2-\begin{pmatrix}4\\4\end{pmatrix}\times1=32-24+8-1=15$$ Ah, j'entrevois. Mon dénombrement "maladroit" vient peut-être de ce que je me crois astreint à plus de précision qu'il n'en faut, classant les intersections selon le nombre d'ensembles qui les contiennent, alors qu'on peut grouper, visiblement. $$|A\cap B|=|A\cap C|=|A\cap D|=|B\cap C|=|B\cap D|=|C\cap D|=4$$ et basta. Peu importe que dans $A\cap B$ on ait $e$ appartenant à deux ensembles, $0$ et $1$ à trois, $x$ à quatre. C'était l'affrontement $$(e,\, f,\, g,\, h,\, i,\, j),\, ( 0,\, 0,\, 0,\, 1,\, 1,\, 1,\ 2,\, 2,\, 2,\, 3,\, 3,\ 3),\, ( x,\, x,\, x,\, x,\, x,\, x)\textrm{ vs }(e,\, 0,\, 1,\, x),\, (f,\, 0,\, 2,\, x),\, (g,\, 1,\, 2,\, x),\, (h,\, 0,\, 3,\, x),\, (g,\, 1,\, 2,\, x),\, (j,\, 1,\, 2,\, x)$$ $$6+12+6\textrm{ vs }4\times6$$ J'essaierai dorénavant de penser que a) une bonne formulation est "nombre d'éléments appartenant au moins à deux ensembles",

b) ne pas trop chercher à classer davantage ces éléments.

Amicalement,

Swingmustard

Swingmustard

Bonjour,

1) Le fait que "chaque Dobble contient 7 cartes, en même temps que chaque carte est contenue dans 6 Dobbles" induit une "symétrie très forte" entre Dobbles et cartes.

Pour les intersections, les "cardinaux intermédiaires" s'en trouvent interdits : aucune carte n'est dans exactement 2 (ni 3, ni 4, ni 5) Dobbles.

La symétrie me donne envie d'écrire deux formules de crible : une pour les Dobbles, une pour les cartes.

Frustré par l'absence de visualisation des intersections, due au dépassement du nombre d'ensembles limite (qui, en ce qui me concerne, est 4), je propose le "presque micro-Dobble" que voici.

Considérons les six cartes $12,\, 13,\, 14,\, 23,\, 24,\, 34$.

Notons $123$ le Dobble $\lbrace12,\, 13,\, 23\rbrace$.

Avec les Dobbles $124,\, 134,\, 234$, ça nous fait un total de $4$ Dobbles à $3$ cartes chacun.

Réciproquement, la carte $12$ appartient à $2$ Dobbles : $123,\, 124$.

On retrouve presque l'essence du Dobble : beaucoup de paires de cartes ont un symbole commun, mais attention, trois paires n'en ont aucun.

Les Dobbles n'ont pas cet inconvénient : deux ont toujours une carte commune, trois ou quatre n'ont aucune carte commune.

J'encadre le premier terme, qui sera toujours commun aux deux formules de crible.

$$\boxed{12}=4\textrm{ Dobbles }\times3\textrm{ cartes par Dobble}=6\textrm{ cartes }\times2\textrm{ Dobbles par carte}$$

$$\textrm{ Réunion de tous les Dobbles : }\begin{pmatrix}4\\1\end{pmatrix}\times3-\begin{pmatrix}4\\2\end{pmatrix}\times1+0+0=\boxed{12}-6=6\textrm{ cartes}$$ $$\textrm{ vs Réunion de toutes les cartes : }\begin{pmatrix}6\\1\end{pmatrix}\times2-\left(\begin{pmatrix}6\\2\end{pmatrix}-3\textrm{ doubles paires disjointes }\right)+4+0-0+0=\boxed{12}-12+4=4\textrm{ Dobbles}$$

Je renonce à lier le $4$ à $\begin{pmatrix}6\\3\end{pmatrix}=20$, même si on pourrait chercher.

2) Retour aux 30 Dobbles : j'hésite entre le bluff et la prudence.

a) Bluff

La "symétrie" des 30 Dobbles est "plus forte" que celle du (1), car elle est sous-tendue par la règle stricte de l'unique symbole commun à deux cartes.

Aussi on prétend que les deux formules suivantes sont correctes $$35\begin{pmatrix}6\\1\end{pmatrix}-35\begin{pmatrix}6\\2\end{pmatrix}+35\begin{pmatrix}6\\3\end{pmatrix}-35\begin{pmatrix}6\\4\end{pmatrix}+35\begin{pmatrix}6\\5\end{pmatrix}-35\begin{pmatrix}6\\6\end{pmatrix}=35$$ $$\textrm{ Réunion de tous les Dobbles : }\boxed{210-525+700-525+210-35}=35\textrm{ cartes}$$

$$\textrm{ vs }30\begin{pmatrix}7\\1\end{pmatrix}-30\begin{pmatrix}7\\2\end{pmatrix}+30\begin{pmatrix}7\\3\end{pmatrix}-30\begin{pmatrix}7\\4\end{pmatrix}+30\begin{pmatrix}7\\5\end{pmatrix}-30\begin{pmatrix}7\\6\end{pmatrix}+30\begin{pmatrix}7\\7\end{pmatrix}=30$$ $$\textrm{ Réunion de toutes les cartes : }\boxed{210-630+1050-1050+630-210+30}=30\textrm{ Dobbles}$$

b) Prudence

Le (1) nous met en garde. Continuons de voir les deux formules comme des conjectures. Contrôler un de ces jours le 630, pour commencer.

Qu'en pensez-vous ?

Amicalement,

Swingmustard