Au dîner du roi..

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

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?

En effet, en réexaminant la problématique, je me dois de modifier quelque chose.

Premier contexte : une bouteille par goûteur, une bouteille l'une après l'autre au hasard jusqu'à tomber sur la bouteille empoisonnée. Mais pour chaque bouteille saine identifiée, la probabilité de découvrir la bouteille empoisonnée augmente peu à peu (comme lors d'un tirage au hasard sans remise).

Deuxième contexte : un seul goûteur peut tester plusieurs bouteilles, mais le poison agit en une heure seulement. Devant l'urgence, il faut trouver rapidement la bouteille empoisonnée, et pour cela il faut nécessairement plusieurs goûteurs simultanément.

Donc pour reprendre le premier contexte ci-dessus, avec 200 essais dans une simulation informatique, en moyenne il faut 515 goûteurs plus ou moins 299. Sur 200 essais, le nombre minimum de goûteurs est de 28, et la valeur maximum est 998. Mais ça c'est quand on a une bouteille unique par goûteur. Avec un seul goûteur pour un maximum de bouteille, comme le poison agit en une heure, on n'aurait pas le temps d'identifier la mauvaise bouteille.

J'avais évoqué une courbe asymptotique mais la situation n'est pas exactement la même que pour mon exemple à propos du jeu MMORPG, car la situation du dîner du roi est un tirage de bouteilles sans remise.

[general7star]

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:

J'ai trouvé n(6)=4 et n(7)=5...

[Sylviel]

Ah, comment fais-tu pour n(6) = 4 ?

[general7star]

Ah, comment fais-tu pour n(6) = 4 ?

Je suis allé explorer du côté des combinaisons et permutations comme on m'a conseillé sur le forum...

log (6 nCr 2) / log (2) = 3.907, soit 4 serviteurs.

[Sylviel]

Hum... Les permutations et combinaison ne donnent a priori qu'une borne inf. J'aurais besoin d'un argument un peu plus précis, par exemple une stratégie explicite...

[Pseuda]

Bonjour,

Ce problème me paraît inextricable (j'ai essayé plusieurs méthodes, toutes vouées à l'échec), mais je n'ai peut-être pas le niveau.

Si j'avais le temps, j'essaierais cette méthode, qui consiste à rajouter une contrainte supplémentaire (au moins dans un 1er temps, ou bien démontrer que cette contrainte n'en est pas une), celle par exemple que les goûteurs goutent tous le même nombre de bouteilles (comme dans le cas d'une seule bouteille : tous les goûteurs boivent la moitié des bouteilles), et ne considérer qu'une puissance de 2 pour le nombre de bouteilles :

N=le nombre de bouteilles est donné (1024)
n = nombre de goûteurs (à faire varier)
k = nombre de tests fait par chacun d’eux (à faire varier)
nombre de possibilités = k parmi n

Il faut que n et k soient tels que : la juxtaposition de toutes ces possibilités ne donnent qu’une seule solution dans le problème avec N bouteilles et 2 bouteilles empoisonnées.

[Romy]

A moins de goûter au pire 999 bouteilles, peut-on conclure sur le contenu de l'unique bouteille parmi 1000 ?

[general7star]

Hum... Les permutations et combinaison ne donnent a priori qu'une borne inf. J'aurais besoin d'un argument un peu plus précis, par exemple une stratégie explicite...

J'ai donné ma formule...

Les bouteilles sont codées en binaire, le reste est pas mal expliqué en long et en large dans le sujet...

[Sylviel]

Non tu as donné une formule sans justification. Dans le sujet il n'y a que des bornes inf d'annoncée, pas de calcul exact. Donc pour le moment pas de preuve.

[Pseuda]

Bonjour,

Il est certain que n(6)=5, et pas 4.

En effet, on peut coder les bouteilles à l'inverse de ce qui a été pour le cas d'une seule bouteille empoisonnée, c'est -à-dire avec : 0=bouteille testée, 1 = bouteille pas testée. Ceci permet d'obtenir plus facilement les codes pour les couples de bouteilles, en multipliant pour chaque couple de bouteilles les digits correspondant à chaque testeur (exemple : 0111*1101=0101).

Essayons avec 4 testeurs pour 6 bouteilles, dont 2 empoisonnées. Il y a 4 testeurs : cela permet d'avoir 2^4=16 combinaisons de testeurs malades ou non. Il y a 6 bouteilles empoisonnées : il faut 2 parmi 6 = 15 combinaisons pour distinguer les couples de bouteilles. Cela paraît donc suffisant.

Les codes des bouteilles sont par exemple les suivants (en colonne, les testeurs) :
B1=1111 : la bouteille n'a pas été testée
B2=1110 : la bouteille a été testée par le testeur 4 seul,
B3=1101 : la bouteille a été testée par le testeur 3 seul,
B4=1100 : la bouteille a été testée par les testeurs 3 et 4 seuls,
etc...
On obtient les codes pour les couples de bouteilles empoisonnées :
B1B2=1110 (obtenu en multipliant les digits de B1 et B2 colonne par colonne) : si B1B2 est le couple empoisonné, le testeur 4 seul est malade,
etc...

On part du principe que les codes choisis pour les 6 bouteilles sont tous différents (sinon on ne pourrait pas les distinguer). Le but du problème est donc de choisir 6 codes (à 4 digits) pour les 6 bouteilles, de telle façon que les codes des 15 couples de bouteilles (obtenus en faisant les produits) soient tous différents (afin d'identifier pour une combinaison de testeurs malades, le couple de bouteilles empoisonnées de manière unique).

En partant des 16 combinaisons possibles pour les couples de bouteilles, on s'aperçoit que la combinaison 1111 n'est pas possible (il faudrait que 2 bouteilles aient la même combinaison 1111). Il n'en reste donc plus que 15 possibles.
La combinaison 1110 (testeur 4 seul malade) peut être attribuée par exemple à B1=1111, et B2=1110 ou l'inverse. Prenons B1=1111 et B2=1110 par exemple. La combinaison 1101 doit être attribuée à B3=1101 et B1 (cela ne peut pas être B2). Puis 1100=B2B3, 1011=B1B4 avec B4=1011, 1010=B4B2, 1001=B4B3. On aboutit à 1000 = non attribuable. En effet, si on pose B5=1001, on a : 1000=B2B5, mais on ne peut plus distinguer B1B5 de B3B4, etc… . Cela fait une 2ème combinaison impossible, il n'en reste plus que 14, donc n(6)<>4, n(6)=5.

[Romy]

Bonjour à tous,

Ce problème n'ayant toujours pas été attesté dans sa résolution, j'ai retrouvé l'énoncé d'origine après avoir saisi un article sur le même thème : http://www.bibmath.net/forums/viewtopic.php?id=6006&cprotect=1
Le temps est un paramètre modifié mais le principe demeure similaire. Des indications peuvent être fournies.
--------------------------------------------------------------------------------------------------------------------------------------
Le Président à vie d'un régime dictatorial décide de donner une petite garden party dans les jardins du 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) ?

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

C'est le premier sujet d'un puzzle analytique difficile : http://www.folj.com/puzzles/very-diffic ... uzzles.htm
---------------------------------------------------------------------------------------------------------------------------------------
L'empereur : Vous êtes le dirigeant d'un empire médiéval et vous êtes sur le point d'avoir une célébration demain. La célébration est la fête la plus importante que vous avez déjà hébergée. Vous avez 1000 bouteilles de vin que vous envisagez d'ouvrir pour la célébration, mais vous trouvez que l'une d'elles est empoisonnée.

Le poison ne présente pas de symptômes jusqu'à la mort. La mort survient dans les dix à vingt heures après avoir consommé une quantité même infime de poison.

Vous avez plus d'un millier d'esclaves à votre disposition et un peu moins de 24 heures pour déterminer quelle bouteille unique est empoisonnée.

Vous avez une poignée de prisonniers sur le point d'être exécutés, et votre fête serait gâchée par l'action d'avoir tué quelqu'un d'autre .

Quel est le plus petit nombre de prisonniers à qui vous devez faire boire des bouteilles afin d'être absolument sûr de trouver la bouteille empoisonnée dans les 24 heures?

[Ben314]

Oui, mais dans les deux cas, c'est bel et bien le problème archi classique où il n'y a qu'une seule bouteille empoisonnée et où la stratégie optimale est très facile a trouver (en tout cas quand on a des rudiments d'algorithmique...).
Ici, tout le problème consiste a essayer de dire quelque chose de non trivial concernant le cas où deux (voire plus...) bouteilles sont empoisonnées.
On a trivialement le minorant classique 2^(nombre_de_tests Vrai/Faux) >= Nombre_de_possibilités , mais après essais par de multiples intervenant pour les petites (ou moyennes) valeurs de n, il semble clair qu'il y a des obstruction de type combinatoire au fait de pouvoir atteindre ce minorant.
Sauf que personne ne trouve lesquelles...

[Romy]

On numérote toutes les bouteilles à l'aide de chiffres binaires et attribue à chaque prisonnier un des drapeaux binaires. Les prisonniers doivent prendre une gorgée de chaque bouteille, où leur indicateur binaire est réglé.

Une manière de détecter une bouteille empoisonnée sur huit bouteilles totales de vin avec trois prisonniers :
si tous les prisonniers meurent, la bouteille 8 est empoisonnée; mais si aucun ne meurt, la 1 est empoisonnée.
1 2 3 4 5 6 7 8
Prisonnier a X X X X (choix de 3, 4, 7, 8)
Prisonnier b X X X X (choix de 2, 4, 6, 8)
Prisonnier c X X X X (choix de 5, 6, 7, 8)
Le nombre de prisonniers pour 1024 bouteilles peut s'obtenir en faisant boire à chacun la moitié de bouteilles.

[Doraki]

J'ai une solution générale qui demande environ (log2 n)²/2 tests (pour 2 bouteilles empoisonnées (d'ailleurs ça marche pour un nombre inconnu de bouteilles empoisonnées entre 0 et 2))

Pour n entre 513 et 1024 ça demande 65 tests, donc c'est pas optimal vu qu'il y a des solutions plus petites, mais je pense que c'est pas mal.

[nodgim]

En proposant ce sujet sur un autre site, un programme a été mis au point et permet de sortir 1000 nombres avec 27 bits seulement (on est dans le problème initial, à savoir le nombre mini de goûteurs pour détecter 2 bouteilles empoisonnées).
L'idée est de sortir au hasard des nombres de 8 bits à 1 parmi 27. Au départ, c'était des nombres de 4 bits à 1 parmi 40, et il s'est avéré qu'après de nombreux essais, c'est pour l'instant un résultat optimal, du moins dans cette idée.
Je donne ci-après le programme, mais n'étant pas du tout programmeur, je ne pourrai répondre à vos éventuelles questions. Toutefois, je peux les transmettre à l'auteur.

#!/usr/bin/env python3
# -*- encoding: utf-8 -*-
#
# enigmatus mai 2016 (sur une idée de nodgim)
#
import sys
from itertools import combinations as C
from random import seed, shuffle
from time import time

#seed(0)
k=0
k+=1;N=int(sys.argv[k]) # Nb de bits
k+=1;M=int(sys.argv[k]) # Nb de bits choisis à 1
try: k+=1;B=int(sys.argv[k]) # Nb de nombres voulu
except IndexError: B=None
try: k+=1;NN=int(sys.argv[k]) # Nb max de tirages
except IndexError: NN=None
#-------------------------------------------------
def bi(n,l):
# Représentation binaire de n sur l bits
s=bin(n)[2:]
ret='0'*(l-len(s))+s
return ret
cods=[]; soms=set()
#-------------------------------------------------
def gener_bits():
# Génération dans un ordre aléatoire des combinaisons de M bits pris parmi N
lst=list(C(range(N),M))
shuffle(lst)
for bits in lst: yield bits
return
#-------------------------------------------------
def gener_cod():
# Génération et test des encodages
global soms, nn
genbits=gener_bits()
nn=0
while not NN or nn<NN:
try: bits=next(genbits)
except StopIteration: print('\nFini : Combinaisons épuisées=%d'%nn); break
nn+=1
cod=0
for k in bits: cod+=1<<k
deja=False
som_new=set()
for cod0 in cods:
som=cod0|cod
if som in som_new or som in soms: deja=True; break
else: som_new.add(som)
if not deja:
soms|=som_new
cods.append(cod)
yield bi(cod,N)
return
#-------------------------------------------------
mat=[]; c=0; nn1=0; T0=T1=time()
gencod=gener_cod()
while True:
try: cod=next(gencod)
except StopIteration: print('\nFini : Nb max de tirages=%d'%nn); break
c+=1; T2=time();
print("%4d %s %7d %7d %8.3f %10.3f %9.6f %9.6f"%(c,cod,nn-nn1,nn,T2-T1,T2-T0,(T2-T1)/(nn-nn1),(T2-T0)/nn));
sys.stdout.flush()
nn1=nn; T1=T2
mat.append(cod)
if B and c>=B: print('\nFini : Résultat atteint=%d'%c); break
print("%d nombres de %d bits générés, avec tirage aléatoire de %d bits"%(len(mat),N,M))

[nodgim]

Un commentaire sur la performance de ce programme:

"Toujours avec ta méthode, j'en suis à 27 bits, dont 8 tirés au hasard et mis à 1. Suivant les tirages, j'arrive à 1000 entre 55 et 80 secondes. Une fois le programme s'est arrêté à 996, après avoir épuisé les combinaisons, mais il arrive fréquemment jusqu'à 1015."

[Doraki]

Intéressant si je comprends bien il se base sur 27 tests et il tire les bouteilles au sort, alors que je moi je faisais l'inverse (je me basais sur 1000 bouteilles et je tirais les tests au sort).

8 /27 est aussi pas très loin de 293/1000, ce qui correspondait à l'efficacité maximale des tests pour 1000 bouteilles.

Faudra que je teste.