Problèmes de JP Delahaye

Et alors ? On peut bien avoir des tiroirs vides, ça n'infirme pas l'argument qu'il y a plus de sous-ensembles que de tiroirs.
Par ailleurs, on part bien d'un ensemble de 10 nombres : pas de répétition.

Bonjour,
Le deuxième problème de prisonniers, énoncé plus haut par mojojo, a déjà été évoqué sur notre forum.
On avait donné la solution ci-dessous en blanc:
Les prisonniers s'attribuent au préalable 100 numéros, tous distincts.
Chacun inscrira sur son papier son numéro moins la somme de tout ce qu'il voit modulo 100.
Un (et un seul) prisonnier fournira la bonne réponse : celui dont le numéro égale (modulo 100) la somme des valeurs des chapeaux distribués.

Si le nombre impair est égal à $1$, il n'y a aucune stratégie gagnante.

Même avec l'élément vraiment essentiel que tu avais oublié, je pense qu'avec 3 ça coince. Par ailleurs, c'est quoi, les "cas" ?
Stratégie de réponse : si l'on voit une majorité de chapeaux rouges (resp. noirs), supposer qu'on a un chapeau rouge (resp. noir) : si l'on voit autant de noirs que de rouges, faire à plouf-plouf.

Tryss, tu n'as pas respecté la consigne "poster les réponses en blanc" (ce que j'ai fait).

Bonsoir,

une n-ième histoire de prisonniers suivi (puisque la tendance est au complotisme), d'une histoire de complot.

$\large •$ Problème 1: "Les prisonniers et les tiroirs"

Des prisonniers sont numérotés de 1 à 100 et connaissent leur numéro. Ils sont appelés un à un et une seule fois dans le bureau du directeur où se trouve une commode de 100 tiroirs numérotés de 1 à 100.
Le directeur a disposé de façon aléatoire dans chaque tiroir un papier portant le numéro d'un prisonnier. Chaque tiroir contient un numéro et chaque prisonnier a son numéro dans un tiroir.

Chaque prisonnier ne peut ouvrir que 50 tiroirs AU PLUS et doit trouver son numéro.
Les prisonniers ne peuvent pas communiquer entre eux pendant l'épreuve, ne savent pas qui a été appelé avant eux et ne peuvent pas déplacer les papiers dans les tiroirs.
Les prisonniers gagnent s'ils trouvent tous leur numéro. Ils peuvent se mettre d'accord avant le début de l'épreuve sur une stratégie.

Trouver une stratégie donnant aux prisonniers une probabilité de gagner supérieure à 30%.

n.b: chaque prisonnier pouvant ouvrir au plus 50 tiroirs a une chance sur deux de trouver son numéro. Une victoire totale a une probabilité de $\frac{1}{2^{100}}$.

$\large •$ Problème 2: "Les rats et les bouteilles"

Un roi possède 1000 bouteilles de vin. Ayant découvert une conspiration, il sait qu'exactement une bouteille est empoisonnée.
Son valet, chargé de déterminer laquelle est-ce, dispose de rats auxquels il peut faire goûter les différentes bouteilles.
Si un rat boit du vin empoisonné, il meurt le lendemain. Le roi veut savoir dès le lendemain et avec certitude quelle est la bouteille empoisonnée.

De combien de rats, au minimum, son valet a-t-il besoin ?

Il existe une variante un peu plus difficile de l'énigme précédente.

$\large •$ Problème 3: "Les rats et les bouteilles" (suite)

Un roi possède $p$ bouteilles de vin. Ayant découvert une conspiration, il sait qu'exactement une bouteille est empoisonnée.
Son valet, chargé de déterminer laquelle est-ce, dispose de rats auxquels il peut faire goûter les différentes bouteilles.
Si un rat boit du vin empoisonné, il meurt le lendemain.
Cette fois, le roi n'est pas pressé. Il donne $q$ jours à son valet pour déterminer avec certitude quelle est la bouteille empoisonnée.

De combien de rats, au minimum, son valet a-t-il besoin ?

n.b: comme dans l'énigme précédente, le valet va faire goûter à chaque rat un mélange de bouteilles. La différence, c'est qu'il pourra réutiliser le lendemain les rats ayant survécu pour leur faire à nouveau goûter d'autres mélanges et ainsi de suite pendant $k$ jours.
Il est important de prouver que le nombre de rats proposé doit être minimum.




source: "Enigmes mathématiques• Guillaume et Clément Deslandes• ellipses.
...

@Tryss

T'as trouvé. Bravo ! La clé du deuxième problème est effectivement de numéroter les bouteilles en base 2.
Mais tu ne devrais pas rédiger ta réponse à l'encre sympathique.
(Ton post apparait quand on enregistre la page en pdf ! )

p.s:Il faut préciser, car l'énoncé n'en dit rien, que le but n'est pas de saouler les rats afin de ne pas risquer de confondre mort par empoisonnement et mort par coma éthylique !
...

Quelques remarques complémentaires et brefs résumés des solutions dont je dispose, tout ou presque ayant déjà été résolu…

$\large •$ Problème 1

On définit $\sigma$, la permutation qui à un numéro de tiroir associe le numéro qu'il contient.
Chaque prisonnier teste d'abord le tiroir correspondant à son numéro puis le tiroir indiqué par le numéro qu'il y trouve et ainsi de suite jusqu'à ce qu'il trouve son numéro: le prisonnier numéro $i$ teste les tiroirs $i$, $\sigma(i)$, $\sigma(\sigma(i))$, etc…

On peut décomposer $\sigma$ en produits de cycles à supports disjoints. Puisque les prisonnier n'ont pas le droit d'ouvrir plus de 50 tiroirs pour trouver leur numéro, la stratégie fonctionne si $\sigma$ ne contient aucun cycle de longueur supérieure à 50.

On cherchera donc la probabilité qu'une permutation de $\{1,2,...,100\}$ ne contienne aucun cycle de longueur supérieure à 50.
Or, pour un $k$ quelconque, le nombre de permutations de $\{1,...,100\}$ contenant un cycle de longueur $k$ est:
\begin{equation}
\binom{100}{k}(k-1)!(100 - k)!=\frac{100!}{k}
\end{equation}

En effet, on commence par choisir un support du cycle: $\binom{100}{k}$ possibilités puis, pour chaque support, les $(k-1)!$ cycles de longueur $k$ possibles puis le reste de la permutation: $(100 - k)!$ choix.

Une permutation de $\{1,...,100\}$ ne pouvant contenir qu'un seul cycle de longueur strictement supérieur à 50, le nombre de ces permutations est:

\begin{equation}
N= \sum_{k=51}^{100} \frac{100!}{k}
\end{equation}

La probabilité que la stratégie échoue est:

\begin{equation}
1-p= \frac{N}{100!}=\sum_{k=51}^{100} \frac{1}{k}
\end{equation}

Et finalement $p$ est environ $0,312$.



$\large •$ Problème 2

Si l'on fait goûter les 500 premières bouteilles à l'infortuné rongeur, sa mort ou sa survie le lendemain impliquera la présence de la bouteille empoisonnée dans la première ou la deuxième moitié du lot.
Mais pour discriminer efficacement des lots toujours plus réduits on numérote les bouteilles de $0000000000_2=0$ à $1111100111_2=999$.

Le premier rat goûte toutes les bouteilles dont le premier chiffre (en partant de la droite) est un $1$ comme $0000000001_2, 0000000011_2, 0000000101_2$, etc…
Le second rat goûte toutes les bouteilles dont le deuxième chiffre du numéro est un $1$.
.
.
.
Le dixième rat goûte toutes les bouteilles dont le dixième chiffre du numéro est un $1$.

Ainsi, la mort du $i$-ème rat indique la présence d'un $1$ en $i$-ième position dans le numéro de la bouteille empoisonnée.

$\large •$ Problème 3

On commence par traiter le cas $q=2$ jours.
Dans ce cas et avec $n$ rats, on ne peut discriminer plus de $3^n$ bouteilles.
La technique utilisée consiste à comparer le nombre de solutions et le nombre de résultats possibles de l'expérience.

Supposons que l'on veuille faire goûter $k$ bouteilles à $n$ rats.
Le lendemain, on constate entre $0$ et $n$ décés.

Si $i$ rats sont morts le premier jour $(0 \leq i \leq n)$, la deuxième journée aura $2^{n-i}$ issues possibles pour les rongeurs. Le nombre de cas où $i$ d'entre eux meurent le premier jour est $\binom{n}{i}$.
Le nombre de résultats possibles est:

\begin{equation}
\sum_{i=1}^{n} \binom{n}{i} \times 2^{n-i}=3^n
\end{equation}

Ici, les solutions possibles au problème sont les $k$ bouteilles. Soit c'est la première qui est empoisonnée, soit c'est la deuxième,…, soit c'est la $k$-ième. La méthode de comparaison "résultats/solutions" donne:
\begin{equation}
k \leq 3^n.
\end{equation}

Enfin il existe une méthode pour discriminer $3^n$ bouteilles avec $n$ rats et en $q=2$ jours.
On commence par diviser les bouteilles en $n+1$ groupes numérotés de $k=0$ à $n$.

Le premier groupe (portant le numéro $0$) contient $2^n$ bouteilles.
Le second groupe contient $n \times 2^{n-1}$ bouteilles réparties en $n$ sous-groupes de $2^{n-1}$ bouteilles.
.
.
.
Le groupe numéro $k$ contient $\binom{n}{k} \times 2^{n-k}$ bouteilles réparties en $\binom{n}{k}$ sous-groupes de $2^{n-k}$ bouteilles.

A chacun des $\binom{n}{k}$ sous-groupes de $k$ rats est attribué un des $\binom{n}{k}$ sous-groupes de $2^{n-k}$ bouteilles.

L'expérience se déroule de la manière suivante: aucun rat ne goûte les bouteilles du premier groupe. Pour le second groupe, chacun des $n$ rats goûte toutes les bouteilles d'un seul sous-groupe de $2^{n-1}$ bouteilles etc… Tous les $k$ rats d'un sous-groupe goûtent toutes les $2^{n-k}$ bouteilles du sous-groupe correspondant (parmi $\binom{n}{k}$) et uniquement celles-là.

Le lendemain, la mort de $k$ malheureux rongeurs situe la bouteille recherchée dans le sous-groupe correspondant du groupe n°$k$. On poursuit les investigations dans ce sous-groupe en appliquant, pour une journée supplémentaire, la méthode précédente.

Pour conclure, on peut montrer par récurrence, qu'avec $n$ rats et en $q$ jours, on ne peut discriminer plus de $(q+1)^n$ bouteilles.
...