81

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.

ghosts_in_the_code
  • 7,024
  • 1
  • 30
  • 100
Milo Brandt
  • 7,881
  • 2
  • 27
  • 53
  • 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? –  Oct 30 '16 at 14:04

10 Answers10

124

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.

keymaster
  • 1,136
  • 1
  • 7
  • 3
  • This seems to be both the shortest and simplest answer so far. – JonTheMon Jan 07 '15 at 15:35
  • 3
    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. – Bogdan Alexandru Jan 08 '15 at 08:24
  • 4
    @BogdanAlexandru It specifcally allows it by saying "you may collect the key*s* in your own cell". – corsiKa Jan 08 '15 at 23:14
  • @corsiKa That's correct, I had missed it, thanks! – Bogdan Alexandru Jan 09 '15 at 08:29
  • 4
    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. – DevOfZot Jan 09 '15 at 20:17
  • 4
    @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. – Steve Jessop Jan 09 '15 at 22:48
  • @Dev I didn't put much thought into the issue initially, since the intended 2520 answer didn't need it (though I clarified in a comment that this sort of solution was allowable). I've actually come across doubts that 2520 is the fastest solution with this restriction though - for $3$ prisoners, $3$ exchanges suffice as: Day 1: If prisoner 1 has your key, give your key to 2; if prisoner 2 has your key, give your key to 1; if prisoner 3 has your key, give your key to 3. Day 2: Give your current key to whoever had yours. Day 3: Same as Day 1. This is faster than the naive 5=lcm(1,2,3)-1 exchanges – Milo Brandt Jan 10 '15 at 00:02
  • 5
    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! – DevOfZot Jan 10 '15 at 00:14
34

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}$.

Alexander
  • 2,443
  • 2
  • 16
  • 20
  • 3
    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. – EagleV_Attnam Jan 07 '15 at 10:55
  • 1
    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. – Falco Jan 07 '15 at 12:34
  • 16
    +1 For figuring out the strategy the prisoners originally used. – Callidus Jan 07 '15 at 13:04
17

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

mdc32
  • 2,743
  • 1
  • 19
  • 39
  • 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. – Milo Brandt Jan 07 '15 at 06:08
  • Ahh. That's faster, but I just wanted to avoid any conflicts between situations where someone received a key and gives one away. Yours works well though, now that I think about it. I'm curious to see the intended solution - I can't even think of a solution where it would take that long without some useless days. – mdc32 Jan 07 '15 at 06:10
  • @Meelo: that gets complicated to figure: $A$ has $F$'s key, which he drops off at $D$'s door (because $D$ has $A$'s originally). $D$ has to know at the end that he has $F$'s key. Does the prohibition on communication not ruin that? – jscs Jan 07 '15 at 06:18
  • @JoshCaswell $A$ returns $F$'s key, and then puts his own original key at $D$'s door. – mdc32 Jan 07 '15 at 06:22
  • $A$ gave $F$'s key to $D$ on the first night. To whom does he return it, and when? What do you mean by "original key"? (I'm talking about Meelo's comment, not your answer.) – jscs Jan 07 '15 at 06:43
  • @JoshCaswell Sorry, misinterpreted your comment. On the second night, $D$ returns $F$'s key to $A$. – mdc32 Jan 07 '15 at 06:45
  • 4
    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. – Florian F Jan 07 '15 at 11:30
  • 3
    On day 2, A2 returns the key he receives to prisoner A's cell. How does A2 know which cell belongs to prisoner A? – Trisped Jan 07 '15 at 18:27
  • @Trisped All the prisoners know where the other prisoners are, so it shouldn't be difficult to return the key. – mdc32 Jan 07 '15 at 19:14
  • @mdc32 yes, but they don't know where the key came from. They know that it was placed in their cell, but they don't know who put it there. – Trisped Jan 07 '15 at 21:26
  • 1
    @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 – mdc32 Jan 08 '15 at 00:00
  • 1
    But they are not allowed to communicate; I assume this include how many keys everyone has at any point. – ratchet freak Jan 08 '15 at 14:28
  • @ratchetfreak I missed that too. Since only 1 person can move their key each day, if you end up with a key then you know it came from the person moving theirs for the day. – Trisped Jan 08 '15 at 16:51
  • @Trisped but you don't know who moved/left a key – Holloway Jan 08 '15 at 17:15
  • @Trengot _ On day 1, prisoner A puts his key outside the cell of whoever has his key (we'll call him A2). Nobody else moves keys._ On the first day, only one person can move a key, so if you get a key, you know who it is from. On all subsequent days only two people can move keys and one of them is returning the key to the previous owner. As a result you know who gave you the key. If you get two keys on the same day then you know one was your key. It is assumed that you can differentiate between the two keys (like they are left in different locations in the cell). – Trisped Jan 08 '15 at 18:00
12

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.

Jodrell
  • 323
  • 1
  • 7
  • 3
    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. – Mikey Mouse Jan 07 '15 at 14:32
  • 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. – Floris Jan 08 '15 at 07:12
  • @Floris, I've amended my answer accordingly. Since the keys are indistinguishable and no one is watching does it matter what the warden said. – Jodrell Jan 08 '15 at 08:37
9

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.

Callidus
  • 3,064
  • 1
  • 16
  • 16
9

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.

Trisped
  • 199
  • 3
  • Good answer. Clearly the fastest way and appears to be completely within the rules. – NotMe Jan 08 '15 at 18:02
  • 1
    I would argue that the placing of the key into the grid constitutes communication and it thus against the rules. – Jack Aidley Jan 09 '15 at 16:05
  • 1
    @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. – Trisped Jan 09 '15 at 17:44
  • 3
    @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. – Jack Aidley Jan 09 '15 at 18:23
  • @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. – Trisped Jan 09 '15 at 21:28
  • @Trisped: Leaving a key is explicitly allowed so it's the exception, using the placement of the key to explicitly communicate information is dodging the other clause. But I think we'll just have to agree to disagree on this one; others can draw their own conclusions. – Jack Aidley Jan 10 '15 at 08:51
  • @JackAidley I still think you are missing the fact that the prisoner is allowed to place the keys in there possession in someone else's cell (with no additional constraints or restrictions). I also noticed that you did not raise this concern with the answer from Callidus which also uses drop locations. If you want, you could ask Meelo to directly address your concern, but as I have already stated, the rules are sufficiently clear that it is the prisoner's responsibility to put it in the cell and there is no restriction on where in the cell the key can be placed. – Trisped Jan 12 '15 at 20:51
  • @Trisped: my objection equally applies to Callidus's solution, for the record. Yours was just more explicit. – Jack Aidley Jan 12 '15 at 22:20
  • I like your answer. Very similar to what I came up with. Mine used the position of the key in a 5x2 grid to indicate who had the key originally, and the "spin" of they key to indicate who has their key. "Spin" was based on clock hand locations. But your 10x10 seems easier to decode and harder to get wrong.... is this key pointing to 3 or 4 could be a problem in mine. – kmort Jan 14 '15 at 18:41
5

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.

Josh
  • 408
  • 3
  • 8
2

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.

aslum
  • 168
  • 1
  • 8
  • 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... – bolov Jan 07 '15 at 20:35
2

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.

Jason
  • 342
  • 1
  • 7
  • 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! –  Jan 12 '15 at 07:44
  • 1
    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. – Jason Jan 12 '15 at 15:45
0

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…

Dr_Olaf
  • 9
  • 1
  • 8
    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. – Milo Brandt Jan 07 '15 at 22:21