Au dîner du roi..

[syrac]

Tu es vraiment à la masse ou tu fais semblant, juste pour troller ?

Non, c'est juste que tu ne sais pas t'expliquer clairement du premier coup.

Bouteille 0 : 00 , bouteille 1 : 01, bouteille 2 : 10, bouteille 3 : 11
A goûte 10 et 11. B goûte 01 et 11

Et la bouteille 00, on n'y goûte pas ? On sait qu'elle est pas empoisonnée ?

Si je me réfère à ce que tu disais plus haut, "le goûteur n°i goûte toutes les bouteilles dont le i-ème bit du numéro est à 1", alors tu ne peux pas commencer la numérotation des bouteilles par 0, parce que tu retrouves avec un goûteur qui devra tester les bouteilles 01 et 11, et un autre qui devra tester les bouteilles 10 et ... quoi au juste ?

Mais supposons que comme tu le dis, A goûte 10 et 11 et que B goûte 01 et 11. Après une heure on aura :

A vivant, B vivant : ne peut pas arriver si l'une des bouteilles 01, 10 ou 11 est empoisonnée.
A vivant, B mort : la bouteille 01 est empoisonnée.
A mort, B vivant : la bouteille 10 est empoisonnée.
A mort, B mort : la bouteille 11 est empoisonnée.

J'espère pour le roi que ce n'est pas la bouteille 00 qui est empoisonnée !!

[Robot]

Encore un petit effort et tu finiras peut-être par comprendre (sauf si tu trolles, ce qui ne me semble pas exclu)
Si aucune des bouteilles 01, 10 et 11 n'est empoisonnée, quelle est la bouteille empoisonnée ?

[syrac]

Toujours en supposant qu'il y ait 1024 bouteilles, en suivant la piste binaire on se retrouve avec les couples suivants goûteur = nombre de bouteilles à tester :

A = 512, B = 256, C = 128, D = 64, E = 32, F = 16, G = 8, H = 4, I = 2, et J = 1.

En omettant le fait que les deux ou trois premiers auront probablement fait un comas éthylique avant d'en terminer, qui saurait calculer le nombre de morts maximal qu'on devra observer pour savoir que telle bouteille est empoisonnée ?

[syrac]

Encore un petit effort et tu finiras peut-être par comprendre (sauf si tu trolles, ce qui ne me semble pas exclu)
Si aucune des bouteilles 01, 10 et 11 n'est empoisonnée, quelle est la bouteille empoisonnée ?

Très juste. A vivant, B vivant : la bouteille 00 est empoisonnée.

[syrac]

sauf si tu trolles, ce qui ne me semble pas exclu

Non non, je ne trolle pas, je suis réellement plus con que la moyenne !

[Pseuda]

Autrement dit, on peut apparier les goûteurs à un ensemble à n éléments, et chaque bouteille à une partie de cet ensemble (pour que les tests puissent différencier les bouteilles). Tout le monde sait que le nombre de parties d'un ensemble à n éléments est : .

Pour obtenir 1000 bouteilles identifiables, il faut que cet ensemble soit tel que 1000, soit n=10.

Maintenant, s'il y a 2 bouteilles empoisonnées, au lieu de 1000 possibilités, il y en a 2 parmi 1000, soit 499 500 possibilités. Avec la même démarche, il faut que n soit tel que à ce nombre, soit n=19.

Me trompé-je ? Si non, est-ce plus clair comme cela ?

[Robot]

Oui, ça montre que 19 est une borne inférieure sur le nombre de goûteurs dans le cas de 2 bouteilles empoisonnées, ce qui a déjà été écrit. Mais ça ne donne pas de nombre de goûteurs suffisant.

[syrac]

@PSEUDA

Dans le cas de trois goûteurs A, B et C on aurait l'ensemble {A,B,C} et ses 2^3 = 8 sous-ensembles {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {A,B,C}, plus l'ensemble vide. Ils pourraient donc tester 8 bouteilles.

Si je comprends bien (ce dont je doute), il faudrait alors que A, B et C goûtent chacun une bouteille différente, en même temps que A et B testeraient en commun une bouteille, tout comme devraient le faire A et C ainsi que B et C. A quoi s'ajoute le fait que A, B et C devraient tester la même bouteille. On arrive à un total de 7 bouteilles. Si tout le monde est vivant une heure après, ça veut dire que l'unique bouteille non testée est empoisonnée.

C'est bien ça ?

EDIT : si c'est bon, ça répond à ma question ci-dessus : le nombre maximal de morts est égal au nombre de goûteurs.

[Robot]

Les bouteilles sont 000, 001, 010, 011, 100, 101, 110, 111.
A teste 100, 101, 110, 111 (1er bit à 1)
B teste 010, 011, 110, 111 (2e bit à 1)
C teste 001, 011, 101, 111 (3e bit à 1)

[syrac]

Les bouteilles sont 000, 001, 010, 011, 100, 101, 110, 111.
A teste 100, 101, 110, 111 (1er bit à 1)
B teste 010, 011, 110, 111 (2e bit à 1)
C teste 001, 011, 101, 111 (3e bit à 1)

Donc (goûteur = numéro de la bouteille goûtée)

A = 100
B = 010
C = 001
A et B = 110
A et C = 101
B et C = 011
A et B et C = 111

Comme précédemment, la bouteille 000 est empoisonnée si tout le monde sort vivant de l'aventure.

Une question se pose : existe-t-il une autre répartition possible des bouteilles, ou l'approche binaire permet-elle de trouver la seule répartition existante ? Ou encore, est-ce que ça vaut la peine de s'emmerder à répondre puisque les bouteilles sont de toute façon identiques ?

[Robot]

Le codage binaire des bouteilles est bien entendu arbitraire. A cet arbitraire-là près, c'est effectivement la seule façon de répartir les bouteilles qui convient.

[Ben314]

Dans le cas où n est une puissance de 2, c'est assez immédiat que la seule solution est celle avec le codage en base 2 (modulo le choix sur la numérotation des bouteilles).
Par contre, ça me semble moins clair dans le cas où n n'est pas une puissance de 2 : il y a évidement beaucoup plus de solution vu que, rien qu'en utilisant le codage en base 2, on peut numéroter les n bouteilles avec n'importe quelle partie à n éléments de {0,1,...,2^k-1} (où k est t.q. n<=2^k), mais ça me semble pas complètement clair que toutes les solutions seront de cette forme...

Sinon, concernant les 2 bouteilles parmi 1000 (avec une seule batterie de test), je pense avoir une solution avec 65 gouteurs.

[syrac]

La répartition des bouteilles est importante dans le sens où la vie ou la mort d'un nombre plus ou moins grand de goûteurs en dépend. Si on place les bouteilles sur une ligne et qu'on numérote par la gauche en commençant par 0, alors placer la bouteille empoisonnée à l'extrême droite tuera tout le monde.

Avec 8 bouteilles, placer celle qui est empoisonnée à la position 3, 5 ou 6 tuera deux goûteurs. La placer à la position 1, 2 ou 4 n'en tuera qu'une seule.

[Robot]

@ Ben : On en était à la discussion du cas de 8 bouteilles. Mais dans le cas général, c'est clair aussi : s'il y a un procédé sûr avec k goûteurs, mettre à chaque bouteille un code à k bits où le i-ème bit est à 1 si et seulement si la bouteille est goutée par le i-ème goûteur. Alors deux bouteilles différentes n'ont jamais le même code binaire.

[Robot]

La répartition des bouteilles est importante dans le sens où la vie ou la mort d'un nombre plus ou moins grand de goûteurs en dépend. Si on place les bouteilles sur une ligne et qu'on commence à numéroter par la gauche, alors placer la bouteille empoisonnée à l'extrême droite tuera tout le monde.

Avec 8 bouteilles, placer celle qui est empoisonnée à la position 4, 6 ou 7 tuera deux goûteurs. La placer à la position 2, 3 ou 5 n'en tuera qu'une seule.

Avec une hypothèse d'équiprobabilité (chaque bouteille a autant de chance d'être empoisonnée qu'un autre), la probabilité pour chaque goûteur de calancher est 1/2.

[syrac]

Avec une hypothèse d'équiprobabilité (chaque bouteille a autant de chance d'être empoisonnée qu'un autre), la probabilité pour chaque goûteur de calancher est 1/2.

je me plaçais dans le cas où on sait quelle bouteille est empoisonnée, ce qui permet de se débarrasser d'un nombre plus ou moins grand de gêneurs ou rivaux. Ça permet également de savoir, toujours dans le cas où la bouteille empoisonnée est connue, dans quel ordre distribuer les bouteilles aux goûteurs afin de se débarrasser de l'un d'eux en particulier, tout en essayant de minimiser les dommages collatéraux.

[Pseuda]

Oui, ça montre que 19 est une borne inférieure sur le nombre de goûteurs dans le cas de 2 bouteilles empoisonnées, ce qui a déjà été écrit. Mais ça ne donne pas de nombre de goûteurs suffisant.

Ah oui. Cela ne va pas du tout. Chacune des 2 bouteilles peut rendre malade, pas les 2 à la fois. Avec cette méthode, tous les goûteurs auront goûté à toutes les bouteilles, ils seront tous malades. Il faut plus de goûteurs qui boivent moins.

[syrac]

Je disais plus haut que le nombre maximal de morts était égal au nombre de goûteurs, mais il semble que ce ne soit pas toujours le cas. En effet, si b est le nombre de bouteilles alors elles sont numérotées de 0 à b-1. Le sous-ensemble {A,B,C}, dans le cas de trois goûteurs, ne se verra attribuer une bouteille que si b est une puissance de 2, auquel cas b-1 est impair et ne contient que des 1 (en base 2).

Si le nombre de bouteilles n'est pas une puissance de 2 alors il y aura toujours au moins un survivant.

[Ben314]

Si on se pose la question (différente) de savoir comment faire pour avoir le moins possible de morts, la réponse est évidente : chaque gouteur goute UNE et une seule bouteille -> un mort si une seule est empoisonnée et deux morts si deux bouteilles empoisonnées.
Donc c'est sans intérêt (mathématique) comme question.

Et si on prétend vouloir minimiser à la fois le nombre de gouteur ET le nombre de mort, ben la question n'a mathématiquement parlant pas de sens vu qu'il n'y a pas de relation d'ordre naturelle sur N² (donc il faut en définir une si on veut que la question ait du sens)

[syrac]

Si on se pose la question (différente) de savoir comment faire pour avoir le moins possible de morts, la réponse est évidente : chaque gouteur goute UNE et une seule bouteille -> un mort si une seule est empoisonnée et deux morts si deux bouteilles empoisonnées.

Oui, mais dans ce cas il faudrait autant de goûteurs que de bouteilles, ce qui nous ramène à ma première intervention dans ce fil.

Pour réduire le nombre de morts à 1 il faudrait qu'au moins une personne sache quelle bouteille est empoisonnée et s'arrange pour qu'elle ne soit attribuée qu'à un seul goûteur {A}, {B}, {C}, etc. Cette personne peut en fait décider à l'avance du nombre de morts qu'elle fera.