Mathieu Seurat a écrit :

Qu'appelle-t-on une "pesée" ici ?

Comparaison de deux tas de pièces, avec comme seul résultat :
"plus lourd / plus léger / de même poids"

Evidemment que non - Je suppose que s'il s'agissait d'une balance
à deux plateaux qui n'est plus utilisée depuis plus de 40 ans,

sauf dans les problèmes ;-)

cela aurait été indiqué.

qui sait ...

Et même dans ce cas, l'utilisation de tares était indispensable.

Là non. Voir le problème classique de trouver une pièce fausse de
poids inconnu parmi 12 en 3 pesées, justement avec ce type de balance,
sans tare ni rien d'autre que la balance toute nue et les 12 pièces.

Piste ? chercher des algorithmes de tri.

J'en donnais un dans ma question précédente.

Les seuls algorithmes de tri que je connaisse sont justement basés
sur des *comparaisons*. D'où ma question sur le type de balance.

Je n'ai aucune idée sur comment utiliser des informations du genre :
"il y a 7 pièces fausses dans le paquet de 25 pièces que je viens
de peser."
(à part le cas trivial "il y a 0/1 pièce fausse dans le paquet de 1
pièce", ou "0/n pièces fausses dans le paquet de n pièces")

Le cas me semblant trivial

?? justement non.

il s'agirait de trouver comment modéliser en langage mathématique
la résolution du problème consistant à trouver le meilleur
algorithme.

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)

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

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

Le cas me semblant trivial

?? justement non.

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 !


nota [*] : détermination des pièces parmi 5
0 pièces fausse : inutile même de peser !
1 pièce fausse : assez évident
2 pièces fausses : pb intéressant
3 pièces fausses : c'est 2 pièces bonnes
4 pièces fausses : c'est 1 pièce bonne
5 pièces fausses : n'en parlons pas !
Il suffit donc de savoir trouver 2 pièces fausses parmi 5.


Amicalement.

--
Philippe C., mail : chephip
avec free.fr comme domaine
site : http://chephip.free.fr/   (divertissements mathématiques)