# Two prisoners and twenty marbles

Two prisoners are planning their escape. Their cells are locked with a padlock that must be opened with a 5-digit code (numbers 00000 to 99999). Each prisoner knows the code of the other prisoner's lock. One prisoner starts with a small bag with 20 identical marbles, while the other prisoner starts with no marbles. Each night the prisoner with the bag can pass the bag with 0 or more marbles to the other prisoner. This continues until both prisoners know the code to their cells. There cannot be any other communication between them.

Before they learn the codes, the prisoners agree on a strategy. What strategy should they use that guarantees their escape and minimises the total wait time?

• Prisoners do not have any other marbles out of those 20?
– z100
Mar 27 at 13:19
• no. They only have those 20 marbles. Updated the description Mar 27 at 13:20
• Can they decide at exactly what time they pass the bag? Does the bag have a string that can be knotted in various ways? Can the bag be turned inside out? Can they heat up some marbles using the famous one light bulb? Can they leave the light on or off? So many quesions! Mar 28 at 20:48
• Wow so many questions! I guess in the spirit of this puzzle no further communication is allowed. But you could allow it for an alternative version of this puzzle. Heat up marbles with a light bulb? - what is that? LoL Mar 29 at 9:53
• Yes you do. In your example the second prisoner won't be able to send 5 back, only 2 or less. Mar 29 at 10:53

Same number of nights as in PDT's solution but perhaps expressed in a simpler way.

The number of nights is still 10.

Each night the prisoner with the bag keeps as many marbles as the next digit in the other prisoner's lock code. The rest is sent to the other prisoner. The prisoner always has 11 or more marbles to play with, so they will never be short of marbles.

With this method, 18 marbles are already enough. Possibly the bag is passed with no marble inside.

• That's correct, well done! I chose this answer over PDT's because it is simpler and easier to understand. Mar 28 at 5:42
• Unless the question is edited to clarify that it's not possible, the first prisoner can leave after 9 days without telling the second prisoner the 5th digit. Mar 28 at 14:24
• @matt_rule "This continues until both prisoners know the code to their cells." Mar 28 at 14:47
• If they don't trust each other then nothing prevents the first prisoner to send a random number of marbles. For the second one it is not so easy because the 1st prisoner will know it before sending the last bag. This being said, the last digit can be brute-forced, so ... . Anyway, I assume they collaborate. Mar 28 at 15:50
• Of course, the prisoner who gets out first can just open the other prisoner's lock when he/she gets out, which saves at least one night. Mar 29 at 10:31

They can do it in 10 nights at least:

The number of marbles in a bag per pass codes the leftmost unsolved digit of the padlock.

Prisoner A codes his marbles like so 11=0, 12=1 until 20=9. Then he gives whatever amount of marbles to prisoner B. One digit down. Then prisoner B has more than or equal to 11 marbles.

Then depending on how many marbles he receives (prisoner A knows this) he should code it where x being the most number of marbles he possesses x=9, x-1=8, x-2=7 and so on until x-9=0 two digits down. (No marbles are the minimum (of course 2 marbles are the minimum in this case I meant hypothetically for smaller marble sets.)

Then prisoner A does the same for the next digit of B and they go back forth repeating the above until they know the full codes of their respective padlocks.

It works because with each pass, the prisoners know how many marbles their partner has and each prisoner always has enough marbles to code any digit for his friend.

Minimising worst case waiting time, one can not do better than the number of nights presented by others.

One can not safely lower by one night, since the person going second then only has

4 nights to pass their information. That means of the log2(100000)/4 bits of information per night, which is more than 4 bits, requiring on average more than 16 states to choose from per night. That means they need to have "most" of the marbles in their possession each time its their turn to pass the bag. This isn't compatible with the other person having to share their piece of information in 5 nights, which requires "almost half" of the marbles to share an average of 10 states per night.

So with the worst case being the already established bound, the only improvement is to make a scheme that short circuits in some cases.

Updated scheme

The main idea is the one of @Retudin:

Person A keeps 0-9 marbles each of their nights, encoding the code in base 10 in five nights. Person B keeps 0-11 marbles each night, encoding a base 12 number. After night 8, the first 13530 codes of the base 12 number are "final" codes, and we at at night 9, otherwise we need the 10th nights to distinguish between the remainders. Average, 9.865 nights

Now, this can be combined with the idea of:

Person B keeping more than the maximum of 11 they are suppose to keep. Each extra marble, up to keeping 19, corresponds to small range of codes that can be bailed out on night 9, and a new set of rules of how the remaining days should be coded.

Of course, person B can't always keep more marbles, for instance A may have kept 9 marbles to code their first digit, leaving B with no other option than the original 0-11 scheme. Or A has kept 8, so B only has the option to keep 0-12, and so on.

Keeping 12, 13, 14... corresponds to the following updates number of stattes each person can keep the next nights up to night 9 (A|B)

12: (1452 codes)
9*11*11*10|11*11*12

13: (1331 codes)
8*11*11*11|11*11*11

14: (1210 codes)
7*12*11*11|10*11*11

15: (1000 codes)
6*12*12*12|10*10*10

16: (810 codes)
5*13*13*12|9*9*10

17: (576 codes)
4*14*14*13|8*8*9

18: (343 codes)
3*15*15*15|7*7*7

19: (100 codes)
2*18*17*17|4*5*5

20: not worth it



The number of "final" codes also changes for each, in tabular form:

[14150,14150,14141,14110,14057,13984,13893,13783,13662,13530]


Final efficiency

9.814 nights

/end new scheme

Initial scheme below:

The first night, person A keeps 0-11 of the marbles, as person B only needs a minimum of 9 marbles to encode digits in the canonical way. Keeping 2-11 marbles is simply a digit +2, and the scheme continues as usual.

If on the other hand person A keeps 0 or 1 marble, they signal to B that they can take the opportunity to encode the code they know in only four nights. The scheme is then a new one:

Person A:

Has one of the 512 first codes. They will only send the 0 or 1 signal the first night if this is the case. In the following four turns, A will keep 0-3 marbles each night, encoding their code in base 4 with the initial 0 coding the first 256, and an initial 1 coding the next 256. This leaves 17 marbles for B each night

Person B:

With their 17 marbles, they encode their code in base 18, just barely covering the 100000 combinations in four base 18 digits. This always leaves 3 marbles for person A to perform their part of the scheme.

As this special cases only a small range of the numbers, it only reduces the expected waiting time to:

9.995 nights

One must hope the ~7 minutes saved is enough to clearly explain the much increased complications :)

A second, and larger, source of redundancy is perhaps easier to recover.

B could also use the extra two states (since A only needs 9 marbles) to signal that they don't need the last night, for instance by using them to encode double 0's or double 1's in their code, meaning they get one digit ahead. This is 6354/100000 codes

Bringing the expected time down to

9.932 nights on average

/end old scheme

• I like your thinking here. Perhaps there are special cases where the prisoners can use a different base (not base 10) to encode the code and save time. Mar 28 at 1:13
• With keep 0-9,0-11,0-9,0-11,0-9,0-11,0-9, if needed 0-11 around 9.87 is already possible (if my calculations are correct), and with more advance schemes like you describe this can be improved a bit. But nice that someone considers maximizing 9 day escape chance. Mar 28 at 16:25
• @Retudin How do you signal the "if needed"? Mar 28 at 16:36
• The prisoners have to agree on what combinations do not require the 10th day during the strategy determination. Of Bs 12^4 combination after day 8, around 13500 can be 'final' leaving 12*7236 different 10 day options to generate over 100000 in total. Mar 28 at 20:05
• The new 0-9/0-11 scheme is beautiful! The second idea with alternative schemes is efficient (I would never have thought about it) but a bit convoluted, for example when entering the "12" subscheme you could iterate this idea of keeping more than the 10 allowed on night 4. making it even more convoluted. I wonder if there is a better/prettier/cleaner way of exploiting this possibility. Mar 29 at 9:28

How about figuring out the code depending on the number of marbles each prisoners have by the end of the night.

For example:

1st night: Prisoner1 (P1) gives 20 marbles to Prisoner(P2) which means that P2's first digit is 0 because P1 has 0 marbles in his possession. P2 takes 9 marbles from the bag. P1 is left with 11 marbles, P1's code is 9

2nd night: P1 places all his marbles (11) in the bag. P2 has 20 marbles (9, from previous night + 11 in the bag). This mean P1 has 0 marbles, the code is 0 again. P2 placed 19 marbles in the bag for P1. P2 has 1 marble, P1's code is 1.

They communicate this way until they figure out each other's code. I think the formula is basically Code = 20 - X (X = # of marbles in the bag + how many the prisoner have each night) Edit: X can't be <10

I think this will work. Maybe there's something I have not accounted for, let me know.

A strategy that can get below 9.8 turns:

The starting player 'A' checks his number of 8's plus 9's

If 0: The Nth time A keeps marbles equal to his Nth digit.
If 1: The first time A keeps 8-17 marbles to mark the 10 possibilities for the value and position of the >7. After that A keeps marbles equal to the other 4 digits.
If 2: The first 2 times A keeps 8+ marbles; where the 40 most efficient of those combinations encode each combination of 2 high numbers/positions. After that A keeps marbles equal to the other 3 digits.
If 3: The first 3 times A keeps 8+ marbles; where the 80 most efficient of those combinations encode each combination of 2 high numbers/positions. After that A keeps marbles equal to the other 2 digits.
etc.
Player B keeps up to 13 marbles each time (assuming B has that much, otherwise up to what B has)

In group 1 (no high number,33%) player B can generate 14^5 possibilities and get to 9.663 days on average, the other groups are less efficient; group 2 (1 high number,41%) similarly reaches 9.826, group 3 (20% the worst group) 9.891. etc. This yields a weighted average of around 9.78

This base 14 setup for the second player seems to work well. Some additional efficiency can be gained since not all possibilities are used; like starting with keeping 18+marbles, A using 0-6 strategy instead of 0-7 in some situations, or B keeping more than 13 to signal specific code(s).

The simplest solution for each prisoner (still 10 days).

Each prisoner gives enough marbles to replenish the other with 10 marbles, then adds the next digit in marbles. The encoded digit of the receiving prisoner is the last digit of their total marble count.

One optimization that can lead to 9 days in many (6814) cases.

Prisoner_1 always leaves Prisoner_2 with 11-20 marbles, of which the last digit represents the lock digit. Prisoner_2 may leave Prisoner_1 with 10-19 marbles to be interpreted by the last digit. Prisoner_2 may also leave Prisoner_1 with 9 marbles to represent a decreasing sequence of 3, or 20 marbles to represent an increasing sequence of 3, both based on the prior known digit with an assumed starting point of 0 on day 1. If they're lucky, and Code_1 starts with 1,2 or 9,8, then both will get out in 9 days. Same is true if the sequence, 'n,n+1,n+2orn,n-1,n-2` exists in Code_1. If my math is right, they can shave a day off 6.84% of the time. They could further agree to switch roles once Prisoner_1 was ahead a sequence and had more than 10 marbles. In that case, there's a tiny chance they could shave a second day off of their escape.

The best case scenario for this scheme is done in 6 moves without sacrificing the guaranteed maximum of 10 moves.

Let's say the codes were 98761 and 98762. On day 1, Prisoner_1 sends 20 marbles. Prisoner_2 interprets "9,8" (from the descending wraparound sequence 0,9,8). On day 2, Prisoner_2 sends back 20 marbles, which Prisoner_1 interprets as "9,8". On day 3, Prisoner_1 sends 20 marbles, interpreted as "7,6". On day 4, Prisoner_2 sends back 20 marbles, interpreted as "7,6". On day 5, Prisoner_1 sends 12 marbles, filling in the last "2". On day 6, Prisoner_2 returns 3 marbles (leaving Prisoner_1 with 11 marbles) filling in the final "1".

My prisoner strategy without looking at anyone else's, (and still 10 days):

Each prisoner keeps the current digit of the other's code, and the other learns his digit from the difference between 20 and the number of marbles received.