l'énigme des n billes

Question

Bonjour à tous,
J'essaye de trouver le nombre minimum de pesés pour identifier la bille intruse (+ou - légère) dans un ensemble de n billes.
j'ai essayer de faire l&#8217;esquisse de l'algorithme (qui essaye de diviser à chaque foi n par 3) et j'ai trouver que le nombre de pesés est donné par la récurrence T(n)=T(n/3)+9.
Mais le résultat et carrément loin de la plaque car pour n=12 billes on peut savoir la bille intruse en 3 pesés et d'indiquer si elle est plus lourde ou légère que les autres, et ma récurrence me donne un résultat très loin.
 Si vous avez  une remarque ou un indice, vous allez vraiment me sauvé la vie :)

cs_L0ci · Answer

Bonjour,

Si j'ai bien compris la question je dirai que le nombre de pésées minimum est le nombre de divisions successives pour atteindre un nombre impair ou 2.

par ex:
12 billes

Pesée 1: 6 billes | 6 billes
on garde le groupe le plus leger
Pesée 2: 3 billes | 3 billes
on garde le groupe le plus leger
Pesée 3: il suffit de comparer 2 des 3 billes pour trouver l'intrus

A partir du moment ou on doit faire 2 groupes et laisser une bille de coter on a une chance de trouver l'intrus. Si on a 2 groupes de meme poids la bille ecartée est forcement l'intrus.

J'espere que ca t'aidera et que j'ai répondu a la question .

L'énigme des n billes

1 réponse

Votre réponse

Discussions similaires