Exercice 1 — les souris goûteuses

Partie 1

1. Il y a 2 bouteilles, numérotées 1 et 2 . La souris en goûte une, par exemple la 1 . Si elle meurt le lendemain, la bouteille 1 est empoisonnée. Si elle survit, c'est la 2.
2. Les 8 bouteilles sont séparées en 2 lots de 4 .

Le premier jour, une souris goûte un mélange du premier lot. Si elle survit, la bouteille empoisonnée est dans le 2ème lot, sinon dans le \(1^{\text {er }}\). Au bout d'un jour, on a donc isolé 4 bouteilles suspectes, et notre souris a soit survécu (elle est prête pour le 2ème jour), soit non (auquel cas on engage une deuxième souris).
Le deuxième jour, on fait goûter 2 des 4 bouteilles suspectes à une souris : si elle meurt, la bouteille empoisonnée est dans ce mélange de 2 . Si elle survit, elle est dans les 2 autres. Au bout de deux jours, on n'a plus que 2 bouteilles suspectes, et on a utilisé entre 0 et 2 souris.
Le troisième jour : c'est la question 1: il faut un jour et une souris, qui peut survivre, ou non.
Au final, \(\mathbf{3}\) jours sont nécessaires. Pour être absolument certain de trouver la bouteille, il faut 3 souris. Si on n'a pas de chance, elles meurent toutes. Si en revanche on est chanceux, la même souris goûte chaque jour et peut survivre.
3. On remarque que \(1024=2^{10}\), on peut donc diviser les bouteilles en lots égaux 10 fois de suite : il faudra donc 10 jours, une division nécessitant une journée de test. Le nombre de souris nécessaire est 10, sachant qu'elles ne mourront pas forcément toutes (avec beaucoup de chance, elles peuvent toutes survivre, si la souris goûte à chaque fois le lot où ne se trouve pas la bouteille empoisonnée, et dans le cas contraire, elles peuvent toutes mourir).
4. On procède comme précédemment mais on ne va pas pouvoir toujours diviser en 2 lots égaux. II est difficile de prouver l'optimalité de la solution mais on peut accepter une solution comme :

• La stratégie fonctionne comme auparavant pendant 3 jours : le premier jour, on a 2 lots de 500 bouteilles, le deuxième, 2 lots de 250 , le troisième, 2 lots de 125 . Au bout de 3 jours, on a donc isolé 125 bouteilles suspectes et consommé jusqu'à 3 souris.
• Le jour 4 on fait un lot de 62 et un lot de 63 bouteilles.
• Le jour 5, on fait 2 lots de 31 (si c'est le lot de 62 qui est suspect), ou un lot de 31 et un lot de 32.
• Le jour 6, si on part d'un lot de 31, on fait un lot de 15 et un de 16; si c'est un lot de 32, deux lots de 16. Les lots de 16 sont "remis sur les rails" des puissances de 2 et nécessitent 4 jours, soit 10 au total. On peut gagner un jour si on a de la chance et que la bouteille suspecte est dans le lot de 15.
• Dans ce cas, le jour 7 on divise en 7 et 8 . On aura de la chance si c'est dans le lot de 7 (le lot de 8 nécessitant 3 jours).
• Dans ce cas, le jour 8 on a un lot de 3 et un lot de 4 . On aura de la chance si c'est dans le lot de 3 .
• Dans ce cas, le jour 9 on a un lot de 1 et un lot de 2 . Si la bouteille incriminée est dans le lot de 1 , c'est gagné en 9 jours.
  Bon, cette méthode est tout de même peu satisfaisante : on peut supposer que la cave du roi est constituée de grands crus exceptionnels, et c'est un peu dommage de les laisser s'éventer ouverts pendant 10 jours ! D'où la nécessité de la partie 2.

Partie 2

1. On peut remarquer que le tableau nous donne directement quelles souris meurent en fonction de la bouteille empoisonnée : il suffit de lire les colonnes, s'il y a un 1 , la souris correspondante meurt.
   Ainsi : si c'est la bouteille 1, la souris 1 meurt et l'autre vit. Si c'est la bouteille 2, la souris 1 meurt et la 2 vit. Si c'est la 3 , les deux vivent. Si c'est la 4 , les 2 meurent. Ce sont 4 résultats différents qui permettent donc de conclure à coup sûr en un jour, en utilisant 2 souris. Le nombre de souris mortes sera 0 (bouteille 3) 1 (bouteilles 1 et 2) ou 2 (bouteille 4).
2. On dessine de même un tableau en se débrouillant pour que les combinaisons de 0 et de 1 soient différentes dans chaque colonne. (attention : plusieurs solutions sont possibles!)

Dans ce tableau j'ai choisi de ne pas utiliser la possibilité de faire goûter une bouteille par toutes les souris pour maximiser le nombre de souris survivantes.
Ainsi : bouteille 1 empoisonnée : la souris 1 vit, les 2 et 3 meurent, etc. etc. On constate que tous les résultats sont différents et permettent de conclure.

1. Le nombre de bouteilles que l'on peut tester avec 3 souris correspond à toutes les manières d'écrire un nombre de 3 chiffres binaires : 111, 110, 101, 011, 100, \(010,001,000\), c'est à dire \(2^{3}=8\) bouteilles. Le tableau peut ressembler à cela (encore une fois, de nombreuses permutations sont possibles et le tableau n'est pas demandé sur cette question):
2. \(1024=2^{10}\) bouteilles, on peut écrire 1024 nombres différents de 10 bits, 10 souris sont donc nécessaires et permettent de trouver la bouteille en un jour.

Evidemment, écrire quelles bouteilles doivent être goutées par chaque souris est un peu fastidieux, mais n'a rien d'impossible, il suffit d'être méthodique.
NB : si on considère 1000 bouteilles, il faut toujours 10 souris, 9 souris ne permettant de tester que \(2^{9}=512\) bouteilles. On peut juste maximiser les chances de survie en éliminant les 24 nombres les plus chargés en 1 de la solution.

Le mot du correcteur : tout ceci n'explique pas comment on peut introduire du poison dans une bouteille de vin fermée sans que cela ne se voie sur le bouchon