Quel est le nombre minimum de pesées nécessaires pour trouver la balle de poids différente?

Question

S'il y a 9 balles parmi lesquelles si 1 balle est de poids différent, il faut un minimum de 2 pesées pour trouver la balle impaire. S'il y a 27 balles, cela nécessite 3 chances.

9 -> 3 pow 2 -> 2 chances.

27 -> 3 pow 3 -> 3 chances.

Question: Quel est le nombre minimum de requis pour trouver pèse la balle bizarre si on leur donne

3 pow 45-3 pow 40 balles

?

Impossible d'utiliser la calculatrice. Je pense, une équation/formule doit être dérivée.

Quelqu'un peut-il craquer ce casse-tête?

Answer 1

Si 3^x = N balles et x -- number of weighs, x = log3(N);

3^x = 3^45 - 3^40; 
3^x = 3^40 * (3^5 - 1); 
x = log3(3^40) + log3(3^5 - 1) = 40 + log3(242); 
real_x = ceil(x); 

Answer 2

Sur la base de vos exemples, nous devons en déduire que la balle différent poids est connu soit d'être plus lourd ou connu pour être plus léger. Pour simplifier, je suppose que c'est plus lourd. Premièrement, voyons pourquoi il est possible de le faire en 45 pesées: Pour des balles de 3n, on peut peser n contre n, laisser n sans peser et réduire à n balles. Faites ceci 40 fois, en réduisant à un lot de (3^45-3^40)/3^40 = 3^5-1 = 242 boules. La grosse balle est quelque part dedans. Ajouter une balle normale connue, de sorte que vous avez 243 (une puissance de 3 à nouveau) et continuer avec cinq autres pesées, après quoi vous aurez la lourde balle. Voyons maintenant pourquoi cela ne peut pas être fait en 44 pesées ou moins: Chaque pesée vous fournit une information, qui peut être considérée comme un nombre de 0, 1, ou 2. 0 pour "le poids lourd" ou "0". la balle est sur la gauche ", 1 pour" la balle lourde est sur la droite ", et 2 pour" la balle lourde est dans le lot non pesé ". C'est vrai, peu importe combien de balles sont pesées contre un nombre égal de balles. Ainsi, les résultats de 44 pesées peuvent être considérés comme une séquence de 44 chiffres - 0, 1 'et 2. Il y a 3^44 résultats possibles de toute stratégie en utilisant 44 pesées. Mais vous avez plus de 3^44 balles, donc vous ne pouvez pas garantir de trouver la bonne en utilisant un processus expérimental qui ne produit que 3^44 réponses différentes. Du point de vue de la théorie de l'information, il y a plus d'informations dans la «bonne réponse» que ce qui peut être produit par 44 pesées.

Answer 3

Une autre façon intuitive pour obtenir la réponse est en vous posant cette question:

Combien de balles peut être vérifié au plus par une seule pondération? La réponse est la suivante: si vous comparez deux balles sur trois, vous trouvez immédiatement celle qui est de poids différent (plus ou moins lourde) ou vous trouvez qu'elles ont un poids égal qui, par le processus de l'élimination conduit à ce que la troisième balle ait un poids différent. En conséquence, on peut diviser N balles sur des groupes de 3 plus un groupe restant de M (avec 0 < = M < 3).Appliquer une seule pondération par groupe de 3 éliminera 2/3rds de toutes les balles. Cela signifie que vous êtes à gauche avec un nouveau groupe de balles à partir duquel vous devez trouver celui avec un poids différent, le nombre de balles dans ce groupe est égal à plancher (N/3) + M.

En appliquant le même procédure à ce groupe réduit de balles, vous pouvez trouver la balle avec un poids différent dans le cas général au plus au plafond (log (N)/log (3)) étapes. La raison de l'instruction ceiling() est que vous pouvez éventuellement manquer de groupes de 3 et être laissé avec un groupe de 2 balles pour lesquelles une pondération supplémentaire est requise. (Si le dernier groupe est seulement 1 boule, vous n'avez pas besoin de le peser pour en déduire qu'il doit s'agir de la balle d'un poids différent.Plus précisément formulé, le nombre de pondérations requises semble être au plus plancher (log (N)/log (3)) + 1; de là, la simple observation que si log (N)/log (3) est entier, la pondération supplémentaire n'est pas nécessaire conduit à la valeur plus précise du plafond (log (N)/log (3)).)