Écrire une réponse @ Prise2Tete

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

	Forum » Enigmes Mathématiques » Cartes et symboles Écrire une réponse Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide ! Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci. Rédige ton message Nom Courriel \| \| \| \| Upload \| Aide Message [quote=dylasse]Soit un jeu de n cartes où chacune possède m symboles. Nous nous plaçons d’abord dans le cas où il y a m+1 cartes avec le même symbole (S1). Les autres symboles de ces m+1 cartes sont tous différents. Supposons qu’il existe une carte qui ne contient pas S1, elle doit alors posséder un symbole de chacune des m+1 cartes, donc elle doit avoir m+1 symboles. C’est impossible, donc si il y a m+1 cartes avec S1, toutes les cartes possèdent S1 et donc tous les autres symboles sont différents. On a donc en tout x = 1 + (m-1) * n symboles. Pour notre cas de 55 cartes à 8 symboles, il faudrait donc avoir x = 386 symboles différents ! Nous nous plaçons maintenant dans le cas où il n’y a au maximum m cartes qui contiennent le même symbole. Nous pouvons construire un jeu avec m carte qui contiennent S1. Ces m cartes nécessitent 1 + (m-1)m symboles différents. Nous construisons ensuite la suite de ce jeu, sans ajouter de nouveaux symboles, en prenant comme premier symbole des m-1 cartes suivantes un des symboles de la première carte (S2) puis en plaçant une permutation de la matrice (m-1) x (m-1) des symboles des cartes 2 à m (sans le premier S1). On recommence l’opération avec les m-1 symboles de la première carte, ce qui nous fait en tout 1 + (m-1)m cartes, soit autant que de symboles (ce qui est logique puisque chaque symbole se trouve sur m cartes et que chaque carte contient m symboles). Donc le nombre maximal de cartes possible est N = 1 + (m-1)m. C’est le jeu optimisé à m symboles par carte, qui possède x = N = 1+ (m-1) m symboles différents. Pour m=8, ce nombre maximal est donc N = 57. Le jeu de carte de scaff60 ne possédant que n=55 cartes, c’est donc possible que ce soit un jeu de 57 auquel on a retiré 2 cartes, ce qui fait que 15 symboles n’apparaissent que 7 fois et 1 seulement 6 fois (celui en commun des 2 cartes retirées), et tous les autres 8 fois. Montrons maintenant que l’on ne peut pas avoir de solution avec moins de 57 symboles pour un jeu de 55 cartes. On va en fait montrer, d’une manière générale, que si le jeu possède plus de cartes que N – m, alors N symboles sont nécessaires Soit donc un jeu de n cartes où : N – m = m²-2m+1 < n < N Supposons (Hyp1) que le nombre de symboles est x < N = 1 + (m-1)m Supposons (Hyp 2) que chaque symbole n’apparaisse que sur m-1 cartes au maximum, on aurait au maximum x (m-1) symboles sur l’ensemble des cartes, c’est à dire au maximum x * (m-1)/m cartes, soit n <= x (m-1)/m < (1 + (m-1) m) * (m-1)/m = 1 – 1/m + (m-1)² Donc, n < m² - 2m + 1, c’est impossible, donc (Hyp2) est fausse : donc au moins un symbole (S1) apparaît m fois. Sur ces m cartes où S1 apparaît, il y a 1 + m(m-1) symboles différents, ce qui contredit (Hyp1), donc le nombre de symboles différents est >= N, donc au minimum x=N. Pour un jeu qui possède N – m cartes, ou moins, on peut retirer m cartes du jeu optimisé avec le même symbole et donc x = N-1 symboles différents sont suffisants. Si le jeu possède N – m – (m-1) ou moins, on peut retirer du jeu précédent m-1 cartes avec le même symbole (la dernière carte portant ce symbole ayant été enlevée précédemment). Etc… (jusqu’à N – m – (m-1) - … -1) Pour n<=m+1, le nombre de symboles nécessaires est la partie supérieure droite de la matrice suivante (exemple avec n=8), dont le dénombrement est aisé. S01 S02 S03 S04 S05 S06 S07 S08 S01 S09 S10 S11 S12 S13 S14 S15 S02 S09 S16 S17 S18 S19 S20 S21 S03 S10 S16 etc… … S08 S15 S21 S26 S30 S33 S35 S36 Pour m+1 < n <= (m²-3m)/2+1… j’ai pas encore trouvé de formule ! En conclusion : pour m et n donnés, on a les valeurs de x suivantes : Si m²-m+1 < n, alors x = 1+(m-1)n Si m²-m+1-(i+1)m+i(i+1)/2 < n <= m²-m+1 -im+(i-1)i/2 , alors x = m²-m+1-i, pour 0<= i <= m-1 Si n<=m+1, x=nm – (n-1)n/2[/quote] Options Ne pas convertir les émoticônes sur ce message Sécurité Répondez (numériquement) à la petite énigme suivante : Dans une course, vous doublez le 19ème, en quelle position êtes-vous ?* Retour Résumé de la discussion schaff60 21-03-2010 10:10:45 Je viens d'acquérir un petit jeu de cartes qui a cette particularité : Chaque carte a 8 symboles différents. Entre 2 cartes prises au hasard, il y a toujours un et un seul symbole en commun. Le jeu comprend 55 cartes, combien faut-il au minimum de symboles différents pour pouvoir composer ce jeu ? Peut-on trouver une formule plus générale, si on a n cartes comportant chacune m symboles différents, quel est le nombre minimum x de symboles qu'il faut en fonction de m et n ? Un petit exemple si ce n'est pas clair : Avec 4 cartes et 3 symboles par carte il faut 6 symboles différents pour composer le jeu : 1ere carte : A B C 2ème carte : A D E 3ème carte : B D F 4ème carte : C E F Je n'ai pas encore la réponse à ces questions (si ce n'est que je sais de combien de symboles différents est composé mon jeu), mais je compte sur votre perspicacité. Pied de page des forums P2T basé sur PunBB Screenshots par Robothumb © Copyright 2002–2005 Rickard Andersson
Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact