Au dîner du roi..

[Pseuda]

@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.

C'est bien cela. Les goûteurs sont un ensemble {A,B,C}, et on apparie les parties de cet ensemble aux bouteilles : = bouteille 1, {A}= bouteille 2, etc...
On regarde les malades (je préfère parler de malades, l'énoncé ne précise pas, bien que tu aies l'air d'affectionner quelque chose de plus grave), cela donne la bouteille empoisonnée.

Malheureusement, cette méthode ne marche pas avec 2 bouteilles, et je n'ai pas le temps de voir comment l'adapter pour que ça marche. En considérant des bouteilles mises par couple, ça ne marche pas parce qu'un couple veut dire "et", et non pas "ou".

Oui, le nombre maximal de malades est égal au nombre de goûteurs (les 3 goûteurs ont bu la bouteille 8), si on ne compte pas le roi au cas où les goûteurs se soient trompés . Et chacun des goûteurs a bu 4 bouteilles (dans un autre registre, le digit O/N qui lui correspond).

[syrac]

je préfère parler de malades, l'énoncé ne précise pas, bien que tu aies l'air d'affectionner quelque chose de plus grave

Quand on met du poison dans une bouteille destinée au roi (ou à n'importe qui du reste) c'est certainement pour le faire passer de vie à trépas, pas pour le rendre malade.

Je suppose que tu as très peur de la mort, au point d'utiliser ce mot avec réticence...

[Pseuda]

je préfère parler de malades, l'énoncé ne précise pas, bien que tu aies l'air d'affectionner quelque chose de plus grave

Quand on met du poison dans une bouteille destinée au roi (ou à n'importe qui du reste) c'est certainement pour le faire passer de vie à trépas, pas pour le rendre malade.

Je suppose que tu as très peur de la mort, au point d'utiliser ce mot avec réticence...

Ah, ton sens de la déduction est toujours aussi aiguisé, comme le prouvent tes précédents messages...

Non, je n'aime pas le macabre, c'est tout (genre films d'horreurs). Je suis tournée vers la vie, comme peut l'être une mère qui a eu 3 enfants. Je pense au contraire que ce sont ceux qui en parlent à tort et à travers qui en ont le plus peur (comme pour exorciser un mauvais sort). La souffrance me fait beaucoup plus peur que la mort.

Bref, pour terminer sur une note plus optimiste, les goûteurs ne devraient pas avaler toute la bouteille empoisonnée (il faut qu'il en reste un peu pour les autres qui goûtent aussi, et pour le roi au cas où elle ne serait pas empoisonnée). Ils devraient être moins atteints que le roi, qui lui, on le connait, va la boire en entier... Ils pourront recommencer avec un autre roi, si jamais ils se trompent, surtout avec les 2 bouteilles, parce que pour l'instant on n'a pas encore trouvé la solution...

[syrac]

Non, je n'aime pas le macabre, c'est tout (genre films d'horreurs). Je suis tournée vers la vie, comme peut l'être une mère qui a eu 3 enfants. Je pense au contraire que ce sont ceux qui en parlent à tort et à travers qui en ont le plus peur (comme pour exorciser un mauvais sort). La souffrance me fait beaucoup plus peur que la mort.

On déborde du sujet, mais en 2014 j'ai traduit pour mes proches le livre d'une hypnothérapeute américaine qui traite d'une manière extraordinaire la question de la souffrance et de la mort, au point que c'en est un hymne à la vie. Je ne peux pas mettre le PDF en ligne parce que ce n'est pas une traduction officielle, mais si tu m'indiques ton email par MP je te l'enverrai. Si bien sûr le sujet t'intéresse...

Ah, ton sens de la déduction est toujours aussi aiguisé, comme le prouvent tes précédents messages...

J'ai des amis avec lesquels il ne faut jamais prononcer le mot "mort", tellement ça leur fait peur. Et toute leur famille est dans ce cas. D'où ma "déduction". Je leur ai bien entendu envoyé le livre en question.

[Pseuda]

Hum, désolée, non merci Syrac.

[Ben314]

Par exemple, vu que tu (syrac) parle de Troll dans l'autre post, tu peut me dire quel est le c... de première qui a mis au moins 30 posts sans le moindre début d'intérêt (et pour plus de la moitié sans aucun lien avec la question) dans ce fil qui était très intéressant ?

[nodgim]

Je propose ici une solution avec 59 goûteurs et 59*17=1003 bouteilles pour distinguer 2 bouteilles parmi ces 1003.

Avec 17 formats de code distincts, composés chacun de 2 à 5 bits à 1 sur 59 bits. Ces 59 bits sont placés en cercle, ce qui fait que pour un format donné, il y a 59 positions possibles.

Formats:
11
1001001 (ou 22, si on compte les zéros intermédiaires par simplification d'écriture)
33
44
555
66
777
88
999
10.10
11.11.11.11
12.12
13.13.13
14.14
15.15.15.15
16.16
17.17.17.17

Les codes ont été choisis pour que la fusion de 2 quelconques d'entre eux donne un code fusionné unique. Le nombre de codes fusionnés est de 1003*1002/2=502 503.

Il n'y a pas eu de test informatique pour valider que tous les codes fusionnés sont distincts. Seul ce travail permettrait d'avoir cette assurance.

[Ben314]

Sauf erreur, ça déconne :
Si on prend ton 5em format (non décalé) : X = 1000001000001000001
et ton 3em format (non décalé) : Y = 100010001
Alors la "fusion" donne XouY = 1000101010001000001

D'un autre coté, si on prend ton 3em format "décalé" de 4 : X' = 0000100010001
Alors la "fusion" donne X'ouY = 1000101010001000001

C'est à dire XouY = X'ouY

[nodgim]

Sauf erreur, ça déconne :
Si on prend ton 5em format (non décalé) : X = 1000001000001000001
et ton 4em format (non décalé) : Y = 100010001
Alors la "fusion" donne XouY = 1000101010001000001

D'un autre coté, si on prend ton 4em format "décalé" de 4 : X' = 0000100010001
Alors la "fusion" donne X'ouY = 1000101010001000001

C'est à dire XouY = X'ouY

Salut Ben,
Et merci de porter un oeil critique à cet essai. La mise au point n'est pas simple, et l'analyse forcément incomplète.
Tu as bien trouvé un bug avec 555+33=555+(33 décalé). C'est un aspect que je n'ai pas vu, il risque de ne pas être unique. J'ignore si ça se peut se réparer, en tout cas pas facilement. Il semble que le plus à redouter est un nombre impair de zéros consécutifs, à cause de la symétrie (raison pour laquelle j'avais choisi 555 et non 55).

[nodgim]

2ème essai. On parle du test unique pour distinguer 2 bouteilles parmi 59*17=1003. (59 goûteurs)
On a 17 format de 3 bits à 1 sur 59 bits. Les 59 bits sont placés en cercle, ce qui a pour conséquence qu'un format est utilisé 59 fois.

Formats
ici la désignation du format se fait par un double chiffre qui traduit la longueur d'une séquence répétée 2 fois. La séquence commence à 1 et le reste sont des zéros. On ajoute 1 à la fin des 2 séquences.
22 (c'est à dire 10101)
44 (100010001)
55
77
88
10.10
11.11
13.13
14.14
16.16
17.17
18.18
19.19
20.20
22.22
23.23
25.25

On remarquera que pour un format n, les formats 3n et 3/2 n ne peuvent être présents.
Exemple: 22 et 33 incompatibles car:
10101+
1001001=
...10101+
1001001

[Ben314]

Format 22 décalé de 0 => X=101010000
Format 22 décalé de 4 => Y=000010101
X ou Y = 101010101

Format 22 décalé de 2 => X'=001010100
Format 44 décalé de 0 => Y'=100010001
X' ou Y' = 101010101

il me semble que c'est d'ailleurs l'exemple que tu donne de ce qu'il ne faut pas prendre, non ?

Sinon, a mon avis, si tu veut un peu augmenter le nombre de chances que ça marche, il me semble préférable que chaque gouteur teste environ 290 bouteilles (pour que chaque "test" divise à peu prés par 2 le nombre de cas favorables) donc perso., je mettrais plutôt 17 bits à 1 dans chaque "format".

[Doraki]

En tirant au sort des sous-ensembles de 293 bouteilles jusqu'à pouvoir distinguer tous les cas,
mon pc a découvert des solutions à 57,54, et 60 gouteurs.

(après j'en ai eu marre)

[Ben314]

Tu as mis des contraintes sur le cardinal des "intersections" de deux gouteurs ou tu as laissé faire le hasard ?
Et lorsque tu as pas assez de gouteurs pour distinguer tout les cas, tu cherche un nouveau gouteur qui permet de distinguer deux cas donnant le même résultat ou pas ?

[Doraki]

Non je laisse faire le hasard complètement. Après tout si je me souviens bien il faut faire semblant à ce que les ensembles soient "indépendants" pour que ce soit rentable, donc j'ai laissé faire.

Y'a une alternative encore plus basique à tester c'est de ne pas forcer le cardinal des parties (293 éléments) mais juste prendre chaque bouteille indépendamment avec proba 0.29275...

Honnêtement je m'attendais à obtenir des solutions plus petites

[nodgim]

Sinon, a mon avis, si tu veut un peu augmenter le nombre de chances que ça marche, il me semble préférable que chaque gouteur teste environ 290 bouteilles (pour que chaque "test" divise à peu prés par 2 le nombre de cas favorables) donc perso., je mettrais plutôt 17 bits à 1 dans chaque "format".

Peut être, mais je cherche avant tout une solution qui soit "lisible" sans avoir besoin de faire une liste exhaustive.
Ici, en tenant compte des contraintes : si format n, alors les formats 2n, 3n et 3/2n ne marchent pas, on peut avancer :

Formats
2 (10 10 1)
5 (10000 10000 1)
7,8,11,13,17,18,19,20,23,25,28,31,32,35,37.

Toutes les contraintes ne sont pas listées, et si on en reste avec 59 goûteurs, on remarque que certains formats sont proches ou dépassent un tour complet, ce qui induit des contraintes supplémentaires à vérifier.

Il faut peut être que je cherche plus modeste mais plus sûr au début.

[general7star]

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 ?

Comment sont calculées les 499 500 possibilités?

[Sylviel]

@general : il s'agit de nombre de manière possible de choisir 2 numéro parmi 1000.
Pour le premier tu as 1000 possibilité, pour le second 999, et dans ce cas tu as compté deux fois tout le monde (45,299) et (299,45). Il y a donc au total 1000*999/2 possibilités. Pour généraliser on parle de combinaison et d'arrangements (google t'en apprendra plus).

[Mr Hall]

Une bouteille sur 1000 est empoisonnée. Par conséquent, avec environ 693 goûteurs, la probabilité atteint 50% de découvrir la bouteille empoisonnée, et environ 4603 goûteurs pour que la probabilité atteigne 99%. La probabilité est asymptotique quand le nombre de goûteurs croît : P(x) = 1 - (1 - (1/1000))^x, où x est le nombre de goûteurs.

Je connais une situation similaire : dans le jeu MMORPG "Elite Dangerous", qui est du genre "space opera", il existe 400 milliards de systèmes stellaires, et en supposant que les 500 000 à 800 000 joueurs partent explorer la galaxie au hasard, le nombre cumulé de systèmes stellaires découverts en fonction du temps tend à décélérer (asymptote). La courbe est une croissance logarithmique. Que ce soit l'exploration galactique dans Elite ou la découverte de la bouteille empoisonnée, cela peut nécessiter beaucoup de temps ou beaucoup de participants.

[general7star]

Une bouteille sur 1000 est empoisonnée. Par conséquent, avec environ 693 goûteurs, la probabilité atteint 50% de découvrir la bouteille empoisonnée, et environ 4603 goûteurs pour que la probabilité atteigne 99%. La probabilité est asymptotique quand le nombre de goûteurs croît : P(x) = 1 - (1 - (1/1000))^x, où x est le nombre de goûteurs.

Je connais une situation similaire : dans le jeu MMORPG "Elite Dangerous", qui est du genre "space opera", il existe 400 milliards de systèmes stellaires, et en supposant que les 500 000 à 800 000 joueurs partent explorer la galaxie au hasard, le nombre cumulé de systèmes stellaires découverts en fonction du temps tend à décélérer (asymptote). La courbe est une croissance logarithmique. Que ce soit l'exploration galactique dans Elite ou la découverte de la bouteille empoisonnée, cela peut nécessiter beaucoup de temps ou beaucoup de participants.

Euh... à partir de 10 goûteurs, la probabilité de découvrir la bouteille empoisonnée est de 100% en supposant qu'ils peuvent boire plus d'une bouteille et qu'il est un assemblage optimal. Avec une bouteille chacun, c'est 999 goûteurs. Tu dois probablement parler si les goûteurs choisissent une bouteille au hasard?

[general7star]

@general : il s'agit de nombre de manière possible de choisir 2 numéro parmi 1000.
Pour le premier tu as 1000 possibilité, pour le second 999, et dans ce cas tu as compté deux fois tout le monde (45,299) et (299,45). Il y a donc au total 1000*999/2 possibilités. Pour généraliser on parle de combinaison et d'arrangements (google t'en apprendra plus).

Si je te suis bien, on généraliserait avec log((nbr de bouteilles^nbr de bouteilles empoisonnées - b.*(e.-1))/e.) / log2


Ce qui donne parfois des réponses très, très, très incohérentes...