Au dîner du roi..

[Ben314]

7 bouteilles en 5 tests est aussi impossible mais c'est un peu plus long à vérifier.
(en 6 tests c'est trivial en prenant 1 bouteille par test)

Heuuuuuu, perso, j'aurais bien dit qu'en 5 test c'était tout aussi trivial avec une bouteille par test, non ?

EDIT : NON, NON....

P.S. : on peut plus virer ces messages lorsqu'on se rend compte qu'on a écrit de la m... ?
(si on est obligé de réfléchir avant de taper sur "envoyer", je suis mal....)

[Sylviel]

Je suis curieux de savoir comment tu as obtenu ta règle avec 60 testeurs Bénékire ?

Sinon pour trouver 2 bouteilles empoisonnées parmi K, le nombre minimal de testeur n(K) me semble être :
n(2)=0
n(3)=2
n(4)=3
n(5)=4
n(6)=5 (sauf erreur)
n(7) = 6 (d'après Doraki)

Je généraliserais bien en n(K) = K-1 :dodo:

[nodjim]

C'est possible je crois.
Avec 60 chiffres binaires, on peut réaliser 60*59/2 paires, mais toutes ne sont pas utilisables. Si 2 paires ont un élément commun, ça forme 3 "1" et donc la 3ème paire est indisponible. Donc seulement les 2/3 des paires peuvent être utilisées. ça ferait alors 20*59, qui pourrait passer avec 1000.

[Robot]

nodjim, si tu comprends ce que tu écris, c'est déjà ça. Je dois avouer que moi pas.

[benekire2]

Hum .. en fait avec 60 testeurs je peux pas y arriver avec ma méthode, sauf si on goûte plusieurs fois ce qui est interdit ! Désolé ..

[nodjim]

Pour expliquer ce que j'ai avancé, voici le tableau suivant où:
-une ligne représente une bouteille. Elle comporte 60 bits.
-Un "1" est un verre rempli, un "0" un verre vide.
-Une colonne représente un testeur.

B1: 1100000...
B2: 1010000...

Si B1 et B2 empoisonnées, les malades seront les testeurs 1,2 et 3 (les 3 1ères colonnes). On ne peut distinguer les bouteilles empoisonnées qui si la "somme" des 2 B empoisonnées est unique. Une somme se fait bit par bit situés sur le même rang, avec 1+0, 0+1 et 1+1=1 et 0+0=0.

Soit
B1:1100000...
B2:1010000...
B3:1001000...
B4:1000100..

Toutes les paires exclues sont celles dont les 2 bits se trouvent dans les rangs 2 à 5, ce qui représente C(4,2)=6 paires exclues.

S'il y a 60 bits, le nombre de paires est C(60,2).
Le nombre de paires max, compte tenu des exclusions possibles, est :
60(k+C(k,2)) <= C(60,2)
On trouve k=7, soit 420 paires max.

Mais ce nombre n'est pas bon, car les exclusions sont parfois comptées 2 fois;
1100000
1010000
0110000 est exclu.

0100010
0010010
0110000 est exclu.

Et là ça se complique pour faire le bilan des redondances....

Sinon, quand on a rempli toutes les paires possibles, qui représentent des sommes avec 3 ou 4 "1", il est évident que tous les triplets ne sont pas représentés C(60,3) et encore moins tous les quadruplets C(60,4). Et il est possible de mettre des triplets pour des bouteilles là où les paires sont exclues:

B1:1100000
B2:1010000
B3:0110000 code exclu
B4:0110001 code autorisé (vis à vis de B1/B2)

Et quand on aura complété avec des triplets et des quadruplets, on pourra examiner les quintuplets, etc....

[Ben314]

Sans limite de temps, 11 goûteurs suffisent pour savoir à coup sûr quelles sont les deux bouteilles empoisonnées (sachant qu'un goûteur non empoisonné peut regoûter). On peut peut-être faire mieux.

Il me semble que s'il n'y a pas de limite de temps et qu'on peut réutiliser les gouteurs non morts on s'en sort trivialement avec deux gouteurs : le premier goute les bouteilles une par une jusqu'à ce que mort s'ensuive puis le second fait la même chose.

[Robot]

Oui bien sûr, j'étais parti sur une fausse piste. Je m'en suis rendu compte tout de suite après et ai supprimé le message, mais il est réapparu avec les déménagement du site. La même mésaventure t'est arrivée dans un autre fil, non ?

[Ben314]

Oui bien sûr, j'étais parti sur une fausse piste. Je m'en suis rendu compte tout de suite après et ai supprimé le message, mais il est réapparu avec les déménagement du site. La même mésaventure t'est arrivée dans un autre fil, non ?

Sur un autre et... sur celui là (juste au dessus) où j'ai écrit une grosse boulette dans ma réponse à Doraki...

[nodgim]

Une configuration avec 8 goûteurs permet de trouver 2 bouteilles empoisonnées parmi 10, dans la condition d'un test global unique. Le choix a été fait d'avoir seulement 2 verres pour chaque bouteille, chaque verre occupant l'un des rangs 1 à 8. Ce choix a été guidé par le fait que le groupement de 2 bouteilles donne un nombre avec 3 ou 4 chiffres, et que le 4 chiffres est le plus représenté (C(8,4)).
10 bouteilles trouvées n'est pas forcément le meilleur score. Le choix des paires a été fait seulement en répartissant chaque rang de façon équitable.

Voici les 10 combinaisons. Les chiffres indiqués sont le rang des 2 verres pleins par bouteille.
12;78;34;15;26;37;46;58;13;68.
Avec ce choix là, les 18 autres combis sont exclues (18=C(8,2)-10).

Après que les goûteurs auront bu, il y aura 3 ou 4 malades. le nombre représenté par ces 3 ou 4 goûteurs est unique et permet de retrouver les 2 bouteilles empoisonnées.

Le gain est maigre, le ratio Nb de goûteurs / nb de bouteilles, restant encore proche de 1, mais il doit s'améliorer avec le nb de goûteurs.
On doit pouvoir évaluer, pour des nombres à k chiffres uniquement par bouteille, le ratio de nombre de combinaisons compatibles par rapport au nombre de combinaisons possibles. Ce ratio représente bien entendu le nombre de goûteurs par rapport aux nombres de bouteilles. Il n'y a pas à attendre d'amélioration sensible de ce ratio si k est variable plutôt que fixe.

[nodgim]

Pour 1000 bouteilles, j'ai une solution avec 67 goûteurs (dans le cas d'un seul tour de test).
En fait, c'est une solution qui se généralise avec n goûteurs, et donc qui ne nécessite pas de faire une liste complète de tous les codes.
Je laisse à ceux qui s'intéressent au sujet de réfléchir à cette question.

[syrac]

L'énoncé du problème est tellement pauvre en informations que ça sent le piège. Et de fait, il n'y pas de mathématiques là-dedans mais seulement de la logique.

Si le poison tuait instantanément il serait possible de faire goûter autant de bouteilles à autant de serviteurs qu'on veut. Il suffirait d'attendre que l'un d'eux tombe raide mort pour identifier à coup sûr la bouteille empoisonnée.

Mais le poison tue en une heure ! On ne peut donc pas demander à un serviteur de goûter à plus d'une seule bouteille, sinon une heure après il serait impossible de savoir laquelle l'a tué.

La seule manière de procéder est donc de remettre chacune des bouteilles à autant de serviteurs. Celui qui une heure après tombera raide mort permettra d'identifier la bouteille empoisonnée, c'est-à-dire celle qu'on lui aura remise.

[Sylviel]

Syrac, si tu remontes la discussion tu verras que dans le cas d'une seule bouteille empoisonnée sur 1000 il suffit de 10 gouteurs. Donc ton "raisonnement" est faux. Il s'agit bien d'une question mathématique...

[syrac]

ton "raisonnement" est faux. Il s'agit bien d'une question mathématique...

Ah bon ? Chacun des 10 goûteurs ayant testé 100 bouteilles, comment sais-tu une heure après laquelle a tué l'un d'eux ? Il faudrait refaire le test avec les 100 bouteilles suspectées, ce qui retarderait le dîner d'une heure. Et on ne fait pas attendre le roi...

[syrac]

Je reprends le post supprimé mais réapparu de Robot :

Sans limite de temps, 11 goûteurs suffisent pour savoir à coup sûr quelles sont les deux bouteilles empoisonnées (sachant qu'un goûteur non empoisonné peut regoûter). On peut peut-être faire mieux.

C'est justement là qu'est le piège, ou peut-être que Robot n'a pas lu l'énoncé du problème : un goûteur non empoisonné qui goûte à nouveau, ça n'existe pas. S'il est empoisonné on ne le saura qu'une heure après, au moment même où le roi passe à table. Il est donc impératif d'identifier la bouteille empoisonnée avant l'heure écoulée, il n'y a pas de seconde chance.

[Robot]

Syrac, tu ne comprends rien à rien encore une fois.
Il ne s'agit bien sûr pas de répartir les 1000 bouteilles en 10 lots de 100 !
Il s'agit de numéroter les bouteilles en binaire. Comme il y a 1000 bouteilles, 10 bits suffisent (on pourrait même aller jusqu'à 1024 bouteilles). Ensuite, le goûteur n°i goûte toutes les bouteilles dont le i-ème bit du numéro est à 1. La bouteille empoisonnée est celle dont le numéro a le i-ème bit à 1 si et seulement si le i-ème goûteur est mort au bout d'une heure.

[syrac]

Je n'avais pas lu ces explications, mais admettons. En supposant pour simplifier qu'il y ait 1024 bouteilles, le bit de poids faible sera 512 fois à 1 (tous les nombres impairs de 1 à 1023), ce qui veut dire que 1 serviteur devra goûter 512 bouteilles. Si la bouteille empoisonnée figure parmi elles il mourra au bout d'une heure, là-dessus nous sommes d'accord.

Mais comment savoir laquelle des 512 bouteilles est empoisonnée ?

[Sylviel]

Tu n'as pas l'air d'être très doué pour la déduction.

4 bouteille, 1 empoisonnée.

Gouteur A goute 1 et 2
Gouteur B goute 2 et 3.

1 heure après :
A et B vivant : c'est la 4 qui est empoisonnée
A mort, B vivant : c'est la 1 qui est empoisonnée
A vivant, B mort : c'est la 3 qui est empoisonnée
A et B mort : c'est la 2 qui est empoisonnée.

[syrac]

Avec 4 bouteilles on a : bouteille 1 = 001, bouteille 2 = 010, bouteille 3 = 011, bouteille 4 = 100. Il faut donc trois goûteurs, A, B et C. A goûte les bouteilles 1 et 3, B goûte la bouteille 2, et C goûte la bouteille 4.

Après une heure :

B est mort : la bouteille 2 est empoisonnée.
C est mort : la bouteille 4 est empoisonnée.
A est mort : quelle bouteille est empoisonnée, la 1 ou la 3 ?

[Robot]

Tu es vraiment à la masse ou tu fais semblant, juste pour troller ?
Bouteille 0 : 00 , bouteille 1 : 01, bouteille 2 : 10, bouteille 3 : 11
A goûte 10 et 11. B goûte 01 et 11