Variation de 100 noms de prisonniers dans des cases

Question

100 noms de prisonniers dans des boîtes

Le puzzle suivant est une variante du puzzle ci-dessus.

Noms dans les boîtes

• Les noms de 4 prisonniers sont placés dans 4 boîtes en bois, un nom dans une boîte, et les boîtes sont alignées sur une table dans une pièce. Les cases sont numérotées 1, 2, 3 et 4.

• Les noms sont placés au hasard. Par conséquent, la case 1 est également susceptible de contenir le nom de l'un des 4 prisonniers. Il en va de même pour les autres cases.

• Un par un, les prisonniers sont conduits dans la salle; chacun peut regarder dans au plus 2 cases, mais doit quitter la pièce exactement comme il l'a trouvée et ne peut plus communiquer avec les autres.

• Chaque prisonnier, avant d'entrer dans la pièce, doit appeler les 2 boîtes qu'il ouvrira. Ils ne peuvent alors ouvrir que ces 2 boites.

• Les prisonniers ont une chance de planifier leur stratégie à l'avance, et ils en auront besoin, car à moins que chaque prisonnier ne trouve son propre nom, tous seront exécutés par la suite.

• Quelle stratégie peuvent-ils utiliser pour maximiser leur survie?

Answer 1

Je pense que la réponse est

Les deux premiers prisonniers choisissent les deux premières cases, et les deux derniers prisonniers choisissent les deux dernières cases. La chance de survie est$1/6 \approx 16.7\%$.

Raisonnement:

Imaginons un graphe de quatre nœuds et quatre arêtes, où chaque nœud représente une boîte et chaque arête relie les deux boîtes choisies par un prisonnier. Ensuite, il y aura quatre nœuds et quatre arêtes, et une arête ne peut pas être une auto-boucle.

Compte tenu d'un tel graphe, observez qu'un cycle de n'importe quelle taille dans le graphe permettra deux possibilités. Par exemple, si trois prisonniers A, B, C choisissent respectivement les cases 1-2, 2-3, 3-1, il y a deux cas où tous les trois trouveront leur propre nom: ABC et CAB.

De plus, si un tel cycle a des branches, elles n'augmentent pas les cas globaux de survie: en plus du dernier exemple, si D choisit 1-4, D renonce essentiellement à voir son nom dans la case 1 (puisque l'un des ABC ne trouvera jamais son nom autrement).

De plus, si un composant connecté a plus d'arêtes que de nœuds (par exemple, D choisit 1-2 à la place), les chances de survie tombent à zéro, car ils n'ont pas assez de cases distinctes pour trouver tous leurs noms.

Par conséquent, afin de maximiser les chances de survie, les prisonniers doivent maximiser le nombre de cycles disjoints dans le graphique, ce qui donne deux cycles de deux nœuds chacun. Ensuite, ils survivront dans quatre cas sur$4!=24$ total des cas, donnant $1/6$ chance de survie.