Forum de mathématiques - Bibm@th.net

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Un tyran, 1000 bouteilles et des condamnés

Bonjour,

Le Président à vie d'un régime dictatorial décide de donner une petite "garden party dans les jardins de son palais".
Il réquisitionne donc 1000 bouteilles de vin fin...
Las, il lui revient aux oreilles que l'une des bouteilles contient un poison.
Ce poison présente la particularité de ne laisser apparaître aucun effet secondaire jusqu'à ce que survienne la mort entre 10 et 20 h après son ingestion, même en quantité infime.
C'est d'autant plus ennuyeux qu'il ne l'apprend qu'en même temps que les bouteilles sont livrées, soit 24 h avant le début des festivités prévues.
Il s'avise alors que dans ses geôles croupissent un nombre bien suffisant de condamnés pour servir de goûteurs...
Il décide de décréter l'amnistie pour les goûteurs qui auraient survécu c'est pourquoi, il demande à l'un de ses conseillers, logicien émérite, de lui trouver une méthode qui permette d'utiliser le minimum (!) de goûteurs parmi les prisonniers, afin de déterminer à coup sûr la bouteille à éliminer.
Que pensez-vous que ce nombre minimum puisse être (et pourquoi) ?
(Traduit de l'Américain : j'espère avoir été clair).

@+
[EDIT]
Il doit être évident, j'espère, qu'un nombre de goûteurs exact devra être accompagné de la méthode de détermination de la bouteille empoisonnée...

Dernière modification par yoshi (06-04-2013 21:49:47)

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Un tyran, 1000 bouteilles et des condamnés

Salut,

comme j'ai peur que jpp me grille la politesse, je marque mon passage !

▼une idée

je pense que 10 prisonniers doivent suffire à désighner en 20 heures au maximum LA bouteille incriminée.
Donc la manip est la suivante : les bouteilles sont numérotées de 1 à 1.000. Je convertis leur numéro en binaire.
Je verse une goutte de chaque bouteille dans un verre numéroté de 1 à 10 selon la règle suivante :

dans le verre n° 1, je prélève un goutte du sang de la terre de la bouteille dont le premier numéro du nombre binaire (lu de droite à gauche) se termine par 1 ;

dans le verre n° 2, je prélève un goutte du sang de la terre de la bouteille dont le second numéro du nombre binaire (lu de droite à gauche) se termine par 1 ; et ainsi de suite jusqu'à la dernière bouteille.  Le contenu de chaque bouteille aura été prélevé autant de fois que son code binaire compte de 1.

Chaque prisonnier boit le verre correspondant à son numéro. Les prisonniers qui meurent sont signé 1, les autres, vivants, signés 0. Ils donnent ainsi le numéro en binaire de la bouteille empoisonnée !

Dernière modification par freddy (04-04-2013 15:29:23)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Un tyran, 1000 bouteilles et des condamnés

Re,

▼@freddy

clap ! clap ! clap !
Cela dit l'auteur de l"énigme donne cette solution, mais il précise, cerise sur le gâteau, qu'on peut faire un tout petit mieux...

@+

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Un tyran, 1000 bouteilles et des condamnés

Re,

▼@yoshi

aucun mérite, je connaissais. Par contre, je ne sais plus comment on montre que 8 suffisent !!! Là, je dois chercher et trouver avant jpp !

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Un tyran, 1000 bouteilles et des condamnés

Re,

voilà, je viens de trouver comment on finit le boulot ...

▼amélioration

on forme 4 groupes de 250 bouteilles, qu'on numérote de 1 à 250 dans chaque groupe, et on utilise la technique décrite ci-dessus avec seulement 8 prisonniers moyennant une petite convention : on les fait boire à 4 reprises avec une heure d'intervalle à chaque fois, pour identifier le groupe dans lequel se trouve la bouteille empoisonnée

@+

Dernière modification par freddy (02-04-2013 20:47:46)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Un tyran, 1000 bouteilles et des condamnés

Re,

T'en fais pas, je viens de trouver de quoi te donner des insomnies...

@+

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Un tyran, 1000 bouteilles et des condamnés

Bonjour,

C'est tout ? Pas d'autre propositions ? Trop dur ?

@+

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : Un tyran, 1000 bouteilles et des condamnés

salut.

▼une idée

il y a 1000 bouteilles   1000 légèrement inférieur à [tex]2^{10}[/tex]

d'autre part , [tex] 2^{10} = (_ 0^{10})  +  (_ 1^{10}) + (_ 2^{10}) +.... (_ 9^{10}) + (_{10}^{10})  [/tex]

  1022 = 10 + 45 + 120 + 210 + 252 + 210 + 120 + 45 + 10

le tyran dispose de 1000 bouteilles auxquelles il aura ajouté 22 bouteilles d'eau pure . il fait marquer toutes ses bouteilles.

la stratégie est la suivante:

on prélève une seule goutte par bouteille sur le premier lot de 10 et on fait gouter 10 prisonniers. Si le poison tue 1 seul prisonnier,on pourra savoir quelle bouteille il aura gouttée.

ensuite , on prélève 2 gouttes par bouteille du secon lot . ce qui fera 90 gouttes . on fera donc goutter 9 bouteilles du second lot à chacun des 10 prisonniers. Et si seulement 2 prisonniers meurent , il suffira de savoir quelle bouteille ils ont bu en commun.

en poursuivant le processus , parmi 120 bouteilles  , 3 prisonniers auront goutté à la même bouteille mais ils auront goutté 36b
4 morts parce que   parmi 210 bouteilles ,  4 prisonniers auront goutté à la même bouteille mais ils auront goutté 84b
5 morts parce que   parmi 252 bouteilles ,  5 prisonniers auront goutté à la même bouteille mais ils auront goutté 126b
6morts parce que    parmi 210 bouteilles ,   6 prisonniers auront goutté à la même bouteille mais ils auront goutté  126b
7 morts parce que   parmi 120 bouteilles ,   7 prisonniers auront goutté à la même bouteille mais ils auront goutté 84b
8 morts parce que   parmi 45 bouteilles      8 prisonniers auront goutté à la même bouteille mais ils auront goutté 36b
9 morts parce que    parmi 10 bouteilles     9 prisonniers auront goutté à la même bouteille mais ils auront goutté 9b

avec ce procédé je suis sûr de laisser vivant au moins un prisonnier , au plus 9 . mais je suppose bien évidemment que le tyran s'en tamponne.

maintenant on peut peut-être descendre en deçà de 10 . mais je n'ai pas bien compris le problème des temps.

                               

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Un tyran, 1000 bouteilles et des condamnés

Salut,

▼@jpp

auxquelles il aura ajouté 22 bouteilles d'eau pure
Pourquoi faire de l'eau pure ? Tu veux gâter le vin ?  Ça va pas, non ?
Bon, trêve de plaisanteries...
Dans la solution dont je dispose, il n'est pas question d'eau.
avec ce procédé je suis sûr de laisser vivant au moins un prisonnier , au plus 9 . mais je suppose bien évidemment que le tyran s'en tamponne...@
Oui et non... Les survivants parmi les goûteurs,seront amnistiés. Le tyran ne tient pas en amnistier trop, et donc veut utiliser le minimum de goûteurs.
Sinon, on prend 1000 goûteurs, un seul meurt et hop 999 amnistiés à relâcher...

Mais la question est

trouver une méthode qui permette d'utiliser le minimum (!) de goûteurs parmi les prisonniers, afin de déterminer à coup sûr la bouteille à éliminer.
Que pensez-vous que ce nombre minimum puisse être (et pourquoi) ?

Et ta réponse est ?

Tu donnes 9... 9 quoi ? 9 survivants, 9 goûteurs ?

Le problème du temps, si j'ai bien compris, c'est que l'action du poison n'est pas instantanée : il met aléatoirement entre 10 et 20 h pour agir et on ne peut savoir si un prisonnier a ingurgité du poison que s'il meurt...
En outre, le tyran ne dispose que de 24 h pour identifier la bouteille empoisonnée.
Si le poison agissait dans la minute, ça devrait changer la donne, je n'y ai pas réfléchi.

@+

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : Un tyran, 1000 bouteilles et des condamnés

re.

▼ma réponse

ma réponse est bien évidemment 10 prisonniers puisque selon le nombre de morts je détermine le lot de bouteilles ou se trouve le poison.

s'il y a un mort c'est le premier lot de 10 b , s'il y en a 2 , c'est le second lot de 45 b .... s'il y a 9 morts , c'est le dernier lot de 10 b.

et je ne gache pas le vin .

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Un tyran, 1000 bouteilles et des condamnés

Salut,

▼@jpp

et je ne gache pas le vin .

Aaah.... tu rassures tous les amateurs ! ^_^
Vi, vi, c'est une réponse plausible et acceptée...
Mais j'aimerais bien que tu clarifies ton procédé post #6 avec 1000 bouteilles et non 1022, aussi en termes de gestion du temps.
Les lots goûtés le sont :
- l'un après l'autre ?
- simultanément ? Et comment détermines-tu alors le n° de la bouteille incriminée ?
  Montre-moi ça avec 8 bouteilles et 3 goûteurs, ce sera plus rapide qu'avec 1000 bouteilles et 10 goûteurs ^_^
Toutefois, là, où j'ai pêché l'énigme, il est dit que 10 est la réponse la plus courante, mais qu'on peut en cherchant bien optimiser un chouïa en plus et descendre légèrement en dessous de 10...
Confirmé par freddy

@+

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Un tyran, 1000 bouteilles et des condamnés

Salut,

la solution de jpp ne peut convenir car on manque de temps !!!

arfr

Invité

Re : Un tyran, 1000 bouteilles et des condamnés

▼objection

Re,

voilà, je viens de trouver comment on finit le boulot ...

amélioration : on forme 4 groupes de 250 bouteilles, qu'on numérote de 1 à 250 dans chaque groupe, et on utilise la technique décrite ci-dessus avec seulement 8 prisonniers moyennant une petite convention : on les fait boire à 4 reprises avec une heure d'intervalle à chaque fois, pour identifier le groupe dans lequel se trouve la bouteille empoisonnée

@+

Et si les morts surviennent entré 14 et 16 heures après l'ingestion du premier groupe il faudra encore discriminer entre 4 bouteilles !

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Un tyran, 1000 bouteilles et des condamnés

Salut,

l'objection de arfr est tout à fait exacte.  Il faut la prendre comme une précision à la réponse pour 8 personnes !

C'est ce problème de temps que jpp n'avait pas bien vu. Je me demande d'ailleurs où il est passé, on ne le voit plus.

Dernière modification par freddy (10-04-2013 12:38:09)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Un tyran, 1000 bouteilles et des condamnés

Re,

Je ne dis ni oui, ni non, mais pourquoi aurait-il la bonne réponse et pas toi ?
Je demande le nom du chenapan à interroger et pourquoi lui ?
Et cela n'a rien à voir avec les jeux de mots foireux...
Bien relire le message !

@+

Boody

Membre

Inscription : 31-03-2014

Messages : 183

Re : Un tyran, 1000 bouteilles et des condamnés

Bonjour,

(un déterrage du topic des 3 préludes m'a fait déterré celui-ci)

je pense qu'avec

▼xxx

10

prisonniers on devrait pouvoir s'en sortir.

▼car

on peut numéroter les bouteilles de 0 à 999 et chaque prisonnier assumant le rôle d'un bit du poids faible à fort (0 à 9) goûte les bouteilles dont le n° en binaire contient '1' pour le bit qu'il représente.

On pourrait d'ailleurs déterminer la bouteille empoisonnée parmi 1024 bouteilles mais donner ce nombre dans l'énoncé serait un trop gros indice.

ex. 4 bt 2 prisonniers : le premier goute la bouteille 1 et la 3, le 2ème prisonnier goute la 2 et la 3

0 00
1 01
2 10
3 11

20h plus tard, on pose 1 pour chaque goûteur dégoûté (mort) et 0 pour les vivants

le nombre obtenu est celui de la bouteille cherchée.

Par contre est-ce vraiment le minimum de prisonniers ? faut-il utiliser la contrainte temporelle pour essayer de réduire le nombre de goûteur ?

Joker

Membre

Inscription : 22-07-2014

Messages : 6

Re : Un tyran, 1000 bouteilles et des condamnés

Bonjour !

Ce qui est vraiment drôle avec la solution qui a été proposée, c'est que :

▼ah ah

En plus de faire sortir un minimum de prisonniers de leur trou puant pour leur donner du bon vin, la stratégie proposée réduit le nombre d'amnisties : si tant est que la bouteille est dans les premières, il pourrait y avoir une belle majorité de morts !

Par contre, quelque chose me chiffonne dans ces stratégies

▼faire mieux

Il me semble que les stratégies proposées ne sont pas optimales car on fait boire du vin de toutes les bouteilles. Or, si on teste toutes les bouteilles sauf une et que personne ne meurt, on sait aussi dans quelle bouteille se trouve le poison.

Du coup, il faudrait plutôt adapter cette idée (comme dans le cas où freddy divise en 4 groupes de 250 bouteilles) en faisant des sous-groupes où les bouteilles ne sont pas testées. Voilà mon intuition !

A bientôt,

Dernière modification par Joker (24-07-2014 09:33:19)

Boody

Membre

Inscription : 31-03-2014

Messages : 183

Re : Un tyran, 1000 bouteilles et des condamnés

Bonjour,

@Joker : je n'ai pas lu les autres spoilers (pour pouvoir continuer chercher si le nombre que j'ai donné n'est pas optimale) mais dans ma proposition il y a bien une bouteille qui n'est goûté par personne.

padre

Invité

Re : Un tyran, 1000 bouteilles et des condamnés

Salut,

comme j'ai peur que jpp me grille la politesse, je marque mon passage !

▼une idée

je pense que 10 prisonniers doivent suffire à désighner en 20 heures au maximum LA bouteille incriminée.
Donc la manip est la suivante : les bouteilles sont numérotées de 1 à 1.000. Je convertis leur numéro en binaire.
Je verse une goutte de chaque bouteille dans un verre numéroté de 1 à 10 selon la règle suivante :

dans le verre n° 1, je prélève un goutte du sang de la terre de la bouteille dont le premier numéro du nombre binaire (lu de droite à gauche) se termine par 1 ;

dans le verre n° 2, je prélève un goutte du sang de la terre de la bouteille dont le second numéro du nombre binaire (lu de droite à gauche) se termine par 1 ; et ainsi de suite jusqu'à la dernière bouteille.  Le contenu de chaque bouteille aura été prélevé autant de fois que son code binaire compte de 1.

Chaque prisonnier boit le verre correspondant à son numéro. Les prisonniers qui meurent sont signé 1, les autres, vivants, signés 0. Ils donnent ainsi le numéro en binaire de la bouteille empoisonnée !

salut freddy,
j'ai essayé de resoudre l’énigme avec ma méthode mais bon je me suis rendu compte que mon raisonnement était faux car j'avais négligé la contrainte du temps . J'ai donc essayé de voir les raisonnement des autres membres pour m'en inspirer , mais je ne comprend pas le votre , pourriez vous m’éclairer ?
merci d'avance

padre

Invité

Re : Un tyran, 1000 bouteilles et des condamnés

ps : y a t il des secrets dans les calculs en base 2 ? DD

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Un tyran, 1000 bouteilles et des condamnés

Bonjour,

Qu'est-ce que tu entends par "secrets" ?
Informatiquement, on peut jouer sur les bits d'un octet.
Je l'ai déjà expérimenté en toute partie ici:
http://www.bibmath.net/forums/viewtopic.php?id=6079

@+

Boody

Membre

Inscription : 31-03-2014

Messages : 183

Re : Un tyran, 1000 bouteilles et des condamnés

...mais je ne comprend pas le votre , pourriez vous m’éclairer ?
...

Bonjour,

j'ai mis un exemple dans le post #16 avec 4 bouteilles.

HTH :)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Un tyran, 1000 bouteilles et des condamnés

B'jour,

Je n'avais jamais donné la solution.
La voilà (en V.O : pas le courage de tout traduire !)
http://www.folj.com/puzzles/very-diffic … uzzles.htm

@+

Boody

Membre

Inscription : 31-03-2014

Messages : 183

Re : Un tyran, 1000 bouteilles et des condamnés

B'jour,

Je n'avais jamais donné la solution.
La voilà (en V.O : pas le courage de tout traduire !)
http://www.folj.com/puzzles/very-diffic … uzzles.htm

@+

Salut Yoshi,
je n'ai pas lu la solution ni les autres propositions (pour pouvoir continuer à chercher si besoin), je voulais juste savoir si ma réponse (#16) était correcte ou s'il y avait mieux ?

Dernière modification par Boody (21-07-2015 21:25:56)