FuretFruit
Il faut trouver l'invité dans les 48 heures qui suivent?
Topic : « Légère énigme du soir qui mets en sang avenoel ¯\_(ツ)_/¯ »
FuretFruit
EnfantTerrible
ils trinquent comme ca tout le monde meurt: une goute suffit a tuer et quand on trinque on a une partie de son verre qui va dans l'autre et tout le monde trinque.
Factom
Citation de FuretFruit
Il faut trouver l'invité dans les 48 heures qui suivent?
Oui ! Sinon il s'enfuit à tout jamais dans la nature !
GenieKetamer
On demande aux invités de boire chacun une grosse liche de la bouteille qu'ils ont amené pour inaugurer le banquet et on attend 24h 
c'est un cadeau à la base et ils seraient mécontent de voir qu'on les suspecte 
geekborg
Le poison met 24h pour agir et les invités partent dans 48h.
Donc ça fait que chaque serviteur doit se taper 5 bouteilles par jour (5*10 = 50 et 50*2=100).
Bon après la suite je vois pas.
Donc ça fait que chaque serviteur doit se taper 5 bouteilles par jour (5*10 = 50 et 50*2=100).
Bon après la suite je vois pas.
EnfantTerrible
La première approche qui semble évidente est de prendre un serviteur pour chaque bouteille, et ainsi de voir qui meurt, pour trouver le poison. Ceci nous ferait 1000 serviteurs utilisés, on peut mieux faire.
Sans contrainte de temps, on aurait pu ensuite penser à une dichotomie : puisque le vin empoisonné est mortel même à petite dose, on pourrait faire des mélanges de vin. On sépare nos 1000 bouteilles en deux groupes, ce qui nous fait deux mélanges, qu'on fait gouter à deux serviteurs. On recoupe ensuite en deux le groupe du serviteur mort, etc, jusqu'à isoler le poison. A chaque étape on réutilise le serviteur qui n'est pas mort à l'étape précédente (ça fait vraiment tyran, mais c'est l'énonce qui est comme ça, je délègue toute responsabilité à l'auteur original). Ainsi, le nombre de serviteurs mobilisés serait égal au nombre de divisions de l'espace qu'on a du faire. Notons k ce nombre. On a du couper k-fois notre espace en deux afin d'arriver à 1. 10002k=1
2k=1000 ekln(2)=1000
k=ln(1000)ln(2)
On arrondit k à l'entier supérieur (on doit faire toutes les divisions de l'espace nécessaires, pas moins), ce qui nous fait 10.
Mais cette approche ne fonctionne que sans contrainte de temps, donc n'est pas viable ici.
On pourrait ensuite penser différement en se disant que un esclave peut gouter plusieurs bouteilles (ce qui est équivalent à la technique du mélange). Imaginons que nous repartitions les bouteilles dans une salle de sorte à ce qu'elles forment un carré (plus une rangée non complète car on ne peut pas faire un carré avec 1000 bouteilles). On associe à chaque rangée (colonnes et lignes) un serviteur. Celui-ci boit toute sa rangée. Ainsi, l'intersection des rangées des deux serviteurs morts nous donne la bouteille empoisonée. Ici on trouve sqrt(1000) = 31,6..., on fait prend donc un rectangle de 31*32 = 992, et on rajoute une rangée incomplète de 8, ce qui nous fait 64 serviteurs utilisés. C'est pas mal. Mais on peut encore faire mieux.
Les points rouges sont des serviteurs, les carrés noirs des bouteilles
Le vert représente le poison. On trouve la bouteille empoisonée.
En fait le fait qu'un serviteur meurt ou non nous donne de l'information. Ce qu'on doit trouver, c'est comment cette information peut nous permettre d'identifier la bouteille empoisonée. Qu'à cela ne tienne, nous allons identifier chaque bouteille par un nombre binaire unique, et chaque serviteur par un numero (non binaire celui-ci).
Ce nombre binaire comportera autant de bits que de serviteurs, et la position d'un bit dans le mot correspondra à un numéro de serviteur. Si ce bit est à 1, alors cela signifie que ce serviteur aura bu dans cette bouteille.
Par exemple la bouteille 3 sera codée 0110 (si on code sur 4 bits, c'est à dire 4 serviteurs), ce qui signifie que les serviteurs 2 et 3 auront bu dedans.
Une fois que tout le monde a bu, on regarde les numéros des décédés : tous on leur bit à 1 dans la bouteille empoisonée, leur mort nous apporte l'information nécessaire.
Si par exemple on avait le serviteur 1 et le 3 de mort, alors la bouteille correspondante serait (0101), c'est à dire la numéro 5 !
Combien de serviteurs cette technique demande-t-elle? Il en faut assez pour encoder de manière unique chaque bouteille, donc il faut : , ce qui nous donne k = 10 serviteurs (même démo que précédemment).
Sans contrainte de temps, on aurait pu ensuite penser à une dichotomie : puisque le vin empoisonné est mortel même à petite dose, on pourrait faire des mélanges de vin. On sépare nos 1000 bouteilles en deux groupes, ce qui nous fait deux mélanges, qu'on fait gouter à deux serviteurs. On recoupe ensuite en deux le groupe du serviteur mort, etc, jusqu'à isoler le poison. A chaque étape on réutilise le serviteur qui n'est pas mort à l'étape précédente (ça fait vraiment tyran, mais c'est l'énonce qui est comme ça, je délègue toute responsabilité à l'auteur original). Ainsi, le nombre de serviteurs mobilisés serait égal au nombre de divisions de l'espace qu'on a du faire. Notons k ce nombre. On a du couper k-fois notre espace en deux afin d'arriver à 1. 10002k=1
2k=1000 ekln(2)=1000
k=ln(1000)ln(2)
On arrondit k à l'entier supérieur (on doit faire toutes les divisions de l'espace nécessaires, pas moins), ce qui nous fait 10.
Mais cette approche ne fonctionne que sans contrainte de temps, donc n'est pas viable ici.
On pourrait ensuite penser différement en se disant que un esclave peut gouter plusieurs bouteilles (ce qui est équivalent à la technique du mélange). Imaginons que nous repartitions les bouteilles dans une salle de sorte à ce qu'elles forment un carré (plus une rangée non complète car on ne peut pas faire un carré avec 1000 bouteilles). On associe à chaque rangée (colonnes et lignes) un serviteur. Celui-ci boit toute sa rangée. Ainsi, l'intersection des rangées des deux serviteurs morts nous donne la bouteille empoisonée. Ici on trouve sqrt(1000) = 31,6..., on fait prend donc un rectangle de 31*32 = 992, et on rajoute une rangée incomplète de 8, ce qui nous fait 64 serviteurs utilisés. C'est pas mal. Mais on peut encore faire mieux.
Les points rouges sont des serviteurs, les carrés noirs des bouteilles
Le vert représente le poison. On trouve la bouteille empoisonée.
En fait le fait qu'un serviteur meurt ou non nous donne de l'information. Ce qu'on doit trouver, c'est comment cette information peut nous permettre d'identifier la bouteille empoisonée. Qu'à cela ne tienne, nous allons identifier chaque bouteille par un nombre binaire unique, et chaque serviteur par un numero (non binaire celui-ci).
Ce nombre binaire comportera autant de bits que de serviteurs, et la position d'un bit dans le mot correspondra à un numéro de serviteur. Si ce bit est à 1, alors cela signifie que ce serviteur aura bu dans cette bouteille.
Par exemple la bouteille 3 sera codée 0110 (si on code sur 4 bits, c'est à dire 4 serviteurs), ce qui signifie que les serviteurs 2 et 3 auront bu dedans.
Une fois que tout le monde a bu, on regarde les numéros des décédés : tous on leur bit à 1 dans la bouteille empoisonée, leur mort nous apporte l'information nécessaire.
Si par exemple on avait le serviteur 1 et le 3 de mort, alors la bouteille correspondante serait (0101), c'est à dire la numéro 5 !
Combien de serviteurs cette technique demande-t-elle? Il en faut assez pour encoder de manière unique chaque bouteille, donc il faut : , ce qui nous donne k = 10 serviteurs (même démo que précédemment).
Factom
Je valide également le pavé ultra long qui résume aussi tout ce qui a été proposé 
Scorpion
Il y a d'autres solutions valables hein
Factom
Citation de EnfantTerrible
EnfantTerrible
Citation de Factom
Citation de EnfantTerrible
Factom
Le fameux 5ème qui trouve ça 
FuretFruit
J'ai pas compris la soluce 
Factom
Citation de FuretFruit
J'ai pas compris la soluce
En gros faut numéroter les bouteilles
Et t'écris les nombres en binaire : 01000000 pour la 2ème bouteille par exemple
Et chaque serviteur corresponds à un "bit", donc il boit si ya un 1
En regardant ceux qui sont mort ou pas t'as exactement l'écriture avec des 0 et des 1 donc le numéro de la bouteille
Tu peux faire ça si k le nombre de serviteurs est tel que 2^k > 1000, ici c'est le cas car 2^10=1024
EnfantTerrible
nofake no arnaque j'ai 13 ans> >>Factom
on me croit toujours pas pour ma classe?
Citation de FuretFruitEn gros faut numéroter les bouteilles
J'ai pas compris la soluce
Et t'écris les nombres en binaire : 01000000 pour la 2ème bouteille par exemple
Et chaque serviteur corresponds à un "bit", donc il boit si ya un 1
En regardant ceux qui sont mort ou pas t'as exactement l'écriture avec des 0 et des 1 donc le numéro de la bouteille
Tu peux faire ça si k le nombre de serviteurs est tel que 2^k > 1000, ici c'est le cas car 2^10=1024
on me croit toujours pas pour ma classe?
FuretFruit
Citation de Morfalou
Citation de FuretFruitIl faut que plusieurs serviteurs boivent des mêmes bouteilles. Quand t'as la "triplette gagnante" tu sais quelle bouteille ils ont bu en commun, donc tu connais le coupable.
J'ai pas compris la soluce
Il y a mille bouteilles, comment tu peux savoir quelle bouteille est la bonne alors qu'ils en auront bu au moins une centaine chacun?
Honteux
Citation de Morfalou
Citation de FuretFruitIl faut que plusieurs serviteurs boivent des mêmes bouteilles. Quand t'as la "triplette gagnante" tu sais quelle bouteille ils ont bu en commun, donc tu connais le coupable.
J'ai pas compris la soluce
Ah j'ai enfin compris
