Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #51 - 10-12-2013 12:13:55

Neotenien
Passionné de Prise2Tete
Enigmes résolues : 43
Messages : 56

Estimatio

Ah ok JackV, pout ton problème, N est le nombre de solutions ?

Eh bien dans ce cas, à ton ami prof de math, tu pourrais demander qu'il demande à son logiciel d'énumérer l'ensemble des possibilités (k) et l'ensemble des solutions (P)... et dès qu'on a (P/(P+1))^k<0.01, tu peux considérer que N=P+1 avec une incertitude de moins de 1%.

(Ceci dit, on peut aussi faire une incertitude à 5 % en faisant (P/(P+1))^k<0.05 )

#0 Pub

 #52 - 10-12-2013 12:23:15

Neotenien
Passionné de Prise2Tete
Enigmes résolues : 43
Messages : 56

eqtimation

Ah et puis si effectivement les pièces sont inversibles, pour celles qui n'ont pas de pièces équivalentes une fois retournée, le nombre de pièces doit être augmenté de 1 à chaque fois. Si on arrive à N pièce, one fois ceci fait, le nombre maximal de possibilités est de N!

Mais apparemment, à chaque solution, il reste des pièces hors tapis... du coup, peut-être essayer différentes combinaisons dont la somme des surfaces donne la surface de l'hexagone (ça diminuera les possibilités).

 #53 - 10-12-2013 12:25:18

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

estimatoon

Jackv, ce sont toujours les mêmes pièces au départ comme dans Trapézomino 34 ?
Quand tu dis, je trouve les solutions complètement au hasard, c'est avec une vraie procédure de tirage aléatoire, ou c'est toi qui fait un peu comme tu le sens ?

@dylasse : Jack ne peut pas savoir combien d'autocollants (ou d'assiettes) composent la collection.

 #54 - 10-12-2013 19:56:48

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 562

Esttimation

Titou, en supposant que l'ensemble des vignettes Panini sont empaquetées de façon aléatoire et que les vignettes sont imprimées en quantités égales, on doit pouvoir déduire un intervalle de confiance à partir des informations données, non ?
Bon, l'encadrement doit être énorme et au final, il ne nous avancera pas à grand chose, mais c'est possible ?

 #55 - 10-12-2013 22:46:33

Neotenien
Passionné de Prise2Tete
Enigmes résolues : 43
Messages : 56

Estimatin

Nombrilist : ben voilà!!

Alors me dire que "grace à prise2tete on a la solution" je ne l'ai vu clairement nulle part dans les réponses jusqu'à maintenant. Il est certain que la probabilité (N-1)/N intervient.

Ma solution est une ébauche à partir d'éléments que l'auteur de l'énigme peut avoir pour résoudre son problème. Mais ma solution suppose que le nombre de tirage doit être au moins de 5 fois N.

Après, ce qu'il faudrait, c'est trouver une corrélation entre l'écart qu'il y a entre P et T, avec T.

Il faudrait pouvoir établir des dénombrements voir les cas ou le nombre de tirage est inférieur à N, égal à N ou supérieur à N.

Dans le problème initial, j'ai l'impréssion qu'il y a trop d'inconnus (3 je pense) pour pouvoir résoudre simplement.

Je vais voir ce qui se passe si N=4 en voyant pour une cardinalité différente du nombre de tirages.

 #56 - 10-12-2013 23:45:46

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 301
Lieu: Montargis

Estimatiion

Sur un plan purement mathématique sans liaison avec un quelconque jeu, est-il possible de résoudre ce problème en estimant N ou pas? Connaissant T et P !

 #57 - 11-12-2013 11:00:10

Neotenien
Passionné de Prise2Tete
Enigmes résolues : 43
Messages : 56

Esimation

dylasse a écrit:

Sans Paul et Mickey, le problème posé par JackV est bien posé et il vaut mieux critiquer nos réponses que corriger l'énoncé pour qu'il colle à nos réponses !!!

Pour ceux qui ne sont pas des fans de Trapezominos, voici 2 autres exemples où on connait T et P mais pas N.

"A Noël, Jack reçoit une cinquantaine de pochettes Panini de la collection Foot2013 (ou La Reine des Neiges, on s'en fiche !), qui contiennent chacune environ 6 autocollants.
Il n'a pas reçu l'album pour les coller, mais ouvre quand même toutes les pochettes et fait la liste des différentes images trouvées, en entourant celles qu'ils voient pour la seconde fois : il compte 225 images (liste 1, T) et 69 images entourées (liste 2, P).
Grâce à P2T, Jack sait combien d'autocollants différents composent la collection. Et toi ?"

"Jack est un grand expert d'assiettes alsaciennes, c'est pourquoi son ami Lucien l'appelle pour lui dire qu'il a fait une découverte étrange dans le grenier de tante Hortense. Il a trouvé une série d'assiettes dans des vieux cartons, récupérés une à une dans des brocantes. Lucien a repéré 20 modèles différents dont 15 qui sont en double ou plus. Jack lui dit, c'est dommage, je pense qu'il te manque 2 assiettes pour avoir une série complète... Jack a pu affirmé ça grâce à P2T, mais toi qu'en penses-tu ?"

Que ce soit les Panini, les assiettes ou le problème à JackV, dans tous les cas, on connait le nombre de tirages (en supposant que JackV ait pris soin de compter le nombre de demandes qu'il a faites).

Donc le problème se résume bel et bien à ma résolution.

Maintenant en ce qui concerne le problème posé par JackV, il semble évident que ça se résume au fait de savoir
"Quel probabilité j'ai que P=T pour N donné, connaissant T après avoir effectué un certain nombre de tirage".

Pour N=2 par exemple, si la population est {1,2}
on peut avoir, pour k=4, en tirage
1111 P=1 T=1
1121 P=2 T=1
1211 P=2 T=1
2111 P=2 T=1
On a également
2222
2212
2122
1222
Avec les mêmes P et T que ci dessus.

Pour les autres tirages (les 8 autres) on a P=2 et T=2.
Donc pour N=2, avec 4 tirages, on n'a QUE 50% de chance d'avoir P=T avec P=2.

Que se passe-t-il si le nombre de tirages augmente pour N=2 ?

On aura une probabilité de plus en plus faible que le dernier élément non tiré (2 par exemple) n'apparaisse pas ET ON EN REVIENT A MA METHODE!

Je vous laisse essayer avec N=3.... bon courage.

Maintenant je comprend pourquoi ce site s'appelle "prise2tete" si dès qu'on propose une solution fiable (aidé par 3 autres membres de prise2tete qui ont bien compris également que le problème pouvait être vu autrement) on est envoyé boulé comme ça sans même avoir fait les simulations! hmm

 #58 - 11-12-2013 13:11:05

Jackv
Elite de Prise2Tete
Enigmes résolues : 34
Messages : 1998
Lieu: 94110

Estimatioon

Au risque de me répéter, je rappelle que pour moi, le but du problème tel que je l'ai posé, c'est d'avoir une petite idée du nombre total de solutions différentes N, sachant que j'en ai déjà repérées T dont un certain nombre P ont été trouvées plusieurs fois et sachant d'autre part que je n'ai pas noté le nombre total de tirages.

Tout l'intérêt de la question consiste à obtenir ce résultat avec un nombre total de tirages (donc T également) restant très petit devant N, tout en précisant si possible l'indice de confiance que l'on peut lui accorder (sous forme d'écart quadratique moyen par exemple).

Je rappelle aussi qu'on ne peut pas retourner les trapézominos.

 #59 - 11-12-2013 14:40:41

Neotenien
Passionné de Prise2Tete
Enigmes résolues : 43
Messages : 56

Estimatio

Ton problème ne peut avoir de solution avec un indice de confiance assez fort si tu pars sur ces hypothèses (à savoir nombre de tirages < N). Sans doute avec moins de 10%.

Tu aurais dû noter le nombre de tirages! Rien ne t'empêchais de le faire. (D'ailleurs, puisque tu sais combien apparaissent au moins 2 fois, pourquoi ne connais-tu pas le nombre total des solutions que tu as demandé ? Je trouve ça curieux...). Il te reste à redémarrer de 0 alors...

Mais le fait que tu aies P assez grand (une vingtaine je crois ?) avec ton T proche de P, signifie que ton N n'est peut être pas si loin de P.

Quoi qu'il en soit, normalement pour les autres problèmes "du même genre" cités, on connait forcément le nombre de tirages.

Je termine donc ma méthodologie afin d'avoir une solution clé en main.

Pour ce qui est donc, de connaitre le cardinal d'une population N qu'on ne connait pas, qui est un tirage avec remise. Soit P le nombre d'éléments différents obtenus au bout de k tirage.

Si on veut être sûr de N à 95 %, il suffit que

(P/(P+1)^k) < 0.05

Soit ln(P/(P+1)^k) > ln (0.05) = -3 (environ)
(On change le sens de l'inégalité car on passe de + à - enfin je ne suis pas arrivé à le montrer mathématiquement...)

k.ln(P/P+1)) > -3

ln (P/(P+1)) > -3/k

Si on obtient ce résultat au bout de k tirages, on peut estimer à 95% que N=P ou N=P+1.

 #60 - 11-12-2013 18:32:57

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

Estimationn

La question posée initialement est relativement claire.
N'en déplaise à certains, je n'ai pas vu de démonstration prouvant qu'il n'y a pas de solution à cette question, juste des "c'est évident" ou des "à vu de nez".
Je n'ai pas non plus vu (ni écrit, oui je sais ! tongue) de démonstration répondant pleinement à la question.
J'ai proposé 2 formules, la 1ère T(N,K) ayant semble-t-il été démontrée par d'autres, la 2nde P(N,K) n'étant qu'une conjecture de ma part sur la base de valeurs simples. Avec mon peu de méthode, je n'ai pas réussi à aller plus loin, en particulier à cause de puissances aussi grandes. En tout cas, il semble qu'on puisse obtenir 2 équations complexes à 2 inconnues, ce qui peut tout aussi bien donner une infinité de solutions qu'un nombre restreint...

Je pense que ceux qui souhaitent répondre à une autre question ont toute liberté d'ouvrir une autre énigme.


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #61 - 12-12-2013 11:44:31

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 679

Estmiation

[TeX]N[/latex] est le nombre de pions dans le grand sac.

On note [latex]T_n[/latex] et [latex]P_n[/latex] les valeurs moyennes de [latex]T[/latex] et [latex]P[/latex] au bout de [latex]n[/latex] tirages.

On a
[latex]T_1=1, \quad P_1=0[/TeX]
[TeX]T_n=T_{n-1}+\frac{N-T_{n-1}}{N}[/TeX]
[TeX]P_n=P_{n-1}+\frac{T_{n-1}-P_{n-1}}{N}[/TeX]
Si l'on connaît [latex]N[/latex], on peut donc calculer par récurrence [latex]T_n[/latex] et [latex]P_n[/latex] pour tout [latex]n[/latex] donné.

On cherche [latex]N[/latex] et [latex]n[/latex] qui minimisent [latex]\sqrt{(T_n-1750)^2+(P_n-105)^2}[/latex].

On trouve alors
[TeX]N=15194[/TeX][TeX]n=1859[/latex] (nombre de tirages)

[latex]T_n=1749.82860[/TeX][TeX]P_n=104.813490[/TeX]
Voilà !

 #62 - 12-12-2013 14:00:32

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 301
Lieu: Montargis

estimatiin

Excellent boulot masab cool
J'avais précédemment mis [latex]T_n=N-N*(1-\frac{1}{N})^n[/latex]  , cette formule est aujourd'hui validée par ton calcul smile

 #63 - 12-12-2013 14:37:26

Jackv
Elite de Prise2Tete
Enigmes résolues : 34
Messages : 1998
Lieu: 94110

Esstimation

Bravo et merci à masab big_smile qui devrait clore cette discussion avec ce calcul qui rejoint les résultats déjà proposés par dylasse, enigmatus, kossi_tg et lui-même (non, pas Lui-meme, lui-même lol !).

 #64 - 12-12-2013 20:02:34

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 562

sEtimation

D'accord, mais ça, ce sont les espérances. Dans la pratique, tu as probablement autant de chance que N= 15 194 que N se situe aux alentours de 12 000 ou 18 000, voire même 10 000 ou 20 000.

 #65 - 13-12-2013 21:59:59

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

estimarion

Ouais, très intéressant, Masab ! smile
Mais comment as-tu fait le calcul final ?


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #66 - 14-12-2013 15:47:48

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 679

Estimatino

On se donne un intervalle pour [latex]N[/latex], par exemple [latex]15150\leq N\leq 15220[/latex].

On se donne un intervalle pour [latex]n[/latex], par exemple [latex]1850\leq n\leq 1900[/latex].

On fait un programme qui calcule [latex]T_n[/latex] et [latex]P_n[/latex] pour tous [latex]N[/latex] et [latex]n[/latex] dans ces intervalles.

On trouve ainsi  [latex]N[/latex] et [latex]n[/latex] minimisant [latex]\sqrt{(T_n-1750)^2+(P_n-105)^2}[/latex].

 #67 - 15-12-2013 20:59:46

Neotenien
Passionné de Prise2Tete
Enigmes résolues : 43
Messages : 56

Etimation

Il y a quand même un gros problème!! C'est que tu estimes N dès le départ!! Comme si tu savais que N valait 1750 au carré.

Mais si N vaut, mettons, 2000 ?

n doit être le nombre de tirages j'imagine ?

Et si tu changes n, je doute que les résultats de T et P soient les mêmes pour ta méthode des moindres carrés. Ce que tu fais n'est qu'une estimation de la fonction décrite par P suivant N ?

Ce qu'on cherche est, je le rappelle, une "bonne" estimation de N d'après P et T.

Mais estimer N avec un nombre de tirage largement inférieur à N c'est du pure délire!

Si n est à environ 1/3 de N, disons, 30, comment pouvez vous "estimer" que N soit 90 plus facilement qu'il ne vaut 120 si on n'a que P=12 et T = 9 ?

De plus tu fais intervenir 3 variables ici! Donc il faudrait un graphe en 3 dimensions ou un tableau en 3 dimensions (Avec P, T et N) et estimer N=f(P,T). Mais pour faire ceci, il fait faire k sondages pour chaque N or Jackv n'a qu'un seul sondage.

De plus ta formule avec les racines carrée, pas besoin d'expérience!! Puisque la racine carrée est nulle (et donc minimale) pour Tn=1750 et Pn=105.

C'est vraiment du n'importe quoi. Et dire que Jackv croit qu'il s'agit de la bonne méthode.. Bah il va se casser les dents tant pis !!!

Ma méthode était la bonne! (D'autant qu'elle remplit toutes les conditions initiales)

Mais au passage j'ai juste fait une petite erreur...

Si au bout de n tirages, on n'a que P différents, la probabilité (P/P+1)^n donne la probabilité pour que le (N-1)eme élément ne soit pas tiré, et si cette probabilité est assez faible, alors on estime que P=N à ce moment là (et non pas P=N+1)..

Bon, j'espère qu'on va nous accorder du crédit quant à notre méthode. Je suis multidiplomé de l'enseignement supérieur aux CNAM en Informatique (bac+4) et en mathématiques (Licence maths appliquées option calcul scientifique).

 #68 - 16-12-2013 12:33:25

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

estimatuon

Neotenien a écrit:

Je suis multidiplomé de l'enseignement supérieur aux CNAM en Informatique (bac+4) et en mathématiques (Licence maths appliquées option calcul scientifique).

Je ne sais pas si quelqu'un te l'a demandé ou si c'est juste pour te la jouer. Dans les deux cas, je crois qu'on s'en balance big_smile


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #69 - 16-12-2013 18:55:36

Jackv
Elite de Prise2Tete
Enigmes résolues : 34
Messages : 1998
Lieu: 94110

EEstimation

Neotenien : estimer N avec un nombre de tirages largement inférieur à N c'est du pure délire!

Mais c'est tout simplement la réalité de mon problème !!!

Masab me dit N vaut environ 15000. Bon.
Je suis parfaitement conscient que cela signifie que N a simplement des chances non négligeables de se situer entre 10000 et 20000, mais cela répond parfaitement à la question que je posais.

Si je dois attendre d'avoir trouver 99 % des solutions pour dire que N a 95 % de chance de valoir une certaine valeur, compte tenu du nombre assez restreint de nouvelles solutions que je trouve chaque mois et qui va aller en diminuant de plus en plus, je crois que je serais mort avant d'avoir la réponse lol !

 #70 - 16-12-2013 20:49:55

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 562

estimatoon

Au final, il aurait fallu demander une moyenne et un intervalle de confiance à x%. Mais bon, comme tu l'as dit, au pif, entre 10 000 et 20 000, ça me paraît correct.

 #71 - 16-12-2013 21:10:32

Neotenien
Passionné de Prise2Tete
Enigmes résolues : 43
Messages : 56

zstimation

Jackv a écrit:

Neotenien : estimer N avec un nombre de tirages largement inférieur à N c'est du pure délire!

Mais c'est tout simplement la réalité de mon problème !!!

Masab me dit N vaut environ 15000. Bon.
Je suis parfaitement conscient que cela signifie que N a simplement des chances non négligeables de se situer entre 10000 et 20000, mais cela répond parfaitement à la question que je posais.

Si je dois attendre d'avoir trouver 99 % des solutions pour dire que N a 95 % de chance de valoir une certaine valeur, compte tenu du nombre assez restreint de nouvelles solutions que je trouve chaque mois et qui va aller en diminuant de plus en plus, je crois que je serais mort avant d'avoir la réponse lol !

Pas forcément!! Si tu n'as actuellement que 20 solutions différentes et que tu as eu une centaine de réponse en tout, tu peux estimer que N vaut 20 avec 95% de chances. D'après ma formule, le nombre de tirages pour avoir 95 % de chance est à peu près de 5 fois T (suivant les valeurs de N, ça varie entre 4.5 et 5 fois).

Alors qu'avec la méthode T et P, je pense que le nombre de tirages pour avoir une probabilité élevée que N=P avec R=T-1 doit être de l'ordre de N²/2.

 #72 - 16-12-2013 22:22:09

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

Estimmation

Ce qui suit n'a peut-être pas grand intérêt, d'autant moins que je ne sais pas donner de preuve. Mais je me coucherai sans doute mieux après l'avoir couché noir sur blanc ! lol

Avec T fixe (1750) et P ponctuellement fixe, on doit pouvoir donner une moyenne de N pour chaque valeur de P, sur la base de la courbe de la proba que N=n.
- Pour P=0, on a par exemple :
    - une proba nulle que N < 1750,
    - une proba infime que N =1750 (1749!/1750^1749),
    - une proba qui croit d'abord avec N (pas de preuve mais on s'imagine à peu près que 1751 ou 3500 ou 15000 donneraient plus),
    - une proba qui tend vers 0 (quelle est la proba que N=10^1000 ? Je dirais à peu près 10^-1000).
   Je ne sais pas donner la moyenne (T^2 ?) ni le N maximisant la proba. La moyenne pourrait d'ailleurs valoir l'infini dans ce cas.
- Pour P=105 :
    - une proba nulle que N < 1855,
    - une proba assez faible que N =1855,
    - une proba qui croit d'abord avec N,
    - une proba qui tend vers 0.
pourrait d'ailleurs valoir l'infini dans ce cas.
- Pour P=1750 ça me paraît moins évident.


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #73 - 16-12-2013 22:31:20

Jackv
Elite de Prise2Tete
Enigmes résolues : 34
Messages : 1998
Lieu: 94110

estimatiin

Je te rappelle que je dispose, non pas de 20 mais de 1750 solutions différentes dont 105 sont apparues plusieurs fois et un point, c'est tout.
J'ai du effectuer moins de 1900 tirages, et non pas 5 fois N.
Pour obtenir les 95 % de chance dont tu parles, il faudrait que j'effectue de 50 000 à 100 000 tirages, et je peux t'assurer que je serais mort bien avant.

Que peux-tu faire de concret avec mes données hormis me dire que la fiabilité du résultat obtenu sera insuffisante (cela, ce n'est pas ton problème) ?

 #74 - 16-12-2013 22:37:11

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,467E+3

estimatipn

Je pense que si un triple est sorti, c'est utile de le savoir...

Si ce n'est pas le cas et qu'un triple sortait avant ta mort, je suis persuadé que d'autres options de recherche verraient le jour. Peut-être est-il possible de creuser dans ce sens ?

 #75 - 16-12-2013 22:52:15

Neotenien
Passionné de Prise2Tete
Enigmes résolues : 43
Messages : 56

stimation

Jackv a écrit:

Je te rappelle que je dispose, non pas de 20 mais de 1750 solutions différentes dont 105 sont apparues plusieurs fois et un point, c'est tout.
J'ai du effectuer moins de 1900 tirages, et non pas 5 fois N.
Pour obtenir les 95 % de chance dont tu parles, il faudrait que j'effectue de 50 000 à 100 000 tirages, et je peux t'assurer que je serais mort bien avant.

Que peux-tu faire de concret avec mes données hormis me dire que la fiabilité du résultat obtenu sera insuffisante (cela, ce n'est pas ton problème) ?

Ah oui tant que ça ? Oulala tu as bien du courage!

Si tu as effectué eu 1750 solutions et seulement 105 en double... avec 1900 solutions données dis-tu ? Curieux comme distribution statistique... A mon avis, N est très très grand. Même pas 10% des solutions sortis en double...

Bon avec ces données... Puisque tu as les k tirages... Ca me permet d'y voir un peu plus clair déjà.

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Mots clés des moteurs de recherche

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
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete