par Anonyme » 27 Oct 2005, 16:45
>>Non pour 3 pesées le max est 12 boules.(on peut prouver que 13 boules n'est pas possible en 3 pesées)
Oui. Je n'étais pas claire : je voulais dire que si on a une boule plus légère (on sait déjà qu'elle est plus légère) parmi 3^k boules, on peut la trouver en k pesées.
Par exemple: en 2 pesées, on peut trouver la boule la plus légère parmi 9 boules.
Sinon, pour le nombre max de boules, je n'ai aucune idée, j'ai juste montré par récurrence que si on a une boule différente parmi 12.3^k boules, on peut la trouver et dire si elle est plus lourde ou plus légère en k+3 pesées.
Pour k=0: on a vu que c'est vrai.
Supposons que c'est vrai pour un entier k quelconque, et montrons que c'est vrai pour k+1.
.Première pesée: On partage les 12.3^(k+1) boules en 12.3^(k+1) / 3 boules et on fait : 12.3^k boules d'un coté et 12.3^k boules de l'autre coté de la balance.
1er cas: si ça balance pas, la boule cherchée fait partie de 12.3^k boules restantes: on sait faire d'après l'hypothèse en k+3 pesées.
on a donc fait k+4 pesées.
2e cas: Si ça balance, on a alors 12.3^k boules susceptibles d'être plus légères (l) et 12.3^k boules susceptibles d'être plus lourdes (L) et 12.3^k boules normales (L).
.2ème pesée: on fait 12.3^k/2 boules (L) avec 12.3^k/4 boules (N) d'un coté, et 12.3^k/ boules(L) avec 3.3^k boules (l) de l'autre coté.
On a alors 3 cas a, b et c :
(6.3^k(L)+3.3^k(l)) a
(6.3^k(L)+3.3^k(N))-- (6.3^k(L)+3.3^k(l)) b
(6.3^k(L)+3.3^k(l)) c
b => la boule cherchée fait partioe des (l) restantes, y en a 3^(k+2) . On sait donc qu'elle est légère et on sait faire en k+2 pesées. (*)
c=> la boule cherchée fait partie des 6.3^k=2.3^(k+1) (L) (à droite), on sait qu'elle est lourde et on sait faire en k+2 pesées. (*)
a => la boule chechée est soit plus légère et fait partie de 3^(k+1) (l), soit plus lourde et fait partie de 2.3^(k+1) (L) (à droite)
, on sait faire en k+2 pesées. (*)
dans les 3 cas, on a 2+k+2 = k+4 pesées.
-
(*) On montre par récurrence que si l'on a une boule différente et qu'on sait d'avance si elle est plus légère ou plus lourde parmi 3^k boules, on sait faire en k pesées, on en déduit que s'il y a une boule différente et qu'on sait qu'elle est plus légère ou plus lourde parmi 2.3^k boules, on sait faire en k+1 pesées, et que si on sait qu'il y a une boule plus légère parmi 3^k boules ou une boule plus lourde parmi 2.3^k boules, on sait faire en k+1 pesées.
Voilà, en éspérant que je me suis pas trompée.
Sinon, je veux bien savoir le nombre max de boules pour p pesées...