Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
201 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Dobble

Envoyé par Domi 
Dobble
il y a six années
avatar
Bonsoir à tous :D

Encore un problème auquel je ne trouve pas vraiment de domicile , "algèbre" semble le moins pire .

Sur l'île des maths on propose le jeu suivant appelé dobble : on a une cinquantaine de cartes sur lesquelles figurent 8 motifs . En piochant au hasard deux cartes dans le jeu , on va toujours trouver exactement un motif en commun sur les deux cartes .

Il faut 57 motifs différents pour réaliser le jeu qui va contenir au maximum 57 cartes . Plus généralement avec n motifs par cartes peut-on réaliser un jeu de n(n-1)+1 cartes avec n(n-1)+1 motifs différents ?

Un exemple de jeu avec trois motifs

ABC
ADE
AFG
BDF
BEG
CDG
CEF

On remarquera que chaque symbole figure exactement trois fois sur l'ensemble des cartes .

Bonne recherche !

Domi
Re: Dobble
il y a six années
avatar
Tu connais la réponse, Domi ? Parce que c'est une question que je me suis posée quand mes enfants ont eu ce jeu...
Re: Dobble
il y a six années
avatar
Remplaçons chacun des n symboles bijectivement par un nombre de 0 à n-1.
Ton exemple devient :

0 1 2
0 3 4
0 5 6
1 3 5
1 4 6
2 3 6
2 4 5

En imaginant que ces cartes représentent un nombre écrit en base n, ces nombres sont rangés dans l'ordre croissant.



Edité 1 fois. La dernière correction date de il y a six années et a été effectuée par Sylvain.
Re: Dobble
il y a six années
avatar
Le problème est invariant par permutation des symboles. Donc chaque symbole apparaît le même nombre de fois dans l'ensemble des cartes. Soit l ce nombre. En multipliant le nombre total c de cartes par le nombre de symboles que chaque carte a en propre p, on a cp=l.n où n est le nombre de symboles distincts. Il faut donc montrer que p=l pour en déduire c=n.
Re: Dobble
il y a six années
avatar
Merci Bisam et sylvain pour les réponses .

On voit en effet assez rapidement que pour n places par cartes , le nombre maximum théorique de cartes est n(n-1)+1 , c'est aussi le nombre de motifs dintincts . Je ne sais pas si ce maximum peut toujours être atteint . Il y a d'autres questions ouvertes , par exemple de minimiser le nombre de motifs différents en fixant le nombre de cartes et le nombre de symboles par carte .

J'ai aussi joué à ce jeu avec mes enfants il y a "quelques" années et je me suis toujours demandé pourquoi il manquait deux cartes . D'un autre côté un des intérêts de ce jeu est que l'on peut y jouer même s'il manque des cartes ( ceux qui ont des enfants ou des petits frères et soeurs comprendront ) .

Bonne recherche et bonne journée à tous .

Domi
Alban0
Re: Dobble
il y a six années
Bonjour, le jeu Dobble a été "mathématisé" sur image des maths (un site du CNRS). Il y a aussi un article sorti ou à sortir dans Quadrature. Il existe un lien avec un espace projectif sur un corps fini. D'ailleurs, la version habituelle de Dobble n'est pas complète (au sens où on pourrait rajouter quelques cartes)
Alban0
Re: Dobble
il y a six années
Avec un lien, c'est mieux : [images.math.cnrs.fr]
Re: Dobble
il y a six années
avatar
Merci Alban

Je n'ai fait que survoler l'article mais il semble que la méthode , exposée pour n motifs par carte , ne "marche" que lorsque n-1 est une puissance d'un nombre premier , le cas général reste ouvert .

Il est quand même étonnament riche ce jeu .

Domi



Edité 1 fois. La dernière correction date de il y a six années et a été effectuée par Domi.
Re: Dobble
il y a six années
C'est une application élégante du plan projectif. Soit $K$ un corps fini quelconque. A chaque élément de $\mathbb P^2(K)$ on fait correspondre un symbole (fleur, étoile etc) et à toute droite du plan projectif on fait correspondre une carte sur laquelle figure les symboles correspondant aux points de cette droite.
exemple: quand $K:=\mathbb F_7$ $card(\mathbb P^2(K))=57$ et chaque droite contient $8$ éléments.

Plus généralement si $p$ est premier et $n\in \N^*$ on a un corps fini de cardinal $p^n$ donc $1+p^n+p^{2n}=card(\mathbb P^2(\mathbb F_{p^n}))$ symboles, autant de cartes, et chaque carte contient $p^n+1$ élements (cardinal d'une droite i.e $card (\mathbb F_{p^n} \cup \{+ \infty\})$).
Re: Dobble
il y a six années
avatar
Notons qu'étant donné un entier $n\geq 1$, on ne sait pas conclure quant à l'existence éventuelle d'un plan projectif fini d'ordre $n$ (i.e. un plan projectif dans lequel chaque droite possède $n+1$ points, i.e. un plan projectif à $n^2+n+1$ points). D'ailleurs pour certaines valeurs de $n$, il n'existe pas de plan projectif d'ordre $n$.

Un théorème de Bruck et Ryser montre que si $n$ est congru à $1$ ou $2$ modulo $4$ et si $n$ n'est pas somme de deux carrés, alors il n'y a pas de plan projectif d'ordre $n$.

On sait aussi qu'il n'y a pas de plan projectif d'ordre 10 grâce à des calculs sur ordinateur (cas qui n'est pas couvert par le théorème de Bruck-Ryser)

Lorsque $n$ est une puissance d'un nombre premier, l'argument de Foys montre qu'un plan projectif d'ordre $n$ existe.
Re: Dobble
il y a six années
avatar
Une autre façon de voir les choses mais je doute qu'elle fournisse un modèle intéressant . Pour n donné ( le nombre de symboles par carte ) , on cherche à placer des pions sur une grille de côté n(n-1)+1 , n pions par ligne de façon à ce que sur deux lignes on puisse toujours choisir trois pions formant un triangle rectangle ( les côtés de l'angle droit parallèles à ceux de la grille ) mais jamais quatre formant un rectangle .

[attachment 27323 trianglesrectangles.jpg]

Mon exemple est symétrique par rapport à la première bissectrice , on peut donc remplacer ligne par colonne .

Domi



Edité 1 fois. La dernière correction date de il y a six années et a été effectuée par Domi.


Re: Dobble
il y a six années
Jeu avec $N$ symboles sur chaque carte, $S$ symboles en tout, $C$ cartes. On prend un symbole fixé $s$; on cherche le nombre d'éléments de l'ensemble $C_{s}$ des cartes contenant ce symbole. Si deux cartes le contiennent, ces deux cartes n'ont aucun autre symbole en commun. En fait les groupes de symboles (excepté $s$ qui est commun à toutes) des cartes de $C_{s}$ forment une partition, en parties à $N-1$ éléments, de l'ensemble des symboles (excepté $s$). Le nombre d'éléments de $C_{s}$ vaut donc : $$Card C_{s}=\frac{S-1}{N-1}
$$ On a compté le nombre de cartes contenant un symbole fixé. Si on fait la somme $T$ de ce nombre pour tous les symboles, on obtient d'une part : $$T=SC_{s}=S\frac{S-1}{N-1}$$ et d'autre part, par ce procédé on a compté l'ensemble des cartes, $N$ fois.
On a donc : $$T=NC$$ Donc : $$C=\frac{S(S-1)}{N(N-1)}
$$ Pour $N=8$, et en choisissant $S-1=N(N-1)=56$, on obtient $C=S=57$. Après vérification du jeu, il y avait 57 symboles et 54 cartes (...). Conclusion (confirmée après coup par un étalage des cartes), les concepteurs ont retiré 3 cartes du jeu complet.
Re: Dobble
il y a six années
[erreur dans ce post]



Edité 1 fois. La dernière correction date de il y a six années et a été effectuée par mathatak.
Re: Dobble
il y a six années
avatar
Bonjour Mathatak

La difficulté est de montrer que ce maximum théorique $N(N-1)+1$ peut être réalisé .

Domi

PS : regarde bien sous la banquette , il me semble que tu as perdu une carte :D
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 137 923, Messages: 1 337 605, Utilisateurs: 24 635.
Notre dernier utilisateur inscrit ferdinandbardamu.


Ce forum
Discussions: 17 399, Messages: 168 705.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page