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 )

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.

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.

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!

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.

[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à !

Bravo et merci à masab 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 !).

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

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).

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 !

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 !

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.

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) ?

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à.