Pauvres prisonniers

Vassillia

Bonjour, un problème assez connu de Peter Bro Miltersen  que j'aime bien et qui intéressera peut-être celles et ceux qui ne le connaissent pas encore.

Les noms de $2n$ prisonniers sont placés au hasard dans $2n$ boîtes en bois, un nom par boîte, et les boîtes sont alignés sur une table dans une pièce.
Un à un, les prisonniers sont conduits dans la pièce ; chacun peut regarder dans un maximum de $n$ boites, mais doit quitter la pièce exactement telle qu'il l'a trouvée et n'est plus autorisé à communiquer avec les autres.
Les prisonniers ont la possibilité de planifier leur stratégie à l'avance, et ils en auront besoin car si chaque prisonnier ne trouve pas son propre nom, tous seront ensuite exécutés.

Quelle stratégie conseillez-vous aux prisonniers et quelle sera alors leur probabilité de survie ?

Vassillia

J'oubliais mais n'hésitez pas à proposer une stratégie même non optimale, c'est ce qui fait l’intérêt du problème selon moi

lourrran

Imaginons que chaque prisonnier regarde $n$ boites au hasard.
Evidemment, si parmi ces $n$ boites, il voit son numéro, c'est ce numéro qu'il va donner.
Sinon, il faut que la stratégie décidée au préalable maximise les chances de réussite. Donc a priori, une bonne stratégie, c'est que le prisonnier de rang $k$ retourne la boite de rang $k$, sauf si il a retourné la boite portant son n°.

Et évidemment, pour améliorer un peu les chances, chaque prisonnier va retourner $n$ boites, mais pas la boite qui porte son propre n°.

A priori, j'imagine 2 stratégies pour améliorer un peu les chances : 
- le prisonnier n°$k$ retourne les boites $k+1$ à $k+n$  
- les prisonniers $1$ à $n$ retournent les boites $n+1$ à $2n$, et les autres retournent les boites $1$ à $n$.

Je bloque là. (l'expression n'est pas déposée, on a le droit de l'utiliser ?)

Bibix

En tout cas, la probabilité de survie est inférieure à $50\%$ donc c'est injuste !

JLapin

Indication :

on pourra commencer par calculer la probabilité qu'une permutation de $[1,2n]$ contienne dans sa décomposition en produits de cycles à supports disjoints un cycle de longueur strictement plus grande que $n$.

Vassillia

Belles tentatives lourrran, il y a de l'idée mais c'est dommage de ne pas se servir de l'information obtenue en ouvrant la boite.

Sinon l'indication de JLapin peut aider aussi, visiblement il connait la réponse même si tout cela risque de rester injuste

On peut quand même avoir une probabilité de survie supérieure à 1/3 jusqu'à $2n=18$ ce qui est quand même pas mal vu les circonstances.

Etienne91

Toutefois plus $n$ augmente plus la stratégie optimale devient efficace par rapport à la stratégie «  chaque prisonnier choisit $n$ boîtes au hasard » !

depasse

Bonsoir,
J'en ai déjà parlé sur ce forum:
$n$ parmi $\binom {2n}{n}$ en juillet 2019, après qu'un ami se soit fait arracher la main par les chiens de notre président.