Bonjour,

voici quelques solutions:

1°) on a le temps: avec un seul rat. Chaque fois qu'il a soif on lui donne un peu d'eau d'une bouteille différente. Lorsqu'il crève par empoisonnement, on identifie immédiatement la bouteille d'eau qui a servi.

2°) on est pressé: on sert à une groupe tribal de rats 1000 coupelles avec chacune l'eau d'une des 1000 bouteilles.Lorsqu'un rat crève on s'appuie sur les idées suivantes les autres rats identifiant immédiatement la coupelle qui contient le poison, car:


"L'odorat et la manière dont le rat marque sont territoire peuvent lui sauver la vie. Par exemple, si un rat a mangé quelque chose d'inhabituel ou d'empoisonné et meurt, les membres du groupe reniflent dans la gueule du défunt pour reconnaître ce qu'il a mangé et ne mangeront jamais de cet aliment. D'autre part, si un rat a un doute quant à un aliment, il urine dessus pour empêcher les autres d'en manger."

Bien à vous

Je suis curieux quant à la motivation de ta réponse. La forme se veut investie et recherchée, mais le fond est aussi désinvolte qu'inintéressant mathématiquement. Du coup, je me demande, comme je n'ai pas accès au ton et au langage du corps, si ta réponse est moqueuse ou juste distraite pour ne pas dire idiote.

Peut-être est-ce une tentative de répondre de façon originale, ce qui expliquerait probablement ton pseudo, mais lorsque l'originalité n'est ni utile, ni agréable, elle devient très vite insupportable.

Dans tous les cas, tente de relire l'énoncé (on n'a droit qu'à une seule étape et donc on ne peut essayer les bouteilles une à une) et de donner une réponse adéquate (ceci est un site de maths et pas de biologie, la solution doit consister en une distribution choisie par toi et non par les rats), car je trouve ce problème très intéressant et riche, et j'aurai bien voulu pouvoir le partager.

Bonjour,

>>>mwek

merci pour les compliments exprimés avec tant de gentillesse!

Je signale qu'il n'est dit nulle part dans l'énoncé

Bonjour mwek

 Cliquez pour afficher

J'avoue ne pas avoir tout compris :
Est-ce qu'un même rat peut boire à plusieurs bouteille ?
Si oui, qui choisit ces bouteilles ?

Je suppose les réponses comme étant "oui"

Est-ce qu'on peut ... par exemple ... faire boire à un premier rat, un peu du contenu des 500 premières bouteilles ?
Puis à un autre rat (ou le même s'il n'est pas mort), 250 autre bouteilles etc. etc. ?

Si ce que je raconte est possible alors le nombre de rats n qu'il faut acheter est tel que 2ⁿ > 1000 soit 2ⁿ=1024 soit n = 10 rats

Bonjour papy13 et merci pour ta réponse.

 Cliquez pour afficher

Ton résultat est juste, mais la méthode de distribution de l'eau aux rats n'est pas claire. Pour tes questions, on suppose qu'une molécule du poison suffit pour tuer le rat et que du coup, on peut mélanger effectivement 500 gouttes dans un seul verre et le faire boire au rat.

Après avoir trouvé une des diverses méthodes de distribution possibles, essaye de résoudre le cas des 2 bouteilles, qui est beaucoup plus difficile...

@castoriginal

 Cliquez pour afficher

Mauvaise foi mise à part, l'énoncé est très clair:

Citation :
On fera boire à des rats de ces différentes bouteilles et on attendra le résultat. Il faudra alors identifier la bouteille empoisonnée.

LE résultat, un seul, donc une seule étape.

D'ailleurs, je me demanderai sinon où serait l'intérêt de l'énigme!!!

Allez castoriginal, essaye plutôt de résoudre l'énigme et je te pardonnerai tes péchés!

bonjour

 Cliquez pour afficher

Où est le problème? n- rats pour n bouteilles empoisonnées car certains rats sont résistants: j'ai beau mettre des produits chez moi, ils sont toujours là !!!!!

Tu rejoins le club de castoriginal?

Salut!
Je ne pense pas que l'énoncé soit  assez clair.

 Cliquez pour afficher

En effet, même la méthode de papy13 ne se fait pas vraiment en une étape, puisqu'il faut attendre de voir si le premier rat meurt avant de choisir les 250 bouteilles à tester ensuite... Et, si on peut attendre ainsi, force est de constater que le minimum est bien de 1 comme l'a dit castoriginal. D'un autre côté, si on ne peut vraiment rien attendre, il me semble que le minimum (pour être certain de trouver) est de 1000. Forcément, le problème devient bien moins intéressant avec cette approche, mais comment déterminer la bonne approche?

Bonjour,

je pense que le problème n'a d'intéret que si le poison est diluable à volonté sans perte d'éfficacité : une goutte d'éau empoisonné suffirait à tuer une armée de rats, même en la diluant dans des hectolitres d'eau.
ce qui comme l'a signalé ming est irréaliste : les vrais rats sont bien trop résistants !

 Cliquez pour afficher

Bon faut pas exagérer tout de même, ici la dilution ne sera que de 500 fois.

Je vais donner le protocole sur un exemple avec 8 bouteilles notées ABCDEFGH, pour lesquelles il suffit de 3 rats.
je numérote mes bouteuilles en binaire :
A = 000
B = 001
C = 010
D = 011
E = 100
F = 101
G = 110
H = 111

puis je "lis les rats verticalement" (de droite à gauche)
1er rat : je lui donne à boire un mélange des bouteilles BDFH
au même moment et sans attendre quelque résultat que ce soit, je donne au 2ème rat un mélange des bouteilles CDGH
toujours au même moment, je donne au 3ème rat un mélange des bouteiles EFGH

j'attends un peu et j'observe quel(s) rat(s) meur(en)t
Je note le résultat en binaire :
si par exemple les rats 1 et 2 meurent : 011 bouteille D
aucun ne meurt : 000 bouteille B
tous meurent : 111 bouteille H

ici il suffit donc de 10 rats comme l'a parfaitement signalé Papy13, mais son raisonement pêchait méthodologiquement. (il lui faudrait le double de rats avec sa méthode, peut être bien même plus) chacun des rats boit un mélange de l'eau de 512 bouteilles prises parmi les 1000

Pour être sûr de la validité du résultat même si aucune bouteille n'était empoisonnée, comme 1000 < 1024, certains codes binaire ne seront pas utilisés, il suffit donc de ne pas utiliser entre autre le code 000...00 pour garantir que si aucun de mes dix rats ne meurt, c'est que toutes les bouteilles sont saines.
(et que s'ils meurent selon un des codes inutilisé c'est que je me suis trompé dans mes mélanges, ou que plusieurs bouteilles sont empoisonnées)

Le protocole avec deux bouteilles empoisonnées est semblable, mais ce n'est pas le code binaire naturel qu'il faut utiliser.
Il y a C(1000, 2) = 49500 cas possibles, et la plus petite puissance de 2 49500 est 65536 = 2¹⁶
un protocole idéal ne peut donc pas utiliser moins de 16 rats.
reste à en trouver un avec 16 rats seulement, s'il existe !!
(raisonnement sur la "quantité d'information" fournie par l'état de 16 rats à la fin du test)
à suivre...

Bonjour.

 Cliquez pour afficher

Dix rats suffisent.
On numérote les bouteilles dans la base binaire, en complétant les numéros par des 0 à gauche de manière qu'ils aient tous dix chiffres.
On fait boire au premier rat du contenu des bouteilles ayant 1 comme premier chiffre; au deuxième rat du contenu des bouteilles ayant 1 comme deuxième chiffre, etc.
À la fin, on recense les rats dans l'ordre, en écrivant 1 pour un rat mort et 0 pour un rat vivant. On obtient un nombre en base binaire de dix chiffres qui est le numéro de la bouteille d'eau empoisonnée.

Bonjour à tous,

>>> plumemeteore

Chacun des 10 rats doit goûter à l'eau de 100 bouteilles.Or il est dit que

Bonjour catoriginal,

Tu n'as pas compris ce qu'a écrit plumemeteore (c'est à dire la même chose que moi), c'est pas 100 c'est 500 et quelques et c'est pas l'une après l'autres, c'est le mélange en une seule fois.

Bonsoir mathafou et plumemeteore
Bravo pour la résolution pour une bouteille empoisonnée.

mathafou, la suite est beaucoup plus compliquée, comme tu as dû remarquer.
En passant, 2 parmi 1000 donne à peu près un demi million, tu as oublié un zéro. La raisonnement sur la quantité d'information est élégant et donne bien un minorant égal à 19 pour 2 bouteilles. Mais 19 est-il possible? Ça m'a travaillé pendant des semaines. Bonne chance!

Pour l'algorithme de distribution, ça sera compliqué, et pour la théorie qui trouverait le nombre n optimal de rats en fonction de b, nombre des bouteilles et p, nombre des bouteilles empoisonnées, c'est encore plus complexe. Courage!

Exemple:
Pour 6 rats, sauf erreur, et même si 2^4=16>2parmi6=15, 4 rats ne suffisent pas!

La principale difficulté étant le fait qu'une bouteille suffise à tuer un rat sans qu'il ne boive de l'autre! Si le rat ne meurt qu'en buvant le mélange des deux bouteilles, il suffirait de généraliser la méthode binaire et on aurait la réponse avec 19 rats pour 2 bouteilles de poison qu'il fait mélanger pour mourir, parmi 1000 bouteilles.

Comme ce n'est pas le cas, il faut trouver un sous ensemble de l'ensemble des parties de E={1...n} tel que l'union de deux éléments d'un couple de ce sous ensemble ne soit jamais la même pour deux couples distincts, pour ne pas hésiter entre deux bouteilles ou plus. Cet ensemble doit par ailleurs être de cardinal maximal, pour rentabiliser les n rats au maximum.

C'est très très dur!

Bonsoir à tous

J'ai découvert ce problème il y a quelques jours et j'avoue qu'il m'a intrigué au point que j'ai ouvert un fil sur un site où j'ai mes habitudes .

Des ébauches de solutions ont été proposées mais le problème n'est vraiment pas facile .

@mwek : Tu as une solution ? Si oui , tu es sûr quelle minimise le nombre de rats ?

Imod

Bonjour,

Comme on ne parle pas de la concentration du poison,
on dira qu'une seule lampée tue le rat testeur.
Je n'ai besoin que de 3 rats

 Cliquez pour afficher

On prend une bouteille au hasard et on fait boire une  gorgée
au 1 er rat ;si il reste en vie on vide la bouteille .
on prend 8 bouteilles et on en vide 1/8 dans la première;
si le rat reste en vie on continue.
Nous savons qu'une série de 8 tombera sur le poison donc
notre rat épargné jusque là va s'empoisonner.

on isole cette série en 4 et 4  et on teste un 2ème rat
s'il ne meurt pas on  divise en 2 et 2 et on sait
qu'il va mourrir ,notre 3 éme rat désignera celle des 2

Bonjour,

Citation :
On fera boire à des rats de ces différentes bouteilles et on attendra résultat

@dpi

Tu n'as pas vraiment lu le sujet et tu rajoutes un blanqué ( tu peux préciser pourquoi ? )

Imod

@Imod

J'ai tout simplement essayé de répondre à la question
pratique suivante:j'ai 1000 bouteilles dont une empoisonnée,
je n'ai que peu de moyens pour acheter des rats,comment
faire au mieux.

Le fait de n'avoir droit qu'à une expérience ( une seule observation ) complique énormément le problème .

Ma question portait plutôt sur le blanké . Le problème est ouvert à tous et carrément difficile . Dans ce contexte où chacun essaie de proposer des idées , quel est l'intérêt d'avancé masqué ?

Merci pour ta contribution

Imod

Bonsoir à tous,

lmod, oui, j'ai une solution, mais elle ne minimise pas du tout le nombre de rats. Je dois être à une cinquantaine de rats pour 1000 bouteilles dont 2 sont empoisonnées.

dpi, comme on te l'a dit, il faut une expérience, un résultat.

Mais je reconnais que dans plusieurs cercles où j'ai proposé cette énigme, on m'a parlé de p étapes quand on a p bouteilles empoisonnées, et on a trouvé du 4logp(b) pour le nombre de rats à utiliser dans ce cas, b étant le nombre de bouteilles et logp le log en base p. Ce n'est pas optimal non plus, on le sait, ça donne 41 rats pour 1000 bouteilles dont 2 sont empoisonnées quand on a deux étapes.

Peut-être est-ce par rigidité, mais je trouve plus intéressant d'explorer le cas où on n'a droit qu'à une seule étape. Mais si vous avez des propositions différentes, elles sont les bienvenues.

Je refuse de mourir avant d'avoir trouvé le nombre optimal n de rats en fonction de b et de p.



Bonne soirée!

Bonsoir,

>>> mwek

Bonjour à tous,
Voici une méthode différente de celle de Plumemeteore pour pouvoir repérer une bouteille empoisonnée parmi b bouteilles, et ce à l'aide de n rats. Comme dit plus haut, avec n rats on pourra tester un maximum de 2expn bouteilles pour trouver la bouteille empoisonnée.

Je m'explique en partant d'un exemple : imaginons que nous ayons trois rats et que nous voulions retrouver une bouteille empoisonnée parmi un maximum de bouteilles (maximum que nous aurions encore à définir). Voici ma méthode, où nous avons préalablement repéré les trois rats par les lettres A,B et C :
Si la méthode existe, c'est qu'après avoir fait « boire aux rats de ces différentes bouteilles et  attendu le résultat », nous pourrons noter les lettres renseignées par les rats morts, -et que ces lettres nous indiqueront le numéro de la bouteille empoisonnée. Dès lors, vu sous cet angle, la méthode qui appréhende le max de bouteilles pourrait être celle qui aura profité au max des lettres A,B et C. Or, il n'y a pour cela pas mieux que de construire l'ensemble des sous-ensembles de {A,B,C}, c-à-d { A ; B ; C ; AB ; AC ; BC ; ABC } . Ainsi, en effet, en ayant fait boire le flacon 1 à A, 2 à B, 3 à C, 4 à A et B, …, 7 à AB et C,  nous pourrons toujours savoir, sans erreur possible, quel flacon est contaminé. Par exemple, si les rats morts sont A et B, c'est que le flacon recherché porte le numéro 4. Puisque toutes les « sous-combinaisons » tirées de ABC sont là et qu'elles sont au nombre de 7, il sera impossible de tester une 8e bouteille, puisque celle-ci ne pourra plus être identifiée par une nouvelle sous-combinaison tirée de ABC. Ainsi, par ce qui précède, avec n rats il semble impossible de tester plus de 2expn -1 flacons (2expn -1 étant le cardinal de l'ensemble des sous-ensembles …). Sauf que l'on pourra toujours placer au départ une bouteille supplémentaire (donc finalement une 8e bouteille dans notre exemple), qui ne sera bue par aucun rat et qui sera donc la bouteille à incriminer si aucun rat ne meurt.
Conclusion : n rats permettent de tester au maximum 2expn bouteilles, s'il n'y a qu'une seule bouteille empoisonnée. Cette méthode faisant intervenir « l'ensemble des sous-ensembles » est toujours applicable et permettra toujours de trouver la bouteille empoisonnée.

A présent, pour ce qui est de répondre à la question Bonus : « Et s'il y avait 2 bouteilles empoisonnées ? Et s'il y en avait n … »  je dois dire que la solution m'étonne encore. Il semble bien que, par exemple, on ne puisse pas faire mieux que d'utiliser 999 rats pour trouver deux bouteilles empoisonnées, ou plus, parmi 1000 bouteilles.  
En fait, on doit utiliser n-1 rats pour trouver plus d'une bouteille empoisonnée parmi n bouteilles, c'est la solution la plus triviale (et la plus inattendue).
Bien sûr, je ne parle pas ici d'expérience « à plusieurs étapes » comme on en parle plus haut, dont je ne vois pas bien de quoi il s'agit. L'énoncé de départ ne parle pas de plusieurs étapes donc je m'en suis tenu à cet énoncé. C'est déjà assez compliqué comme ça
Amicalement
Ruco

Bonsoir

Un long message pour expliquer pourquoi le nombre de signaux émis par les rats morts ou vifs doit être au moins égal au nombre de configurations possibles pour les flacons empoisonnés

Affirmer ensuite qu'il faut autant de rats que de flacons , là tu peux détailler

Imod  

Salut Imod
Le début de mon message est : « voici une méthode différente de celle de Plumemeteore pour pouvoir repérer une bouteille empoisonnée parmi b bouteilles, et ce à l'aide de n rats ». J'ai fait trop long, d'accord, mais c'est tout de même bien une méthode différente de celle de Météore que je propose. Et je ne me contente pas de faire « savoir que le nombre de signaux émis par les rats morts ou vifs doit être au moins égal au nombre de configurations possibles », puisque je prouve que ce nombre est EGAL au nombre de configurations possibles.
L'énoncé du premier message est : « Quelle stratégie adopter pour acheter un minimum de rats ? »
Ta stratégie, à toi, c'est juste de dire que « le nombre de signaux émis par les rats morts ou vifs doit être au moins égal au nombre de configurations possibles » ?

Quant à expliquer les n-1 rats nécessaires pour b=n bouteilles, c'est certainement obligatoirement vrai dans certains cas, mais je me demande si je n'ai pas généralisé trop vite.

Ruco

J'ai bien sûr écrit tout ça amicalement  

On peut en effet faire bien mieux pour un nombre de bouteilles assez grand . Je n'ai pas donné de stratégie car je n'en ai pas

Imod

PS : J'aboie mais je ne mord pas