Prisoners sorting cards - this puzzle is not for the faint of heart

[bonanova]

The warden is at it again. The entire prison population will be set free if the inmates can achieve a simple result. They must stack three cards, an Ace, King and Queen, on a table, in that order, with the Ace on top.

Alone and in a closed room, the warden begins the process by placing the three cards face up on a desk in some or all of three bins, appropriately marked Left, Middle, and Right. If they all occupy a single bin, only the top card is visible. If they occupy only two of the bins, then only two cards are visible, and it is impossible to tell which of the two visible cards conceals the third. Of course if they are all in separate bins, all three are visible. How the cards are initially laid out is totally up to the warden, but for the purposes of this puzzle we may assume the placement is random.

At 8:00am on the fateful day, a prisoner chosen at random enters the room and moves one of the visible cards from its bin to a different (possibly empty) bin. That is, from the top of one stack to the top of another (possibly empty) stack. The prisoner then leaves the room and is led back to his cell. He does not communicate in any way with the other inmates. Then at 9:00am, and at one-hour intervals thereafter, a second, third, etc., randomly chosen prisoner enters the room and again moves a single card from the top of one pile to the top of another. A prison guard inspects the cards after each move and informs the warden if at any time the three cards become stacked in a single bin in the desired order: Ace, King, Queen, with Ace on top.

 

The cards must be correctly stacked by the time the 5:00pm prisoner leaves the room, or before, for the prisoners to be released. They are all executed otherwise.

The prisoners are not permitted to work out a strategy beforehand. In fact, the prisoners do not know what they are expected to do until they enter the room. We could say that prisoners enter the room, read the above description of the problem, make their move, and then leave.

What are the prisoners' chances?

We can assume they are smart. Smart enough to be Brain Denizens.

[Yoruichi-san]

 

I had done the same analysis as Barc and concluded that it's probably the correct answer because

Even if the warden were to give them the worst-case scenario of starting off with one pile of three cards, the first prisoner would move one card off the pile, and the following 7 prisoners would each get a 50/50 chance of making three separate stacks of cards by randomly choosing one of the two visible cards to move to the empty bin. The odds that those seven would all fail to separate the cards into three stacks would be 0.5

⁷, meaning that the prisoners have a >99% chance of being released even in that worst case scenario.

As for coming up with a different strategy

I don't think it's possible with the points given in the previous post. My reasoning hinges on points 4 and 6, that there is some "correct" move for any arrangement of cards that is independent of the time of day, plus my own assertion that the amount of information that each prisoner sees when he enters the room can be expressed as an unordered set of which cards are visible. I think it's valid to throw out the positional information of which bin (left / middle / right) is holding each card because, for any solution that the prisoners can arrive at without discussion before starting that uses that information (for example, saying "if there's an empty bin then move the card to the left of the empty bin into that empty bin"), there is an equally valid solution that a prisoner could arrive at that uses the opposite directionality (moving the card to the right of the empty bin instead of the one to the left). If there's no way for the prisoners to agree on that arbitrary choice of directionality by discussing a strategy beforehand, then there's no way to be sure they'll all make the same arbitrary choice when determining their own strategy.

Now suppose you have an optimal strategy where the correct move does not depend on the time of day and is completely deterministic based on which cards are visible. A prisoner walks in and sees King and Queen showing. Whichever of the King or Queen he selects to move, if he moves it to an empty bin, then there's a 1/2 chance he will move the lone card to a different bin and therefore not change the state of the problem. Because moves are deterministic based on the visible state, every other prisoner will make the same move, and they will all die. The optimal solution must involve moving one of those cards to an empty bin -- if the optimal solution involved moving one card onto another, then there's a 50/50 chance that move would create a pile of three cards, and then the only possible subsequent move would be to move the top card back off of the pile to go back to the initial state, and you would enter an endless cycle because the moves are deterministic and independent of time of day.

That said, I bet bonanova's already thought of that and has a solution that still works with those rules despite my argument that attempts to show it's impossible.

 

plasmid gives me too much credit, so I'm going to out myself now and state that this is adapted from genius puzzler who will be credited when the solution is found. This is done to keep Google out of the competition, not that anyone would do that.   Further, I worked on this puzzle until I convinced myself that I could not solve it before looking at the solution. So you guys are the heroes here, not me.

 

Let me add:

1. plasmid's first paragraph makes me wonder. His mirror point seems valid, and it's possible

   that my adaptation opened a loophole. If so, a slight modification of the OP avoids it:

   The first prisoner solves the puzzle and writes an algorithm on a piece of paper that he leaves in the room.

   In that case, and if there are in fact multiple solutions, then Prisoner 1 selects one that they all will use.

   In that case, any algorithm that gives AKQ will be a correct solution to the puzzle.

   That is, it won't be required that every prisoner would have found the same algorithm (if there are several) and used it.

   Or we could say the prisoners are allowed to discuss a strategy beforehand.

    

2. I can provide a helpful clue, one that still leaves a very hard problem, if desired.

 

 

Maybe I'm missing something, but I think this might oversimplify the problem.  If I can select a specific direction, I think I can get to AKQ in 6 moves from any initial formation, regardless of the time.

1.  If you see only and A and a K, place the A on top of the K.

2.  If you see all three cards, place the K on top of the Q.

3.  If you see only a single stack, move the top card to the left of the stack.  (Consider the three positions to 'wrap around')

4.  If you seen two cards that are not A and K, move the card on the right to the empty space on the left (of the pair, keeping the idea of wrapping around).

 

With this strategy a starting single stack can be solved in 4 moves, first making a stack of 2 cards on the right and a single card on the left, then making three stacks of single cards.  Most starting double stacks can be solved in 4 moves or less, since even if the original formation had 2 cards stacked on the left instead of the right, moving the rightmost card to the left of the stack would reset the formation to having 2 cards stacked on the right. And of course three stacks is solved in 2.  The formation that would take 6 moves is _ K A/Q -> _ A/K Q -> Q A/K _ -> Q K A -> K/Q _ A -> A/K/Q 

 

Which makes me think there is probably a directionally independent solution of some form of the problem, but when I try the original problem without directions, I run into plasmid's issue.

[Barcallica]

Can a prisoner choose not to move anything?

 

also do they know what time it is?

Edited August 14, 2014 by Barcallica

[plasmid]

Must a prisoner commit to moving a card to a particular bin before seeing what's underneath it? Or may he change his mind and pick a different card, or change the chosen card's destination, after seeing what's underneath the card he initially picks up?

[Barcallica]

may he change his mind and pick a different card, or change the chosen card's destination, after seeing what's underneath the card he initially picks up?

 

if he may, can he put it back?

[bonanova]

Good questions.

The prisoner must make a move. Wait. No, he doesn't. But skipping a move only makes it harder to finish by 5:00pm.
The move is based solely on visible cards.
The move may not be reconsidered based on information gained by making the move.

0. Enter the room.
1. Look at the (visible) cards.
2. Decide which visible card to move and where to move it.
3. Make the move.
4. Leave the room.

Re time of day.
I introduced time of day only to limit the total number of moves.
But you may assume the prisoner has a functioning timepiece.

Gratuitous fact:

Left, Middle and Right are labels whose only function is to enable a description of what a prisoner might see and what move he should then make.

[Quantum.Mechanic]

I just read an equivalent puzzle in a puzzle book, so I'll sit this one out...

[Barcallica]

I am stuck.

 

8a.m to 5p.m there will be 10 prisoners participating at most.

Upon reading the rules, 10th man must deduce that his action is to put ace on a king, otherwise they lose.
10th Man's duty is to put Ace on King/Queen

Upon reading the rules, 9th man deduces what 10th man's job is and will know that his job is to put King on Queen so to make it possible for 10 man to make final move.
9th Man's duty is to put King on Queen

Upon reading rules 1-8th Men should deduce their job is to spread the cards (no 2 cards in the same bin). For example 8th through 1st prisoner should not make a move if cards are already spread out.

I know they can't strategize but I am assuming they will logically reach above conclusion and act accordingly.

However I couldn't find out a logical moves for 8th or 1st prisoners if they are seeing e.g. A-K/Q or A-Q/K with zero cooperation.

What am I missing? or am I wrong altogether?

[bonanova]

Nice analysis.

You may have made some assumptions you don't need to make.

Here are some things to consider.

from the OP we can conclude

1. Prisoner 1 might see any possible starting position.

2. A sequence of ten or fewer moves exists between every visibly distinct starting position and AKQ.

3. Every visibly distinct position is encountered by at least one of these sequences.

4. Every visibly distinct position has a correct "next" position, and therefore it has a correct next move.

5. Each prisoner does a complete solution in order to know the move indicated by the position he sees.

6. The correct move is not related to the time of day.

7. The solution is a set of sequences that includes all visibly distinct positions and ends with AKQ.

[plasmid]

I had done the same analysis as Barc and concluded that it's probably the correct answer because

Even if the warden were to give them the worst-case scenario of starting off with one pile of three cards, the first prisoner would move one card off the pile, and the following 7 prisoners would each get a 50/50 chance of making three separate stacks of cards by randomly choosing one of the two visible cards to move to the empty bin. The odds that those seven would all fail to separate the cards into three stacks would be 0.5

⁷, meaning that the prisoners have a >99% chance of being released even in that worst case scenario.

As for coming up with a different strategy

I don't think it's possible with the points given in the previous post. My reasoning hinges on points 4 and 6, that there is some "correct" move for any arrangement of cards that is independent of the time of day, plus my own assertion that the amount of information that each prisoner sees when he enters the room can be expressed as an unordered set of which cards are visible. I think it's valid to throw out the positional information of which bin (left / middle / right) is holding each card because, for any solution that the prisoners can arrive at without discussion before starting that uses that information (for example, saying "if there's an empty bin then move the card to the left of the empty bin into that empty bin"), there is an equally valid solution that a prisoner could arrive at that uses the opposite directionality (moving the card to the right of the empty bin instead of the one to the left). If there's no way for the prisoners to agree on that arbitrary choice of directionality by discussing a strategy beforehand, then there's no way to be sure they'll all make the same arbitrary choice when determining their own strategy.

Now suppose you have an optimal strategy where the correct move does not depend on the time of day and is completely deterministic based on which cards are visible. A prisoner walks in and sees King and Queen showing. Whichever of the King or Queen he selects to move, if he moves it to an empty bin, then there's a 1/2 chance he will move the lone card to a different bin and therefore not change the state of the problem. Because moves are deterministic based on the visible state, every other prisoner will make the same move, and they will all die. The optimal solution must involve moving one of those cards to an empty bin -- if the optimal solution involved moving one card onto another, then there's a 50/50 chance that move would create a pile of three cards, and then the only possible subsequent move would be to move the top card back off of the pile to go back to the initial state, and you would enter an endless cycle because the moves are deterministic and independent of time of day.

That said, I bet bonanova's already thought of that and has a solution that still works with those rules despite my argument that attempts to show it's impossible.

[bonanova]

I had done the same analysis as Barc and concluded that it's probably the correct answer because

Even if the warden were to give them the worst-case scenario of starting off with one pile of three cards, the first prisoner would move one card off the pile, and the following 7 prisoners would each get a 50/50 chance of making three separate stacks of cards by randomly choosing one of the two visible cards to move to the empty bin. The odds that those seven would all fail to separate the cards into three stacks would be 0.5

⁷, meaning that the prisoners have a >99% chance of being released even in that worst case scenario.

As for coming up with a different strategy

I don't think it's possible with the points given in the previous post. My reasoning hinges on points 4 and 6, that there is some "correct" move for any arrangement of cards that is independent of the time of day, plus my own assertion that the amount of information that each prisoner sees when he enters the room can be expressed as an unordered set of which cards are visible. I think it's valid to throw out the positional information of which bin (left / middle / right) is holding each card because, for any solution that the prisoners can arrive at without discussion before starting that uses that information (for example, saying "if there's an empty bin then move the card to the left of the empty bin into that empty bin"), there is an equally valid solution that a prisoner could arrive at that uses the opposite directionality (moving the card to the right of the empty bin instead of the one to the left). If there's no way for the prisoners to agree on that arbitrary choice of directionality by discussing a strategy beforehand, then there's no way to be sure they'll all make the same arbitrary choice when determining their own strategy.

Now suppose you have an optimal strategy where the correct move does not depend on the time of day and is completely deterministic based on which cards are visible. A prisoner walks in and sees King and Queen showing. Whichever of the King or Queen he selects to move, if he moves it to an empty bin, then there's a 1/2 chance he will move the lone card to a different bin and therefore not change the state of the problem. Because moves are deterministic based on the visible state, every other prisoner will make the same move, and they will all die. The optimal solution must involve moving one of those cards to an empty bin -- if the optimal solution involved moving one card onto another, then there's a 50/50 chance that move would create a pile of three cards, and then the only possible subsequent move would be to move the top card back off of the pile to go back to the initial state, and you would enter an endless cycle because the moves are deterministic and independent of time of day.

That said, I bet bonanova's already thought of that and has a solution that still works with those rules despite my argument that attempts to show it's impossible.

 

plasmid gives me too much credit, so I'm going to out myself now and state that this is adapted from genius puzzler who will be credited when the solution is found. This is done to keep Google out of the competition, not that anyone would do that.   Further, I worked on this puzzle until I convinced myself that I could not solve it before looking at the solution. So you guys are the heroes here, not me.

 

Let me add:

1. plasmid's first paragraph makes me wonder. His mirror point seems valid, and it's possible

   that my adaptation opened a loophole. If so, a slight modification of the OP avoids it:

   The first prisoner solves the puzzle and writes an algorithm on a piece of paper that he leaves in the room.

   In that case, and if there are in fact multiple solutions, then Prisoner 1 selects one that they all will use.

   In that case, any algorithm that gives AKQ will be a correct solution to the puzzle.

   That is, it won't be required that every prisoner would have found the same algorithm (if there are several) and used it.

   Or we could say the prisoners are allowed to discuss a strategy beforehand.

    

2. I can provide a helpful clue, one that still leaves a very hard problem, if desired.

[plasmid]

That makes it easy to guarantee release if the prisoners still get to know what time of day they enter the room.

Want to take away their watches so they're all forced to follow the same algorithm without knowing when they've entered?

[Barcallica]

That makes it easy to guarantee release if the prisoners still get to know what time of day they enter the room.

Want to take away their watches so they're all forced to follow the same algorithm without knowing when they've entered?

Or force them to make move.

[bonanova]

Don't see that it matters.

 

The configuration dictates the move, not the time of day.

The solution is not "If it's 3:00 then place the Q on top of the A."

With a random warden, Prisoner 1 might make the winning move.

 

Y-San's post tells the nature of the solution, so let's just pose it that way:

Arrange the configurations into categories of your choice, then give the correct move for each case.

[bonanova]

Y-San, do your steps have a cycle?

 

If left stack is A and K in some order, then doesn't your step 4 just shuttle the Q between center and right?
Or am I misunderstanding Step 4?

 

What would be your moves, starting from say K  A/Q  __ ?

[Yoruichi-san]

Y-San, do your steps have a cycle?

 

If left stack is A and K in some order, then doesn't your step 4 just shuttle the Q between center and right?

Or am I misunderstanding Step 4?

 

What would be your moves, starting from say K  A/Q  __ ?

The idea is to 'splay' the cards into three steps moving from right to left.  With the concept of the positions wrapping around, it simplifies the possible positions greatly.  In those terms, three formations would be equivalent, i.e.  K A/Q _ = _ K A/Q = A/Q _ K with the K considered to be to the left of the A/Q.

 

Hence _ K A/Q -> _ A/K Q -> Q A/K _ -> Q K A -> K/Q _ A -> A/K/Q 

Or equivalently  K A/Q _ -> A/K Q _ -> A/K _ Q*** -> K A Q -> _ A K/Q -> A/K/Q

 

(***note that here the A/K is actually considered to be on the right in terms of the wrapping around)      

[Barcallica]

When I was stuck, I was thinking this would be solution if they could strategize, not as slick as Y-san's but still works. (and it seemed so easy)

 

1-3rd men's job - to pile up the cards in the left bin. (if a card is not in left bin, put that in the left bin, if all are already in left bin, just leave)

4rd man - move 1 card from left bin to center

5th man - move 1 card from left bin to right 

6th man - put k on q

7th man - put a on k.

[Yoruichi-san]

Lol...please don't describe me or anything I do as "slick" .  I'm an engineer, so I tend to be partial towards adjectives that start with 'e', i.e. 'elegant', 'efficient', or 'enigmatic' ;P.

 

It occurs to me that not everyone might intuitively think of directions in terms of connectivity instead of absolute physical position, so it helps conceptually...

 

Instead of thinking of the positions as LMR, think of them as

...LMRLMRLMRLMRLMRLMRLMRLMRLMRLMRLMRLMR...

 

So A/K _ Q becomes

...A/K _ Q A/K _ Q A/K _ Q A/K _ Q A/K _ Q A/K _ Q A/K _ Q...

 

It's a lot easier to see that the A/K is the right stack of the pair.

 

Alternatively, add a rule 0:

0.  Consider the positions to 'wrap around', i.e. that L is connected on the left to R and on the right to M, M is connected on the left to L and on the right to R, and R is connected on the left to M and on the right to L.  Mentally re-map the configuration of stacks so that the empty space(s) are on the left without changing the connectivity.  

 

(I think there's a technical term for it...'homeomorphic transformation', maybe?)

[bonanova]

Marking it solved, but ...

 

Step 4 still confuses me for AK __ Q.

I mean, I see what you do, but not how Step 4 tells you to do it.

 

4. If you see two cards that are not A and K, move the card on the right to the empty space on the left (of the pair, keeping the idea of wrapping around).

 

The card on the right is Q; the empty space is in the middle; what the pair means, idk; and wrapping around doesn't say when or which way.

 

I would get AK  __  Q  ==>  AK  Q  __ , and Step 4 brings that back to AK __ Q which is a cycle

 

For you, Step 4 changes AK __ Q into K A Q. Which suggests (at least for this specific case) this re-wording

 

If you see two cards that are not A and K, and if the empty space is not on the left, then rotate the configuration so that the empty space occupies the left slot.

 

__  Q  AK

 

Then, move the card on the right (A) to the empty space on the left (of the pair???)

 

A  Q  K

 

Then reverse the rotation

 

K  A  Q

 

Does that do it?

[Yoruichi-san]

Sure, revise away...

 

Although I have to respectfully disagree .  I think if you fully embrace the idea of 'wrapping around' no revision is necessary.

 

I.e. The earth 'wraps around'.  Europe is technically both to the west and the east of Asia.  However, if you ask any Asian, they'll tell you Europe is to the west, which is b/c 1) it's closer on the west and 2) it's connected to the west.  

 

"Of the pair" is referring to the pair of cards (since you only see two cards when you walk into the room), which also makes more sense in the previous terms since, in my mind at least, it implies the cards are adjacent. I.e. if you see A_Q and you think of it in terms of ...A_QA_QA_QA_QA_QA_QA_QA_Q..., the "pair" is pretty obvious.  *shrugs*

 

Anyways, what was the original problem?  I feel like based on what you've said, it should have a pirate-game-esque solution, but I'm not seeing it here. I'm very interested in what it might be.

[k-man]

Maybe this wording would be easier to understand (not that it changes anything):

 

4.  If you see two cards that are not A and K, move the card that has an empty space to its right (wrapping around) into that empty space.

[Yoruichi-san]

Works for me .  I still really want to see the original problem though .  Thanks bon-chan .