Two prisoners, in separate cells, are watched over by one eccentric and whimsical guard. One day he (inevitably) decides to give the prisoners a chance to earn their freedom by playing a game with them. The game works as follows:
- Prisoner $1$ is given a special stone.
- On the first day, the guard arrives in Prisoner 1's cell with three distinct boxes, and she may choose which box to place the stone in. The guard will then deliver the three boxes (plus stone) to the other prisoner.
- The next day the guard will begin at the second cell and the same process occurs in the other direction, with Prisoner 2 choosing which box (of the same three boxes) to place the stone in, and the guard delivering them back to Prisoner 1.
- This continues, with the single stone being delivered in alternate directions on alternate days, indefinitely. (Once this guard has thought of an idea, he commits.)
But there is a twist. On each day one of the boxes, known only to the guard, is the 'Greedy' box. When the guard is midway through delivery, the stone will be moved into the 'Greedy' box if it wasn't there already. But if the stone is already in the 'Greedy' box, then it is placed in one of the other two boxes at random. Neither prisoner will witness how the stone moved. At the end of every day, the identity of the 'Greedy' box will change acording to a simple three day cycle (i.e. 123123123), but the prisoners do not know what which box begins as the 'Greedy' box. And while they know that the greedy boxes follow the pattern 123123123, they dont know which box is box 1, which one is box 2 and which one is box 3.
Each day, when the guard has finished his delivery and the prisoner sees which box contains the stone, she has the option of pointing to the box she believes is the 'Greedy' box that day. If she does this and is correct, both prisoners go free. If she is wrong though, the game is over, and both remain imprisoned for eternity, forced to endure more of this crazy guard and his 'games'. They both understand all these rules, and are given just one chance to communicate beforehand to come up with a strategy.
How can they devise a plan to guarantee their freedom? And - more to the point - how can they do so in the fewest number of days, so they spend as little time with this maniac as possible?
A couple of notes:
- The boxes are distinct and memorable, so they can be told apart and remembered from one day to the next, but the prisoners do not yet know how they are distinct when creating the strategy. Nor will the boxes be presented to each of them in a consistent order, and so their strategy cannot depend on that either. (This means that, for example, if both prisoners decide to label the three boxes as A, B and C upon seeing them, they have no way of guaranteeing that they label them the same way as each other.)
- No, the prisoners cannot mark the stone, or mess with the boxes, or put anything else in a box, or otherwise 'think outside the box'. The only communication between them is in the choice of which box to place the stone in each day.