Énoncé
Il y a 10 rats et 1000 bouteilles de vin dont une empoisonnée. Si un rat boit de la bouteille empoisonnée, il meurt au bout d’une heure. Votre but est de déterminer quelle est la bouteille empoisonnée en donnant aux rats à boire des bouteilles de vin selon la combinaison que vous souhaitez puis en constatant quels sont les rats morts au bout d’une heure. Comment faites-vous ?
Solution
L'idée ici est de faire correspondre une bouteille de vin avec un sous-ensemble des 10 rats. En effet, il y a 10 rats donc 2^10=1024 sous-ensembles possibles de rats, donc plus que le nombre de bouteilles. En pratique, on numérote les rats de 1 à 10, et les bouteilles de 1 à 1000, puis pour la bouteille numéro k, on écrit k en écriture binaire ; comme k est inférieur à 2^10, son écriture binaire comportera au maximum 10 chiffres et s’écrira donc a_1, a_2,…, a_10, avec a_p valant 0 ou 1. Puis pour chaque entier p entre 1 et 10, on donnera à boire de la bouteille k au rat numéro p si a_p=1. À la fin, on constate quels sont les rats morts, et on trouve ainsi l’écriture binaire associée : b_1, b_2…b_10, avec b_p=1 si le rat p est mort et 0 sinon, puis on convertit ce nombre en base décimale et on trouve ainsi la bouteille empoisonnée.
Aucun commentaire:
Enregistrer un commentaire