This is yet another of those crazy warden and mathematical prisoner puzzles.
This time, there are $2n$ prisoners (each with a distinct name).
The warden has a room with $2n$ boxes, each box has the name of exactly one prisoner, and each prisoner's name appears in some box (picked randomly by the warden).
The game the warden plays is that each prisoner goes independently (one by one) in a room and points at some $n$ of the boxes. The goal being that each prisoner should choose the box which contains their own name. If any one of the prisoners does not then they all lose the game. The prisoners aren't allowed to communicate in any way (with each other) what boxes they picked.
If each prisoner picked $n$ boxes at random, then the probability that they win the game (each picks their own name) is $\dfrac{1}{2^n}$ which is pretty small.
They are allowed to choose a strategy before any of them enter the room.
Show that there is a constant $c \gt 0$ (independent of $n$) and a strategy such that the prisoners win the game with probability at least $c$.
This time, there are $2n$ prisoners (each with a distinct name).
The warden has a room with $2n$ boxes, each box has the name of exactly one prisoner, and each prisoner's name appears in some box (picked randomly by the warden).
The game the warden plays is that each prisoner goes independently (one by one) in a room and points at some $n$ of the boxes. The goal being that each prisoner should choose the box which contains their own name. If any one of the prisoners does not then they all lose the game. The prisoners aren't allowed to communicate in any way (with each other) what boxes they picked.
If each prisoner picked $n$ boxes at random, then the probability that they win the game (each picks their own name) is $\dfrac{1}{2^n}$ which is pretty small.
They are allowed to choose a strategy before any of them enter the room.
Show that there is a constant $c \gt 0$ (independent of $n$) and a strategy such that the prisoners win the game with probability at least $c$.
No comments:
Post a Comment