Trouver une bouteille perdue (problème d'algorithme)

Question

La question est la suivante:

Un scientifique crée un nouveau composé, appelé composé A, qui explosera 10 jours après avoir été mélangé avec le composé B. Ce composé A a été stocké dans une bouteille inférieure à une étiquette sur une étagère avec $ N-1 $ bouteilles de matériau non réactif et le scientifique ne sait pas qui est composé A. Il y a exactement une bouteille de composée A parmi la $ n $ bouteilles sur l'étagère. Le scientifique a $ o (journal (n)) $ Békers plein de composé B. Comment peut-il déterminer lequel de la $ N $ Les bouteilles sont le composé A dans exactement 10 jours?

Je suis un peu coincé parce que je ne sais pas comment réduire la bouteille spécifique en seulement 10 jours. Il est assez évident que vous pouvez simplement appliquer la première moitié des bouteilles au premier bécher, puis si cela ne réagit pas, vous savez que la bouteille souhaitée est dans la seconde moitié et ainsi de suite. Mais comment puis-je la réduire sans assister les résultats des premiers tests?

Nous devons créer quelque chose lorsqu'une série d'explosions nous aidera à réduire le fait que celui-ci (disons d'abord son parmi les N / 4, puis N / 10, puis N / 100, etc.). Comment diable fais-je cela?

Answer 1

Il s'agit d'un problème classique que j'ai déjà vu encadré comme un casse-tête plutôt que d'une question CS (avec une autre catégorie fixe $ n $ et nombre fixe de béchers), Bien que je ne me souvienne d'aucune source pour cela.

Vous pouvez le résoudre comme suit: Numérotez vos bouteilles de $ 0 $ to $ N-1 $ et étiquetez vos béchers de 1 $ à $ \ lfloor \ log_2 (n-1) \ rfloor + 1 $ (le nombre de bits nécessaires pour représenter numéros $ 0 $ to $ N-1 $ en binaire).

Maintenant pour chaque bouteille, procédez comme suit: laissez $ x $ être l'étiquette de la bouteille. Pour chaque $ i $ tel qu'il y ait une 1 $ à la $ i $ 'th positionnement dans la représentation binaire de $ x $ , mettez un peu le composé de cette bouteille dans le bécher $ i $ .

Désormais après 10 jours, les béchers qui explosent vont préciser exactement le numéro de la bouteille explosive en binaire.