"Philippe 92" <nospam@free.invalid> a écrit dans le message news:
mn.babf7d85cb14b608.22155@free.fr...

...

Bon ! Laissons tomber vos précedentes lignes qui n'ont rien à voir au
problème posé.

Et comment prouver que c'est le meilleur donc.
Une borne inférieure est donné par la "quantité d'information"
Il y a C(100,10) = 17310309456440 répartitions possibles des pièces.
Si une pesée donne a[i] résultats possibles, la quantité
d'information obtenue est au mieux le produit des a[i] (moins si les
informations obtenues sont redondantes).
Il est donc nécessaire que ce produit soit au moins égal au nombre de
répartitions. Soit prod(a[i]) >= C(100,10)

Cette possibilité est indépendante d'un calcul par pesées. C'est comme si
vous disiez : devant peser un kilogrammes, je doit peser mille fois un
gramme. Mon algorithme précédent arrivait à 60 pesées maximum et 6 pesées
minimum. Ce qui contredit votre hypothèse.

Une pesée qui pèse (= donne le poids de) n pièces donne
a[i] = min(n[i]+1,11) résultats possibles

Malheureusement cette borne est si grossière qu'elle n'aboutit pas
à grand chose. Avec tes pesées :
20 pesées de 5 pièces donnent 6^20 résultats possibles à priori,
ce qui est déjà largement supérieur à C(100,10) !
Il est indispensable de raffiner cette borne (car les résultats des
20 pesées ne sont pas indépendants).

Evidemment ! Et c'est là où se pose ce problème. Mais puisque l'hyposthèse
d'une distribution maximale des pesées est posée, il s'agit bien de calculer
ce nombre.

Sans "astuce" la détermination de 2[*] pièces fausses parmi 5 en 3
pesées seulement n'est déja pas évidente, et nécessite de peser
certaines pièces plusieurs fois.

Sur cinq pièces, il suffit pourtant de trois pesées au maximum pour
determiner n'importe quelle quantité de pièces fausses parmi les pièces
vraies.

Qu'en est-il alors avec plus de pièces ? si au lieu de faire 20 tas à
priori et de peser chacun d'eux, tu commences par peser disons
30 pièces, et selon le résultat de cette première pesée choisis
judicieusement les pièces à peser (ou repeser) lors de la pesée
suivante ?

bis repetita :

Non. Le problème de trouver 10 pièces fausses parmi 100 n'est pas facteur de
trouver une pièce fausse parmi dix.

Le cas me semblant trivial

?? justement non.

Oui :-)

Et avec ta méthode, on "voit" juste que le nombre max de pesées est
*inférieur ou égal* à 60. Et la remarque précédente conduit à
suspecter fortement que ce soit strictement inférieur à 60 !

Il se peut qu'une distribution hasardeuse des pesées arrivent à 60. 60 est
donc inclue.

nota [*] : détermination des pièces parmi 5
...

1 pièce fausse : assez évident

Reste trois pesées au maximum.

2 pièces fausses : pb intéressant

Je ne vois pas où est le problème. Reste aussi trois pesées au maximum.

trois pièces fauses ..

Pareil, reste trois pesées au maximum.

4 pièces fausses

reste aussi trois pesées au maximum.

...

Amicalement moi aussi

Mathieu