Philippe 92 a écrit :

Que des bêtises.

(supersedes <mn.c3ff7d859f0b00aa.22155@free.fr>)

Mathieu Seurat a écrit :

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

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.

Hélas, c'est faux.
Après examen attentif, avec 2 pièces fausses parmi 5 il faut 4 pesées.

Je n'ai pas dû etre assez attentif, ou les yeux dans le guidon.
C'est vrai, le nombre de pesées pour trouver p pièces fausses parmi 5
est bien de 3, même dans le cas de 2 pièces fausses. Et comme je le
disais moi-même au dessus : il faut bien choisir sa méthode de pesées.
Voir ci-après pourquoi je me suis planté en disant 4.

Jacky a montré que 49 pesées suffisent toujours.

[ snip la preuve que même si on n'a pas choisi le meilleur algorithme
pour trouver 2 pièces fausses parmi 5 et qu'on fait ça en 4 pesées
au lieu de 3, 49 pesées sufisent quand même ]

Soit f(n,p) le nombre minimal de pesées nécessaire pour trouver p
pièces fausses dans un tas de n. (on cherche f(100,10)).

Si on effectue alors une pesée de k pièces on réduit le problème à
trouver p' pièces parmi k + le problème de trouver p" parmi (n-k)
et on a donc  f(n,p) = f(k,p') + f(n-k, p") + 1
bien entendu p' <= k, p" <= n - k et p' + p" = p

Ce qui nous intéresse est le maximum de f(n,p) sur l'ensemble
des répartitions possibles, c'est à dire toutes les valeurs de p.
Sachant que pour chaque valeur de p, on a choisi les valeurs
successives de k pour avoir ce maximum aussi petit que possible
(k = "méthode de pesée").

C'est à dire que
f(n,p) = min/k (max/p' (f(k,p') + f(n-k, p-p') + 1))

qui permet de calculer récursivement les f(n,p).
Malheureusement cette méthode de pesée 'par séparation' n'est pas
optimale dans tous les cas ! Là est l'erreur.

Comme exemple elle donne f(5,2) = 4, alors qu'il existe d'autres
méthodes qui donnent f(5,2) = 3 !

Conclusion :
La méthode indiquée (donnant 49 pesées) pour 10 pièces fausses
parmi 100 est en fait cette méthode par séparation (la mauvaise).
Elle sépare les 100 pièces en 20 tas de 5, puis on cherche
*indépendamment* dans chaque tas de 5 les pièces fausses.
(et on obtient 49, même si pour trouver 2 pièces fausses dans
des tas de 5 on utilise le même mauvais algorithme et qu'on fait ça
en 4 pesées au lieu de 3).

Il doit donc sans doute exister des méthodes de pesées meilleures,
selon le même principe que pour f(5,2) = 3, qui pèsent des
sous-ensembles **non disjoints** de pièces.


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