81
$\begingroup$

One day, the warden of a prison is, like most wardens in puzzles, feeling a little bit capricious and decides that he wants to get rid of his prisoners, one way or another. He gathers all the prisoners in the yard and explains to them - "Tonight, I will go to each of you, hand you a key, and tell you who has your key. Each day after that, while the others are out of the cells and no one is watching, I will allow each of you to place your key in someone else's cell - and each night, you may collect the keys in your own cell. If, at any point, you are certain that everyone has the key to their own cell, you may summon me, at which point each of you will open your own cell and walk free. If anyone has the wrong key, everyone will be executed then and there. You may discuss your strategy before tonight, but afterwards no communication will be allowed regarding my game. - Oh, and by the way, if you are still here seven years from today, I will execute everyone - it'll be a big birthday for me and I want to retire!"

That night, just as promised, the warden went to each cell and gave each prisoner a key. As he handed each prisoner the key, he whispered to them the name of the person possessing the key to their cell. The keys were entirely indistinguishable from one another, but that was okay, because the prisoners had not counted on being able to tell anything about them. Indeed, the prisoners all seemed confident.

Each day for the nearly seven years, the prisoners all anonymously gave the key in their possession to someone else. Then, hardly a month before the deadline, a prisoner shouted to the warden that they were ready. All the prisoners were certain that they would live, and, lo and behold, when they put the keys in the locks to their cells, every cell opened.

What was their strategy? Exactly how many days did it take?

Hint:

The warden had learned this from his own days as a prisoner, when the same challenge was issued to him and just two other prisoners. It took only six days of trading keys before they were released.

Edit: Oops, turns out my prisoners were kind of dumb in their choice of strategy. (If anyone wants to puzzle out what I was thinking of, the information in the post about should be sufficient - but I consider the puzzle, and this question to more about the most efficient way to do it). The prisoners, if wise, can be free in less than a fortnight.

Improve this question
$\endgroup$
1
  • $\begingroup$ I don't understand " I will allow each of you to place your key in someone else's cell - and each night, you may collect the keys (from where?) in your own cell" (I didn't look at the solution) : A goes to B's cell, puts his key there. Then should he must collect the key of B or he can collect the key of C? $\endgroup$
    – user31076
    Commented Oct 30, 2016 at 14:04

10 Answers 10

Reset to default
124
$\begingroup$

9 days.

Every day, each prisoner with an unknown key passes it to the next cell to the left (or to the next guy in alphabetic order, sentence length, age... w/e, just agree on the order on that first day).

Since they know where in the order the owner of their own key is (relative to them), they know on which day to expect their key - they get to keep that, and keep passing the unknown keys as usual. (For example, if guy 4 know guy 7 had his key, he should keep the key he gets at day 3.)

After 9 exchanges, technically possible in the afternoon of day 9, they can be sure everyone has their key.

Improve this answer
$\endgroup$
8
  • 3
    $\begingroup$ Although the rules don't forbid it, this solution will have some prisoners get their key faster than others and thus they will not place anything in their neighbor's cell the following night. At some point they will even have 2 keys. But as I said, there's no restriction regarding that. $\endgroup$
    – Bogdan Alexandru
    Commented Jan 8, 2015 at 8:24
  • 4
    $\begingroup$ @BogdanAlexandru It specifcally allows it by saying "you may collect the keys in your own cell". $\endgroup$
    – corsiKa
    Commented Jan 8, 2015 at 23:14
  • 4
    $\begingroup$ Am I correct in thinking that this (and all of the other <2520 answers) rely on the prisoner being able to distinguish a key he already has from a newly-added key? I took "each night, you may collect the keys in your own cell" to mean the opposite. $\endgroup$
    – DevOfZot
    Commented Jan 9, 2015 at 20:17
  • 4
    $\begingroup$ @DevOfZot: yeah, intuitively one might think the prisoner can tell the difference between "the key he left the cell with this morning, and has been carrying around all day, but chose not to place in another cell", from "the key placed in his cell". It might depend whether keys are fermions or bosons, hence whether they collapse together whenever two are in the same cell ;-) The question doesn't say the prisoner can keep them apart (e.g. in different hands), and almost equally intuitively the prisoners can scratch a grid on the floor as in Callidus's answer and the whole problem's trivial. $\endgroup$
    – Steve Jessop
    Commented Jan 9, 2015 at 22:48
  • 5
    $\begingroup$ That sounds generalizable, but it also requires the prisoners to have the option to not move their keys, which would seem to violate, "Each day for the nearly seven years, the prisoners all anonymously gave the key in their possession to someone else." Seems like these "devious warden" puzzles always come down to very subtle details of wording! $\endgroup$
    – DevOfZot
    Commented Jan 10, 2015 at 0:14
34
$\begingroup$

If every prisoner has a number assigned, that each other prisoner knows, they can leave the prison after 13 days. On day $i$, prisoner $i$ gives his key to the person that holds his key, it is returned on day $i+1$. So, at the start of day 12 every prisoner is holding the key he had in the beginning, and he knows who's key it is. On day 12 they hand over all the keys to the appropriate inmate, and on day 13 they challenge the guard.

You did not mention that they have such numbers assigned by any means - and it wasn't necessary until today. So how would they agree on a common numbering scheme?

The algorithm you thought of, on the other hand, works even when the prisoners do not have numbers from 1 to 10 assigned previously. If, for exactly 2519 days, every prisoner gives the key he holds to the one he was told would have his key, they can walk free after 2520 days.

Why 2520? Because it is (2*2*2*3*3*5*7) = LCM(1,2,3,4,5,6,7,8,9,10), and these are all possible lengths of the cycles in a permutation of any ten values. So for any permutation $p$ of any ten values, $p^{2519}$ = $p^{-1}$.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ The only issue I have with this is the following: say A has B's key and B has A's key. On day one, A puts his key in B's cell. Day 2, B returns A's key and puts his own key in A's cell as well. How does A know which key to return? Of course, this can be solved if the prisoners may test keys, or agree to put returned keys on the ground and 'new' keys on the bed, or something. $\endgroup$
    – EagleV_Attnam
    Commented Jan 7, 2015 at 10:55
  • 1
    $\begingroup$ Yes your scheme will break, if someone gets two keys at once - since keys cannot be distinguished, this will kill every solution instantly. So better Florians Solution with 12 Days. Each one gives his key on day i and all return their key on day 10 and on day 11 everybody know whom to give their key. $\endgroup$
    – Falco
    Commented Jan 7, 2015 at 12:34
  • 16
    $\begingroup$ +1 For figuring out the strategy the prisoners originally used. $\endgroup$
    – Callidus
    Commented Jan 7, 2015 at 13:04
17
$\begingroup$

I don't know if this works, necessarily, but I think it does.

Organize the prisoners $A$ through $J$. On day 1, prisoner $A$ puts his key outside the cell of whoever has his key (we'll call him $A_2$). Nobody else moves keys. On day 2, $A_2$ returns the key he receives to prisoner $A$'s cell. Day 3 starts, and prisoner $B$ puts his key outside of $B_2$'s cell. $B_2$ returns the key on day 4. Continue this until day 20, when prisoner $J_2$ returns the key to $J$. On day 21, each prisoner puts the key by the cell that they are supposed to. For example, if prisoner $E$ gets a key on day 7 and returns it on day 8, he knows to put his key outside of prisoner $D$'s cell.

In other words, if a prisoner receives a key on day $x$, they will place their key outside cell $(x+1)/2$* (converted to a letter, of course).

Hopefully this makes sense and works as a solution. I haven't tested it fully but logically it should (unless I'm missing something here).

*: I'm bad at MathJax, someone help

Improve this answer
$\endgroup$
15
  • $\begingroup$ Yeah, that should work. After your comment, I thought of a way even faster than this, but highly related - there's no reason that you couldn't have A give their key on day 1, B give their key on day 2, etc. and then, on day 11 have everyone return their key to the proper person (since they know which day the received it on). You could edit this answer to use that optimization if you wanted - it's the same essential idea as you already have. $\endgroup$
    – Milo Brandt
    Commented Jan 7, 2015 at 6:08
  • 4
    $\begingroup$ An improvement on Meelo's improvement: On days 1 to 9, prisoner in cell n gives his key to the one who has his own key. On day 10 all keys are returned (a key received on day n is returned to cell n). On day 11 the returne key is delivered to the same cell. The one who never received a key on days 1..9 delivers his key to cell 10. On day 12 everybody has his key. $\endgroup$
    – Florian F
    Commented Jan 7, 2015 at 11:30
  • 3
    $\begingroup$ On day 2, A2 returns the key he receives to prisoner A's cell. How does A2 know which cell belongs to prisoner A? $\endgroup$
    – Trisped
    Commented Jan 7, 2015 at 18:27
  • 1
    $\begingroup$ @Trisped Only A gives out a key on day 1. So on day 2, the person with 2 keys is A2. They return the extra key to A $\endgroup$
    – mdc32
    Commented Jan 8, 2015 at 0:00
  • 1
    $\begingroup$ But they are not allowed to communicate; I assume this include how many keys everyone has at any point. $\endgroup$
    – ratchet freak
    Commented Jan 8, 2015 at 14:28
12
$\begingroup$

The first day, "while no one is watching", a prisoner takes his key and tries it in the lock of each of nine other cells. The prisoner swaps his key for the one that is in the cell that opens. The prisoner then tests that key in the remaining eight doors, and swaps again. The prisoner repeats the process for the remaining seven etc.

The first night the warden is called and all walk free.

Of course, if the keys really are indistinguishable, they will all open all the doors.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ This seems to be the simplest solution. If no one is watching and they're allowed to place it in "someones" cell, it stands to reason they can access all the cells. $\endgroup$
    – Mikey Mouse
    Commented Jan 7, 2015 at 14:32
  • $\begingroup$ He doesn't know whose cell his key opens - he knows who has his key. Also the warden "allows you to place the key in the cell" not "in the door of the cell", and not "you can take a key from the other cell" but only "you can collect keys in your cell at night". Sorry - I don't think you read the problem very well. $\endgroup$
    – Floris
    Commented Jan 8, 2015 at 7:12
  • $\begingroup$ @Floris, I've amended my answer accordingly. Since the keys are indistinguishable and no one is watching does it matter what the warden said. $\endgroup$
    – Jodrell
    Commented Jan 8, 2015 at 8:37
9
$\begingroup$

Just in case it's possible to put the keys in specific locations in a cell...

Each prisoner draws a map of the prison on his floor (or a grid and each prisoner chooses a square that everyone else knows about, or a set of unique locations in the cell, etc).

On day one, each prisoner puts his current key in the cell of the person who has his actual key, in the location corresponding to the prisoner putting the key in. That evening, each prisoner knows whose key he (originally) had, which is also the person who put that key in their cell.

On day two, each prisoner puts the key they got on day one back in the cell of the prisoner he got it from. Everyone now has their original keys, but now they know who owns it.

On day three, each prisoner puts the key they got back on day two in the cell of its proper owner. That night when everyone is back in their cells, they summon the warden.

I rather think the intention of the puzzle is that the "added" keys don't go in any particular location, but you never know.

Improve this answer
$\endgroup$
9
$\begingroup$

2 days

Day 0 (strategy discussion)
Each prisoner is given a number.
One prisoner is chose. In his cell is designed a 10 x 10 grid (using chalk if available, other wise distance from the walls).

Day 1
Each prisoner brings the key in they were given to the designated cell. They place the key in the row corresponding to their number and the column corresponding to the number of the prisoner who originally received their key.

Day 2
The prisoner with all they keys uses the columns to determine who needs which key and the rows to determine which key to give them. The prisoner then distributes all the keys to the correct cells and calls the warden.

Thoughts:
I find that good puzzles require the use of resources which are required to be present in the definition (space in a cell) but not directly mentioned.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Good answer. Clearly the fastest way and appears to be completely within the rules. $\endgroup$
    – NotMe
    Commented Jan 8, 2015 at 18:02
  • 1
    $\begingroup$ I would argue that the placing of the key into the grid constitutes communication and it thus against the rules. $\endgroup$
    – Jack Aidley
    Commented Jan 9, 2015 at 16:05
  • 1
    $\begingroup$ @JackAidley I will allow each of you to place your key in someone else's cell Placing the key in the cell is explicitly allowed. $\endgroup$
    – Trisped
    Commented Jan 9, 2015 at 17:44
  • 3
    $\begingroup$ @Trisped: placing the key in a cell is, yes, but not placing it into a grid according to a pre-agreed system of communication. You're attempting to dodge the "no communication" limit. May as well have everyone write down who has the key. $\endgroup$
    – Jack Aidley
    Commented Jan 9, 2015 at 18:23
  • $\begingroup$ @JackAidley Leaving a key in someone else's cell is also communicating (which is how the prisoners know when they have the correct key). Also, comments on the question indicate that different locations in the cell are allowed. In addition, no physically visible grid is required. The prisoner is just choosing where in the cell to place the key. As such it is clear that the ... no communication will be allowed regarding my game. clause is referring to talking/writing about the game including strategy and who has what key, not the placing of the key in the cell which is explicitly allowed. $\endgroup$
    – Trisped
    Commented Jan 9, 2015 at 21:28
5
$\begingroup$

All prisoners give their keys to the same person. This person tries all keys in their lock, keeps the one that works and passes on the rest. This solves the problem in 10 days and no one has to do math.

Improve this answer
$\endgroup$
0
2
$\begingroup$

The prisoners all give their keys to the same prisoner on the first night. Then when she places the keys the next day she tries them in every lock, and leaves each key in the right cell. Everyone is freed on night 2 regardless of the number of prisoners.

Improve this answer
$\endgroup$
1
  • $\begingroup$ when the ward gives the keys to the first prisoner in day one the prisoner kills the ward, takes all of his keys, escapes and lets the others rot in prison. Not sure if this means the answer is one day or never... $\endgroup$
    – bolov
    Commented Jan 7, 2015 at 20:35
2
$\begingroup$

Since the answer has already been given (both the intended answer, and the "best" answer), I'll just throw out my subversive answer:

The night before they all agree to leave the key in their possession under their pillows. While pretending to give the key in their possession to a new cell, they each go and retrieve their key on day one. That first night they call the warden and open their cells.

The warden, aware of their deception but also that they were not expressly forbidden from finding or removing a key, shoots them or lets them go depending on his capricious whim.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Would it be possible for you to edit in a more detailed explanation as to what in the question leads you to believe this answer is correct? By site policy, answers need to contain detailed explanations, not just be guesses, otherwise they may be deleted. Thank you! $\endgroup$
    – user20
    Commented Jan 12, 2015 at 7:44
  • 1
    $\begingroup$ What exactly is unclear? I've already said this answer is subversive, by which I mean it's neither the intended solution, nor is it following the spirit of the puzzle but rather a little exercise in lateral thinking. The warden put limits on their communication and made an explicit allowance for each prisoner to enter another cell of his choice, but failed to make an explicit rule about what would be allowed or prohibited while in there. It's clear that the intention is that they will place the key in their possession in that cell, but a little subterfuge goes a long way. $\endgroup$
    – Jason
    Commented Jan 12, 2015 at 15:45
0
$\begingroup$

Every prisoner gives his key to the person who has the key to his cell (as told by the warden). Next night, they repeat the whole process. If no one messes up and keeps giving their keys (that means a different key each night) to the same person, everyone will automatically end up with their keys after exactly 9 nights. This is because the telling them creates a chain, in which all prisoners are linked. (Every prisoner has the key to someone elses cell and knows the one who has the key to their cell) Passing keys around in the described fashion "rotates" this chain. Repeat it 10 times and each prisoner ends up with the key he initially got from the warden, one time less and they end up with their own key. Sorry I can't really explain it properly, but it works (I tried it 2 times with playing cards) and is fool-proof. For a maybe better explanation, the problem here is a quite similar: https://www.youtube.com/watch?v=C5-I0bAuEUE

However, I'm not sure if it will still work if there are two chains, i.e. Pris4 has the key to Cell2 and vice versa - then the two will just switch keys back and forth…

Improve this answer
$\endgroup$
1
  • 8
    $\begingroup$ This works if we assume that it's a chain of 10 prisoners. But for three prisoners, A, B, and C, if the warden gives A's key to B, B's key to C, and C's key to A, after 9 rotations, everyone has the key they started to - so A still has C's key, which isn't good. (The other seven prisoners could be given their own keys, or put in a cycle, or whatever) Indeed, the warden can induce any cycle with length from $1$ to $10$, so it actually, as noted in Alexander's answer, takes $2519$ exchanges to ensure that, regardless of cycle length, the chains will be rotated an appropriate amount of time. $\endgroup$
    – Milo Brandt
    Commented Jan 7, 2015 at 22:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.