Les mauvais flacons
Bonjour à tous
Encore un problème qui sort un peu de tout les cadres , théorie des ensembles , des graphes ... ?
J'ai trouvé ça sur un autre site ( je fournirai les références si on me le demande ) .
Voilà le problème :
On dispose de $n$ flacons dont certains ( entre $0$ et $m$ avec $m$ donné ) sont infectés . L'infection est particulièrement virulente , tout rat mis en contact avec une infime partie du contenu d'un tube contaminé va mourir dans les 24 heures . On réalise une expérience unique mettant certains rats en contact avec certains flacons , 24 heures plus tard l'observation des rats morts doit permettre de désigner les flacons contaminés .
Le problème est très simple si on dispose de rats à volonté mais si on veut limiter au maximum le nombre de rats utilisés , quel est ce minimum ?
Je ne sais pas s'il existe une solution générale simple , toute solution partielle sera bienvenue
Merci d'avance pour la participation
Domi
Encore un problème qui sort un peu de tout les cadres , théorie des ensembles , des graphes ... ?
J'ai trouvé ça sur un autre site ( je fournirai les références si on me le demande ) .
Voilà le problème :
On dispose de $n$ flacons dont certains ( entre $0$ et $m$ avec $m$ donné ) sont infectés . L'infection est particulièrement virulente , tout rat mis en contact avec une infime partie du contenu d'un tube contaminé va mourir dans les 24 heures . On réalise une expérience unique mettant certains rats en contact avec certains flacons , 24 heures plus tard l'observation des rats morts doit permettre de désigner les flacons contaminés .
Le problème est très simple si on dispose de rats à volonté mais si on veut limiter au maximum le nombre de rats utilisés , quel est ce minimum ?
Je ne sais pas s'il existe une solution générale simple , toute solution partielle sera bienvenue
Merci d'avance pour la participation
Domi
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Domi
Avec $k$ rats il y a $2^k$ issues possibles or pour $n$ et $m$ donnés comme ci-dessus il y a $C_n^0+C_n^1+\cdots + C_n^m$ possibilités de distributions pour les flacons infectés . On a donc une borne inférieure du nombre de rats nécessaires . On peut aussi élaborer une stratégie élémentaire si un flacon au plus est infecté .
Pour la suite ???
Domi
Le minimum est m. On fait tester chacun des flacons par un rat. S'il survit il testera un autre flacon, etc.
Comme pour k flacons infectés, il faudra tuer au moins k rats pour savoir, le minimum est la valeur maximale de k.
Cordialement.
Dans l'énoncé, on parle d'expérience unique, pas d'expériences successives.
Bon, peut-être que j'ai mal interprété...
Aldo
On a droit à une seule expérience , sinon c'est trop facile . On inocule les doses aux rats choisis , on laisse agir 24 heures et on revient voir pour désigner à coup sûr les flacons infectés .
Domi
Ton explication me laisse à penser que j'ai quand même dû rater quelque chose dans l'énoncé.
Tout d'abord, c'est bien le nombre de rats utilisés qu'il faut minimiser, pas forcément le nombre de rats morts ?
On peut toujours mettre n rats chacun en contact avec un flacon, attendre 24h et savoir pour chaque flacon s'il est infecté. Le problème demande donc si c'est possible avec moins de n rats ?
Merci pour tes éclaircissements.
Aldo
Quelle que soit la procédure, elle doit donner un rat mort (au moins) pour chaque flacon infecté soit k rats morts, et un rat vivant (au moins) pour chaque flacon non infecté. La connaissance du nombre maximum de flacons infectés n'apporte rien si on doit tester tous les flacons (elle apporterait si on les testait successivement). Elle apporte une éventuelle certitude le lendemain matin : Au bout de m rats morts (car on va les regarder les uns après les autres), on saura que les rats non encore vérifiés sont vivants (sauf mauvaise surprise). Mais si k<m, il faut les vérifier tous. Là encore, la connaissance d'un maximum ne sert pas !
Cordialement.
Domi
Domi
Même avec l'habituelle dichotomie, il en faut plus. mais tu as peut-être le moyen de faire revivre les rats morts ?
Cordialement.
Domi
Ah oui, s'il n'y a qu'un flacon toxique, le principe du code de Hamming convient :
Chaque flacon est numéroté en binaire et on inocule le rat numéro i, avec les flacons dont l'expression binaire contient 1 en coefficient de 2i.
Ainsi l'alignement des rats indique, en binaire (1 pour les rats morts et 0 pour les vivants), le numéro du flacon toxique.
Comme 1000 < 210, 10 rats suffisent.
Alain
Domi
Pour 1 flacon maximum, on peut trouver. J'avais tort.
Cordialement.
Domi
$F=\{1,2,\cdots,n\}$ ensemble des flacons .
$R=\{1,2,\cdots,p\}$ ensemble des rats .
$C=\{X\subset F: |X|\leq m\}$ catalogue des flacons possiblement infectés .
$B=(\mathbb{Z}/2\mathbb{Z})^p$ résultat d'une expérience . Chaque indice correspond à un rat avec 1 = vivant et 0 = mort .
$P\subset R\times F$ un protocole d'ingurgitation $(r,f) \in P$ ssi $r$ boit $f$ .
Le protocole $P$ induit l'application $\overline{P} : C \rightarrow B$ par $\overline{P}(X)_i=0$ ssi $\exists f \in X : (i,f) \in P .$
$\overline{P}(X)$ donne le bilan en rats morts du protocole $P$ pour les flacons infectés $X$ .
Le problème revient à trouver les $P$ tels que $\overline{P}$ soit injective .
Une condition nécessaire est que $|C|\geq |B|$ mais elle est sûrement loin d'être suffisante .
Je ne suis pas complètement convaincu que ce formalisme apporte vraiment quelque chose
Merci à ceux qui s'intéressent au problème .
Domi
Voici d'abord quelques procédures Maple qui permettent d'expérimenter un peu.
1) La procédure suivante prend comme arguments n, m, les ensembles des flacons bus par les différents rats et la liste des états des rats après 24 heures (0 s'il est mort, 1 s'il est vivant). Elle renvoie l'ensemble des possibilités pour les flacons empoisonnés.
Exemples :
Exemples :
Je n'ai pas tout lu mais il me semble que tu étudies n flacons dont m empoisonnés alors qu'il s'agit de m empoisonnés au maximum.
Aldo
Un peu de calcul maintenant, toujours pour exactement $m$ flacons empoisonnés parmi $n$.
Supposons l'expérience réalisée. Je note $F=\{1,\ldots,n\}$ l'ensemble des flacons, $V$ l'ensemble des flacons bus par les rats survivants, et $M_1,\ldots,M_q$ les ensembles des flacons bus par chacun des rats morts. Par exemple $M_1=\{1,2\}$ signifie que le premier rat mort a bu les flacons $1$ et $2$. Alors :
- Si un rat survit, on sait que tous les flacons associés sont sains. Les flacons empoisonnés sont donc à chercher dans $F\setminus V$.
- Si le i-ème rat meurt, alors l'un au moins des flacons de $M_i$ (et même de $M'_i:=M_i\setminus V$) est empoisonné.
On voit ainsi que les solutions possibles sont les parties de $F\setminus V$ à $m$ éléments dont un au moins appartient à $M'_1$, un au moins appartient à $M'_2$, $\ldots$, un au moins appartient à $M'_q$.
En appliquant la formule du crible, je trouve que le nombre de telles parties est :
$$s=\binom{n'}{m}-\sum_{i}\binom{n'-|M'_i|}{m}+\sum_{i<j}\binom{n'-|M'_i\cup M'_j|}{m}-\sum_{i<j<k}\binom{n'-|M'_i\cup M'_j\cup M'_k|}{m}+\ldots$$
où $n'=|F\setminus V|=n-|V|$.
Le dénombrement ce n'est pas ma tasse de thé, donc je ne sais pas si on peut trouver une formule plus simple.
Quoi qu'il en soit, pour que l'expérience soit concluante, il faut qu'il n'y ait qu'une seule solution, i.e. que $s=1$.
Avec Maple on peut écrire un programme (que je ne donne pas parce qu'il est moche) qui renvoie ce nombre de solutions sans avoir à les calculer. Voilà ce que ça donne avec les exemples de mon message précédent :
Même en considérant le cas exactement égal à m, il est remarquable qu'il n'y ait pas symétrie entre flacons empoisonnés et sains : la méthode pour 1 flacon empoisonné ne fonctionne pas pour 1 flacon sain.
Je vois bien la méthode employée. Je n'arrive pas à mettre le doigt sur un défaut mais je suis surpris que pour 1001 flacons donnés , 1 contaminé nécessite 10 rats , 2 contaminés nécessitent 1000 rats .
Les maths débordent de ces mystères , il manque quand même une explication !
Domi
- 1 flacon empoisonné parmi 1000 : 1000 possibilités. Avec 10 rats on est tranquille car 2 10 > 1000.
- 2 flacons empoisonnés parmi 1000 : 499.500 possibilités. Avec 19 rats codeurs, on devrait y arriver à condition de trouver la bonne expérience, si elle existe !
On peut tout de même se faire une idée avec 2 flacons empoisonnés parmi 6, ce qui ne fait que 15 possibilités. Or 24 = 16 est supérieur à 15.
Pourtant, Juge Ti, avec son programme, nous dit qu'il faudra 5 rats.
Donc, il ne suffit peut être pas que la capacité de codage soit supérieure au nombre de possibilités. Etonnant tout ça ...
Aldo
On numérote les flacons de 0 à $n-1$. Pour tout flacon $x$, soit $c_j(x)$ le $j$-ième chiffre de $x$ en base 2 ($j=0,1,\ldots,k-1$). Soit $A_j$ l'ensemble des flacons $x$ tels que $c_j(x)=0$ et soit $A'_j$ son complémentaire.
On fait tester aux rats les ensembles de flacons suivants :
$A_j$ ($0\le j\le k-1$). Notons $r_j$ les rats correspondants.
$A'_j$ ($0\le j\le k-1$). Notons $r'_j$ les rats correspondants.
$A_j\cap A_\ell$ ($0\le j<\ell\le k-1$). Notons $r_{j\ell}$ les rats correspondants.
Il n'y aucun flacon empoisonné si et seulement si $r_0$ et $r'_0$ survivent.
Il y a exactement un flacon empoisonné si et seulement si pour tout $j$, exactement un rat parmi $r_j$ et $r'_j$ survit.
Supposons dorénavant qu'il y a exactement 2 flacons empoisonnés $x$ et $y$. Pour tout $j$, si $r_j$ meurt et $r'_j$ survit, alors $c_j(x)=c_j(y)=0$. De même, si $r'_j$ meurt et $r_j$ survit, alors $c_j(x)=c_j(y)=1$. Si $r_j$ et $r'_j$ meurent alors $c_j(x)\ne c_j(y)$.
On a pour l'instant une indétermination s'il existe au moins deux indices $j$ tels que $r_j$ et $r'_j$ meurent. Soit $j_0$ l'un de ces indices. Appelons $x$ le flacon tel que $c_{j_0}(x)=0$ et $y$ l'autre flacon. Pour tout $j$ tel que $r_j$ et $r'_j$ meurent, si $r_{j_0j}$ meurt alors $c_j(x)=0$ et donc $c_j(y)=1$, et si $r_{j_0j}$ survit on a $c_j(x)=1$ et $c_j(y)=0$.
Pour $k=3$ on a $2k+k(k-1)/2=9$ donc ma solution n'est clairement pas optimale.
Pour $k=4$ on a $2k+k(k-1)/2=14$ donc ma solution est meilleure que la solution naïve.
$A_i \cap A_j$ ($i<j$)
$A_i \cap A'_j$ ($i\ne j$)
$A'_i \cap A'_j$ ($i<j$)
$A_i \cap A_j\cap A_\ell $ ($i\ne j$, $i\ne \ell$, $j<\ell$)
$A'_i \cap A_j\cap A_\ell $ ($i\ne j$, $i\ne \ell$, $j<\ell$)
mais je n'ai pas vérifié en détail.
Le cas cas m=2 du problème de Domi semble donc résolu, à moins de chercher encore mieux !
Aldo
Merci à lui ! Il reste encore à faire , il est vraiment tordu ce problème !
Domi