Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#26 07-12-2011 16:25:14

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : Le jeu Set et un calcul de probabilités

Salut,

je pense que j'ai trouvé mon erreur : une même carte peut servir à faire SET pour deux paires distinctes.

Par exemple, la paire 1222 et 2321 est complétée par la carte 3123, mais cette carte complète aussi la paire 3121 et 3122.

Donc dans la procédure pas à pas, j'en enlève trop, d'où l'erreur terminale.

je manque de temps, je finirai ce soir, sauf si d'autres trouvent avant moi, ce qui ne me gène absolument pas.


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#27 07-12-2011 19:18:34

jpp
Membre
Inscription : 31-12-2010
Messages : 1 105

Re : Le jeu Set et un calcul de probabilités

salut à tous

une carte peut meme faire un set avec 40 paires  :[tex]\frac{3^4 - 1}{2}[/tex]

par contre , une paire ne peut s'associer qu'à une seule et unique carte pour faire un set.

                                                                         à plus.

Hors ligne

#28 08-12-2011 17:00:23

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : Le jeu Set et un calcul de probabilités

Salut,

bon, je crois que j'ai trouvé.

1/33 est la moyenne de toutes les probabilités de toutes les configurations possibles de 12 cartes telles que chaque fois, on ne peut faire aucun SET.

Nota : quand je note une carte 1231, cela veut dire que j'ai la forme n°1, le fond n°2, la couleur n°3 et le nombre n°1

le tirage non settable suivant : 1211 2313 2112 1233 1111 2222 2333 2331 3131 1212 2122 a une probabilité de 2,5667 % de se réaliser

le tirage non settable suivant : 1111 1112 1121 1122 1211 1212 1221 1222 2111 2112 2121 2122 a une probabilité de 4,05 % de se réaliser. la proba moyenne ressort à 3,308 %

En continuant et en moyennant, on doit s'approcher du résultat de Fred.

Pour une méthode façon Monte Carlo, je sais par expérience que 10.000 tirages sont insuffisants. Pousser à 50.000, voire 100.000 tirages donne un résultat + précis.


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#29 11-12-2011 03:08:01

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : Le jeu Set et un calcul de probabilités

Bonjour,

Fred nous a collé un problème pas si facile.

J'ai regardé si on pouvait trouver la probabilité des donnes de (N+1) cartes sans SET en connaissant la probabilité des donnes de N cartes sans SET.

J'ai suivi la piste ouverte par freddy : Dans une donne, toute carte qui fait SET (de premier niveau) avec un couple de cartes de la donne doit se retrouver dans le paquet des (81-N) non distribuées et diminue d'autant les candidates à être une carte d'une donne de (N+1) cartes sans SET.

Mais il faut encore réduire le nombre des candidates de toutes les cartes non distribuées qui pourraient faire SET (de deuxième niveau) avec les couples formés en associant une carte SET (de premier niveau) et chaque carte dans une donne de N cartes sans SET.

Ce procédé donne des résultats précis et exacts par dénombrement sur des entiers et me donne des produits de probabilités jusqu'aux donnes de 8 cartes qui confortent très bien (au 1/1000 ème près) mes simulations déjà publiées.

Cette méthode entraîne la répartition des donnes sans SET de N cartes sur plusieurs tailles de paquets de cartes candidates aux donnes sans SET de (N+1) cartes, et cette répartition est encore mal maîtrisée…Pour les donnes de 8 cartes on doit considérer 5 paquets de candidates (de 53, 54, 55 ,56 et 58 cartes) et leur attribuer plus de 2 milliards de donnes de 7 cartes

Il doit y avoir mieux …!

Voici les probabilités pour les donnes de 4 à 8 cartes sans SET :
0,987341772152
0,949367088608
0,875883610061
0,762971871566
0,616607110411 pour autant que cette précision (divisions d'entiers dénombrés) ait un sens…

Cordialement

Hors ligne

#30 11-12-2011 14:39:24

jpp
Membre
Inscription : 31-12-2010
Messages : 1 105

Re : Le jeu Set et un calcul de probabilités

Salut à tous.

mais si on poursuit avec le raisonnement de freddy au #19  alors après la douzième carte, je retire 11 cartes des 14 restantes  il en reste 3 possibles dans le talon pour faire un non set  .

la proba s'écrirait:

[tex]P = \frac{81\times{80}\times{78}\times{75}\times{71}\times{66}\times{60}\times{53}\times{45}\times{36}\times{26}\times{15}\times3}{13!\times\left(_{12}^{81}\right)}\times\left(_{12}^{13}\right) \approx0.0316049..[/tex]

mais là , on est au dessus de [tex]\frac1{32}[/tex]

                                                                                     à plus.

Dernière modification par jpp (11-12-2011 18:08:44)

Hors ligne

#31 11-12-2011 20:29:02

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : Le jeu Set et un calcul de probabilités

Bonsoir,
Voici la valeur précise de la probabilité de NON SET pour les donnes de 7 cartes
:
[tex]\frac{7*8*9*101}{5*11*19*79}=0.6166071104[/tex]

Je détaillerai comment y être parvenu.
Je travaille les probabilités des donnes de 10, 11 et 12 cartes à petites doses...

Cordialement

Edit : donnes de 7 cartes, et non 6

Dernière modification par totomm (12-12-2011 23:48:23)

Hors ligne

#32 11-12-2011 22:47:48

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Le jeu Set et un calcul de probabilités

Bonsoir,

  Je suis impatient de lire la suite de totomm....

Fred.

Hors ligne

#33 12-12-2011 00:58:16

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : Le jeu Set et un calcul de probabilités

Bonsoir,

Je travaille de façon à bien recouper les dénombrements : Il est impossible de traiter ce problème à la main, aussi mes résultats sortent de 2 programmes "compilés" car Python interprété est 60 à 100 fois moins rapide.
En plus il y faut des astuces de programmes et des astuces de raisonnement. Pour traiter les cas de 9 et 10 cartes par donne, j'ai réduit les milliards de donnes en supposant fixées les 2 premières cartes mises sur table : Cela ne modifie pas les proportions étudiées.
La probabilité de NON SET pour 10 cartes par donne est de 0,1694504136 = 4 420 755 144 / 26 088 783 435 (je donne les Entiers bruts exacts en numérateur et dénominateur.
La probabilité de NON SET pour 11 cartes par donne est de 0,0817563222 Je ne l'ai pas encore recoupée avec un dénombrement direct.
Je l'ai en calculant, à partir des donnes de 10 cartes en NON SET, comment se répartissent les cartes non encore distribuées, qui donneront des donnes de 11 cartes en NON SET.
Le tableau de répartition comprend donc 2 colonnes : le nombre de cartes pour quelle quantité de donnes. Le voici :

0,1694504136    prob10 non set pour Donne 10 cartes
30    16 035 084    (Nombre de cartes possibles / 71 restantes) * (nombre de donnes / total donnes) = prob partielle
31    46 399 392   
32    296 819 640   
33    852 930 000   
34    1 313 512 200
35    1 262 336 400   
36    444 888 288   
37    134 762 940   
38    40 940 640
39    11 941 020
44    189 540   
    4 420 755 144 total donnes (= bien celui calculé directement pour les donnes de 10 cartes)
Le produit de prob10 avec la somme des prob partielles donne prob11 avec autant de précision que désiré
0,0817563222 = prob11 non set pour Donne 11 cartes

Il manque donc encore la dernière probabilité !

Cordialement

Hors ligne

#34 12-12-2011 23:47:23

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : Le jeu Set et un calcul de probabilités

Bonsoir,

Pour décourager définitivement qui voudrait trouver une solution simple, voici les probabilités de NON SET en effectuant des donnes de tailles croissantes (toujours la même taille dans une partie)

Noter les nombres premiers de 5 et 6 chiffres qui montrent que seul un ordinateur peut trouver les probabilités exactes...

Probabilité Donnes de 3  cartes Sans SET = 78 / 79 soit : 0.9873417721518988
Probabilité Donnes de 4  cartes Sans SET = 75 / 79 soit : 0.9493670886075949
Probabilité Donnes de 5  cartes Sans SET = 5328 / 6083 soit : 0.8758836100608253
Probabilité Donnes de 6  cartes Sans SET = 88182 / 115577 soit : 0.7629718715661421
Probabilité Donnes de 7  cartes Sans SET = 50904 / 82555 soit : 0.6166071104112409
Probabilité Donnes de 8  cartes Sans SET = 1385334 / 3054535 soit : 0.4535335165581668
Probabilité Donnes de 9  cartes Sans SET = 66275064 / 222981055 soit : 0.29722284702617446
Probabilité Donnes de 10  cartes Sans SET = 37784232 / 222981055 soit : 0.1694504136237045
Probabilité Donnes de 11  cartes Sans SET = 0,0817563222 mais"fraction en Entiers non disponible"

en nombres premiers, 3 cartes : [2, 3, 13]   /  [79]
en nombres premiers, 4 cartes : [3, 5, 5]   /  [79]
en nombres premiers, 5 cartes : [2, 2, 2, 2, 3, 3, 37]   /  [7, 11, 79]
en nombres premiers, 6 cartes : [2, 3, 3, 3, 23, 71]   /  [7, 11, 19, 79]
en nombres premiers, 7 cartes : [2, 2, 2, 3, 3, 7, 101]   /  [5, 11, 19, 79]
en nombres premiers, 8 cartes : [2, 3, 3, 76963]   /  [5, 11, 19, 37, 79]
en nombres premiers, 9 cartes : [2, 2, 2, 3, 3, 3, 306829]   /  [5, 11, 19, 37, 73, 79]
en nombres premiers, 10 cartes : [2, 2, 2, 3, 3, 3, 3, 58309]   /  [5, 11, 19, 37, 73, 79]

Sauf demande, je ne me lancerai pas dans l'accélération de mon programme pour trouver la probabilité exacte avec des donnes de 12 cartes. Il faudrait que j'insère un module en c pur (ou même en assembleur)

Cordialement

Edit : J'ai quand même quelques idées pour encore diminuer la profondeur des dénombrements et bien améliorer les algorithmes.
Ce sera peut-être seulement dans quelques semaines ! Bon Noël à tous !

Dernière modification par totomm (13-12-2011 11:35:39)

Hors ligne

#35 31-12-2011 11:48:59

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : Le jeu Set et un calcul de probabilités

Bonjour,

@ fred : cadeau surprise de nouvelle année :
La probabilité de NON SET pour une donne de 12 cartes est de  0,032302 soit 1 / 30,96
Donc plutôt 1 / 31 que 1 / 33

En valeurs entières : [tex]\frac{ 2^2* 3^5*11^2*2767}{5*7*19*37*71*73*79}[/tex]

Méthode :
Avec la loi de composition SET nous savons :
2 cartes quelconques possèdent UNE et UNE SEULE carte SET
et nous disposons de  3 théorèmes de base : ab=ba ; a(ab) = b ; (ab)(ac) = a(bc)      (Voir Setgame sur Internet)

On ne restreint pas la généralité des configurations en choisissant les 2 premières cartes, sauf à remarquer que les configurations suivantes de 3, 4….cartes ne seront plus équiprobables. Ne seront équiprobables que les tirages d'une carte parmi celles non encore distribuées.

Commençons avec 2 cartes a et b parmi les 81, restent 79 non distribuées dont 78 sont NONSET avec les 2 premières et une i=ab SET avec les 2 premières.
Appelons S(n) le nombre de cartes SET désignées par les cartes sur table. S(2)=1

On peut constituer 78 configurations NONSET de 3 cartes parmi 79 en posant une carte c différente de i.
Appelons NS(n) le nombre de configurations NONSET de n cartes. NS(3)=78

Appelons PnonSet(n) la probabilité des configurations NON SET de n cartes : PnonSet(3) = 78/79
Une nouvelle carte posée désigne autant de nouvelles cartes SET que de cartes déjà sur table sauf si une des nouvelles cartes SET correspond à une carte déjà SET antérieurement

Pour chacune des configurations de 3 cartes, les cartes SET j=ac et k=bc sont différentes de i
En effet si on avait i=j, alors ab=ac entraînerait a(ab)=a(ac) soit b=c qui est  faux par construction.
Conclusion 3 cartes différentes ont 2 à 2 des cartes SET différentes.
La nouvelle  carte posée conduit donc à S(3)=S(2)+2=3

Posons une carte d figurant dans les 78 -S(3) = 75 NONSET des 78 encore en paquet non distribué. PnonSet(4)=PnonSet(3)*75/78=75/79

La nouvelle carte qui vient d'être posée pour une configuration de 4 cartes désigne 3 nouvelles cartes SET ainsi S(4)=S(3)+3=6 SAUF si certaines des nouvelles cartes désignaient une ou plusieurs cartes SET déjà reconnues.
C'est ce qui se produit à partir des configurations de 4 cartes pour lesquelles :
NS(4,1)=117 configurations ne désignent que CS(4,1)=5 cartes SET et
NS(4,2)=2808 configurations désignent CS(4,2)=6 cartes SET.

Suivre les répartitions et en donner les formules devient très vite complexe et l'ordinateur est le bienvenu pour ne pas se tromper.

Pour toute configuration de n cartes on obtient :

Le nombre total de configurations  C(n)=C(n-1)*(82-n) / (n-2) Edit : C(3)=79 ; C(4) =79*78/2=3081
Le nombre de configurations NON SET  NS(n)=Somme(NS(n, i))
D'où PnonSet(n)=NS(n) / C(n)

PnonSet(n)  peut être confirmé par  un calcul sur les probabilités partielles des groupes i
Appelons [tex]Partielle(n,\ i)=\frac{81-n-CS(n, i)}{81-n}*\frac{NS(n, i)}{NS(n)}[/tex]

Alors aussi PnonSet(n)=PnonSet(n-1)* Somme des Partielle(n, i)

La récurrence fait  connaître le résultat des donnes de 12 cartes en ne dénombrant que jusqu'aux donnes de 11 cartes,
ce qui permet de ne pas laisser tourner l'ordinateur pendant des semaines pour obtenir un résultat de dénombrement.
en effet on a aussi [tex]NS(n+1)=\sum{ NS(n,i) *\frac{81-n-CS(n, i)}{n-1}}[/tex]

12 cartes par donne conduit à C(12) = 1 440 680 596 355 et NS(12) = 46 536 833 772
Sans doute y -a-t'il d'autres formules de calcul ?

Aussi, même pour quelques heures, il vaut mieux insérer des sauvegardes sur disque dur dans son programme pour garantir des reprises sûres…

Cordialement

Dernière modification par totomm (31-12-2011 12:47:04)

Hors ligne

#36 01-01-2012 18:45:58

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Le jeu Set et un calcul de probabilités

Salut Totomm,

  Il faut que je me penche là-dessus en détail...

A+
Fred.

Hors ligne

#37 02-01-2018 19:05:15

RobinM34
Invité

Re : Le jeu Set et un calcul de probabilités

Bonjour,
je me permets de déterrer ce vieux sujet en espérant que certains sont encore intéressés par sa résolution.
Autant vous le dire tout de suite : je ne suis pas le providentiel individu qui apportera la solution.

En fait, je suis tombé sur ce post en abordant le problème du Set sous un autre angle : à partir de combien de cartes est-on sûr d'avoir un Set?
en lisant vos solutions (en diagonal certes), je me suis rendu compte qu'elles n'apporteraient pas de réponse à mon problème pour une raison simple : vos calculs font tendre la probabilité d'avoir un Set en augmentant le nombre de cartes vers 0 sans jamais l'atteindre (avant 81).

Hors, je pense que tout le monde à conscience qu'à partir d'un certain nombre de cartes, on est sûr d'avoir un set. Et ce nombre n'est pas très élevé.

Je postule qu'il est de 17. En tout cas on peut trouver des plans de 16 cartes sans set (un plan ne comportant aucun ovale, aucun vert et aucun vide en est un).

Si quelqu'un à la méthodologie pour le prouver, je suis preneur.

voilà ce que je sais :
- il y a une combinaison de 3 parmi 81 assemblages de 3 cartes possibles soit : 85320
- il y a une combinaison de 2 parmi 81, le tout divisé par 3, sets possibles soit 1080. Pour atteindre ce résultat le calcul est simple : pour chaque paire, il y a une et une seule carte permettant de former un set. Je dénombre donc les paires possibles. Je divise par 3 car chaque set aura été dénombré trois fois (une par paire qui le compose).
- il y a donc 1 combinaison sur 79 qui est un Set (85320/1080).

mon raisonnement pourrait consister à dénombrer le nombre de paires (plus une carte) possibles pour 16 cartes. Soit une combinaison de 2 parmi 15 (et non 16 car je dois garder une carte à lui associer sur le plateau). Cela exclue 105 cartes, soit plus que le nombre de cartes dans le paquet. Mon erreur vient bien évidemment du fait que certaines cartes auront été exclues plusieurs fois.

Comment intégrer cette erreur dans mon raisonnement?

Voilà, je ne suis pas sûr de passionner grand monde, mais je pense que mon approche explique les erreurs de vos calculs.

Cordialement

Robin

Pied de page des forums