# The Greedy Box (Or: Another crazy guard offering his prisoners freedom)

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. ABCABCABC), but the prisoners do not know what the order is, or which box begins as the 'Greedy' box.

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.
• Just checking: there's just one stone, and (from day 2 on) the guard presents to one prisoner (each day, alternating between them) the 3 boxes with the stone in one of the boxes, and that prisoner can move the stone to a different box. – Lawrence Mar 1 '18 at 8:44
• I (quite probably wrongly as I first read this puzzle while getting ready for bed) interpreted the puzzle as having the following structure. Day 1: prisoner 1 puts stone in box, guard presents boxes to prisoner 2. Day 2: prisoner 2 puts stone in box, guard presents boxes to prisoner 1. Repeat ad infinitum (or ad solution). I think this only results in solutions being one day shorter (under my interpretation), as the sequence of events is the same but the presentations of the boxes each occur a day earlier in my interpretation. – T. Linnell Mar 1 '18 at 8:53
• @T.Linnell Actually, it probably doesn't matter - whether 1 stone or many, they may all end up in the same spot, so the worst case is still the same regardless of the number of stones in the puzzle. – Lawrence Mar 1 '18 at 12:53
• @Lawrence Yes, there's just a single stone, and the first delivery is on day 1. – Alevya Mar 1 '18 at 15:57

The following strategy gives the prisoners a way to escape in...

at most five days, with an average of 4.375 days.

## Strategy

### Selecting a box for sending the rock

• Day 1: Select any box, which is henceforth referred to as "Box A".
• Days 2-4: Choose the same box that the rock was delivered in the day before.
• Day 5 (if needed): Choose Box A.

### Guessing the greedy box

• Days 1-3: No guess.
• Day 4: If the rock was delivered in Box A this time or the preceding time (on days 2 or 4), guess the box that currently holds the rocks as the greedy one. Otherwise, pass and wait until tomorrow.
• Day 5 (if needed): Guess the box the rock is delivered in as the greedy one.

## Explanation

Label the box selected by the first prisoner on the first day as A. Since the rock always switches boxes in transit, we can label the box the second prisoner receives the rock in as B and the remaining box as C.

Since the greedy box always holds the rock either when taken by the guard or when he delivers it, we know that C was not the greedy box on the first day. That leaves four possible orders for the greedy boxes: ABC, ACB, BAC, or BCA.

On day 2, B is always chosen and the rock is delivered in either A or C.

• ABC: A or C
• ACB: always C
• BAC: always A
• BCA: always C.

The two permutations with A delivery on day 2 both have C as greedy on day 3. After the rock is placed in A on day 3 and delivered in C, it is placed in C on day 4 and always delivered in that day's greedy box. This ensures that if delivery is in A on day 2, that delivery will be in the greedy box on day 4. This also allows us to drop BAC from further analysis because it is always A on day 2 delivery.

We can analyze the possible deliveries for day 4 after C is delivered on day 2.

• ABC: A, B, or C. (Day 3: C to A or B. Day 4: A to B or C; or B to A.)
• ACB: always A. (Day 3: C to B. Day 4: B to A.)
• BCA: always B. (Day 3: C to A. Day 4: A to B.)

Note thate A is only delivered on day 4 when it is the greedy box. Combined with the previous analysis, we then know that when A is delivered on days 2 or 4, the greedy box ends up with the rock on day 4. This also allows us to drop ACB since it always holds A then.

Neither of the remaining permuations, ABC nor BCA, has A as the greedy box on day 5. So choosing A allows the rock to be delivered in the greedy box that day.

__Note:__This strategy is not optimal. It could be slightly improved by selecting A on day 4 if the rock is delivered in C. There may be even better improvements available.

## Validation

The following Python script implements the strategy, validates the guesses, and calculates the average number of days.


from __future__ import print_function

BOX_A = 0 # Index of box chosen first time

def guess(deliveries):
"""Return greedy-box guess or None for no guess."""
if len(deliveries) == 4:
if deliveries[-1] == BOX_A or deliveries[-3] == BOX_A:
# It's day 4 and Box A has been delivered on day 2 or day 4
return deliveries[-1]
if len(deliveries) == 5:
# It's day 5
return deliveries[-1]
return None

def choose(deliveries):
if len(deliveries) == 0 or len(deliveries) == 4:
# It's day 1 or day 5, choose Box A
return BOX_A
return deliveries[-1]

def test(permutation, deliveries):
greedy = permutation[len(deliveries) % 3]  # Greedy box
chosen = choose(deliveries)                # Box chosen for rock

if chosen == greedy:
# Move from greedy to others
options = [i for i in range(3) if i != greedy]
else:
# Move to greedy
options = [greedy]

days = 0

# Iterate possible delivery options
for option in options:
updated = deliveries + (option,) # Updated deliveries
guessed = guess(updated)         # Guess for greedy box

if not guessed is None:
# Validate guess
assert guessed == greedy # Ensure guessed box is the greedy one
days += len(updated)
else:
# No guess, continue with updated deliveries
days += test(permutation, updated)

# Return average number of days for successful guess
return float(days) / len(options)

import itertools

# All possible orders of greedy boxes
permutations = list(itertools.permutations(range(3)))

days = 0
for permutation in permutations:
days += test(permutation, tuple())

print('Average days to escape: %f' % (float(days/len(permutations))))


• Nice, that's better than I expected! Is it bad practice that I hadn't even worked out the best solution myself when I posted the puzzle? – Alevya Mar 2 '18 at 6:43
• @alevya I know that even this isn't optimal, so someone else may do even better. – D Krueger Mar 2 '18 at 13:51
• That's what a site like this is great for! I await it eagerly! – Alevya Mar 2 '18 at 15:56

There is one relatively simple way to solve this, but I doubt it's 100% optimal...

Prisoner 1 always puts the rock in the same box

Without loss of generality, let's assume she's always putting it in box A. After the first 5 days, Prisoner 2 notices that one box hasn't had the rock yet, when passed to her.

Here are all the possibilities of orders that Prisoner 2 sees:
BBC, BCB, CBB, CCB, CBC, BCC

Then Prisoner 2 knows that whichever box got the rock once over the first 3 of her days, that box was the greedy box. (e.g. BBC -> C was greedy on day 5)
Prisoner 2 can now wait at until the day she is sure about repeats and she can guarantee their freedom.

Here are the day counts (assuming you can only guess when delivered to):
BBC, CCB -> Free on day 5
BCB, CBC -> Free by day 9 (day 7 if A day is 7 and flips)
CBB, BCC -> Free on day 7

• The nice thing about this method is it would work even if the stone was always delivered the same direction. Of course, this positive is also a negative, because it means half of the deliveries are conveying no information at all - so you're right to suspect it isn't optimal. – Alevya Feb 28 '18 at 21:11

I believe this can be solved in no worse than

6 days

Basic strategy:

Prisoner 1 (P1 henceforth) picks a random box on day 1, since it's established the method of distinguishing the boxes is unknown a priori and hence boxes cannot be preselected. P1 can thus do no better than pick randomly.

On day 2, prisoner 2 (P2) puts the stone in the same box she received it in on day 1. This is better than a random choice as it gives P1 information about what box the stone ended up in on day 1.

On subsequent days, they continue to stick with their respective choices.

After receiving the stone three times, the stone will have appeared in one box twice and one box once. The box it doesn't appear in is the one the other prisoner selected, and the box it appears in once is the greedy box on that same day it appeared there, as also noted in kevin_ten11's answer.

So if a prisoner sees the stone in boxes AAB on their first three times, they can instantly solve since they know B is greedy today. If they see BAA or ABA they don't know based on the boxes alone if A or C is greedy today (but they know B was greedy either 4 or 2 days ago respectively).

Proof of bound:

Assume without loss of generality that the greedy boxes cycle ABCABCABC... There are then four cases in terms of which boxes the prisoners put their stones in:

Case 1: P1 picks A, P2 receives it in (and then picks) B.

Day | Greedy | P1 | P2
----+--------+----+----
1 |    A   |    |  B
2 |    B   | A/C|
3 |    C   |    |  C
4 |    A   |  A |
5 |    B   |    |  B
6 |    C   |  C |
P2 doesn't have enough information to solve on day 5; all she knows is that C is greedy on day 3/6. In general P2 has much less information on day 5 than P1 has on day 6. All P2 knows by day 5 is which box P1 chose and the greedy box on one day of the cycle; she cannot solve the game on day 5 unless she knows the greedy box for day 5 (by seeing BBC or similar).

On day 6 either P1 has seen AAC (and thus he deduces C is greedy today), or CAC. Either way he knows P2 puts the stone in box B. If P1 sees CAC, P1 knows A is greedy on day 1/4 etc. So, since he knows P2 saw B on day 1 (as per strategy), he knows P2 saw either BBC or BCB, since B and C were greedy on days 3 and 5 (but P1 doesn't know which way round). But if P2 saw BBC, P2 would've solved the game on day 5. Since she hasn't, P2 saw BCB so C is greedy on day 3/6 and P1 solves.

Case 2: P1 picks A, P2 picks C. P2 sees CCB and solves on day 5.
Day | Greedy | P1 | P2
----+--------+----+----
1 |    A   |    |  C
2 |    B   |  B |
3 |    C   |    |  C
4 |    A   |  A |
5 |    B   |    |  B
6 |    C   | A/B|

Case 3: P1 picks B; P2 picks A (since A is greedy today, so B will always see the stone in box A).
Day | Greedy | P1 | P2
----+--------+----+----
1 |    A   |    |  A
2 |    B   |  B |
3 |    C   |    |  C
4 |    A   | B/C|
5 |    B   |    | A/C
6 |    C   |  C |

If P1 sees BBC, he knows C is greedy today (day 6). Otherwise he sees BCC, and knows B is greedy on day 2/5. He also knows P2 puts the stone in box A. So P2 received the stone in box A on day 1, when either A or C was greedy. But as P1 put the stone in B, then C can't have been the greedy box, or P2 would've found the stone in C. Therefore A is greedy on day 1/4, and C is greedy day 3/6.

Case 4: P1 picks C; P2 picks A for the same reason as before.
Day | Greedy | P1 | P2
----+--------+----+----
1 |    A   |    |  A
2 |    B   |  B |
3 |    C   |    | A/B
4 |    A   | B/C|
5 |    B   |    |  B
6 |    C   |  C |

If P2 sees AAB she can solve the game on day 5. Similarly if P1 sees BBC he can solve the game on day 6. The only sub-case left is if they see ABB and BCC. Then P1 reasons: B is greedy day 2/5, so P2 must have seen the stone in B on day 5. P2 puts her stone in A, so she must have seen the stone there on day 1. So P2 must have seen either AAB or ABB. But if she saw AAB she would've solved the game yesterday, therefore she saw ABB, and A is greedy on day 1/4 hence C is greedy on day 3/6.

• Looks good to me, and presented very clearly! It's a little different from the method I had in mind, but with the same maximum number of days. I'm pretty sure this is optimal, but I haven't proved it. Maybe I'll just say 'Proof left as exercise for the reader' and leave it at that? :) – Alevya Mar 1 '18 at 16:23
• Eh, scratch that - looks like D Krueger has us both outsmarted! – Alevya Mar 2 '18 at 6:39

EDIT: This is solution is incorrect because (as discussed in the comments) I didn't account for the prisoners not knowing how the boxes are unique before beginning.

The following cannot lose and wins in 3-4 days. (assuming I understood everything).

Use your discussion time to agree that P1 will always place the stone in the Red box and P2 will always place the stone in the Blue one.

Using R -> B -> G (for example) as the guard's order for moving the stone:

• Day 1: The Stone is in R. It moves to either B or G.
• If it moves to B, then X is either R or B on Day A [of the Cycle].
• If it moves to G, then X is either R or G on Day A.
• Let's assume it moved to G.
• Day 2: The Stone is in B. It moves to either R or G.
• If it moves to R, then X is either B or R on Day B.
• If it moves to G, then X is either B or G on Day B.
• Let's assume it moved to G
• Day 3: The Stone is in R. It moves to G.
• Therefore, X is either R or G on Day C.
• Day 4: The stone is in B. It moves to R.
• Therefore, X is either B or R on Day A.
• We already now X is NOT B on Day A. Therefore....
• We now know that X is R on Day A (which is today) and can win!
• Day 5: The stone is in R. It moves to B.
• Therefore, X is either R or B on Day B.
• We now know that X is B on Day B. Therefore, we know that X is G on Day C.

We now know the correct Greedy box order and can win at any time.

This method is foolproof regardless of the hidden box order.
If the hidden order is B -> R -> G, you can win on the 3rd day instead of the 4th.

Sorry about the lack of spoilers. For the life of me, I couldn't get the >! tag to work with the list formatting.

• Sounds reasonable, but doesn't work with the puzzle as posted: "the prisoners do not know how the boxes are distinct when creating the strategy", so they can't agree to select the Red box or the Blue one. – ffao Mar 1 '18 at 8:09
• Ah, I missed that. Hmm... creatively thinking, I suppose they could agree on a simple categorization before hand. Perhaps the "largest box" and the "smallest box". Or more methodically, they could take a few extra days putting it in their "chosen" box until the results made it apparent to the other prisoner which box their partner had chosen. There's a proof for that I'm sure, but I'm too tired to write it. – Hyperglyph Mar 1 '18 at 8:24
• If the boxes are distinguishable, it shouldn't be hard to agree on an order on them, like alphabetical order of a word that would describe it. – Florian Bourse Mar 1 '18 at 10:49
• @FlorianBourse What if the distinction is made by cryptic symbol put on it? – Untitpoi Mar 1 '18 at 13:04
• Consider the space as discrete (use Planck's Length as a unit), agree on a total order on $\mathbb{Z}^3$, and then compare – Florian Bourse Mar 1 '18 at 15:00