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

Question

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.

Answer 1

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))))

Answer 2

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

Answer 3

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.

Answer 4

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.