57 replies to this topic

[bonanova]

Wolfgang, I think the point that asks for clarification is this:
Must each prisoner wait, outside the room and blindfolded, until previous prisoners have taken their positions?

Yes...thats right....he should wait until the previous prisoner is standing in his raw and took his position. 

Spoiler for in this case...

When 20th prisoner enters the hall and sees 4 neat rows he has no idea, which row to join. The formation cannot give him any clues, since his predecessors could not have known what color he would bear. The only possibility I see is to form crooked rows where each man could make a partial turn in his chosen spot. ... y y y ... g g g................x (newcomer)....r r r ... b b b After the newcomer assumes his positon in the middle, the men in the row of his color turn a little, so that he becomes a part of the crooked row and knows his color. I am not sure, the geometry of such formation would endure. Also, the warden might object...

Nice approach.
I agree tho that the warden might object.
Also, wouldn't the nineteenth prisoner also need to execute this [seemingly one-time-only] ploy?

[Prime]

 

 

 

Wolfgang, I think the point that asks for clarification is this:
Must each prisoner wait, outside the room and blindfolded, until previous prisoners have taken their positions?

Yes...thats right....he should wait until the previous prisoner is standing in his raw and took his position. 

Spoiler for in this case...

When 20th prisoner enters the hall and sees 4 neat rows he has no idea, which row to join. The formation cannot give him any clues, since his predecessors could not have known what color he would bear. The only possibility I see is to form crooked rows where each man could make a partial turn in his chosen spot. ... y y y ... g g g................x (newcomer)....r r r ... b b b After the newcomer assumes his positon in the middle, the men in the row of his color turn a little, so that he becomes a part of the crooked row and knows his color. I am not sure, the geometry of such formation would endure. Also, the warden might object...

Nice approach.
I agree tho that the warden might object.
Also, wouldn't the nineteenth prisoner also need to execute this [seemingly one-time-only] ploy?

 

I didn't mean that as one-time-only ploy

Spoiler for how else?

Every time new man joins a row, others in that row turn a little to accomodate new bend.
Since the criminals must form their rows without any knowledge of the colors to come, their formation cannot offer any clues to each newcomer. Only after each new arrival takes his place, the like colored crooks could start fidgetting, thus letting the newcomer know where he really belongs.

Such solution must fail geometrically. And it would aggravate the warden.

I say, let them get executed.

[CaptainEd]

In addition to being apparently impossible, this puzzle has a number of details we haven't used yet:

* there is an "unknown" number of prisoners.

* the unknown number is greater than 14

* the prisoner can't see anything until he (alone) arrives in the room, at which point he is "unfolded", presumably now able to see the earlier arrivals. (From the standpoint of this puzzle, why bother? he can see the other rows, or at least where they are supposed to be, but he doesn't know what color he is. Why bother to let him see where the rows are?)

* the prisoners can arrange a plan beforehand.

 

So, I'm wondering, in the spirit of the slight cheating that various solutions have proposed, what other kind of cheating might be acceptable to Wolfgang and the Warden.

 

Do we imagine that the prisoners themselves get to arrange the order in which they enter the room? (How would that help? I dunno...)

Notice that having the "like colored prisoners fidget" has the flaw of annoying the warden, but it also has the flaw that it can't be sure of working for the first few prisoners, as not all the rows will be populated at first.

We can see how the first two prisoners can arrange themselves so that all four rows' locations are unambiguously visible. But, short of opening and closing their eyes to encode the next arrival's color, I don't see how to cheat surreptitiously enough to get it past Warden Wolfgang.

[CaptainEd]

Spoiler for Glad we had this little cheat..I mean, chat

OK, here is my cheat: once the first two prisoners have established the locations for all four rows, each prisoner in turn comes in, is unblindfolded, but still unable to look up at his own colored paper. The new prisoner (N) walks up to the nearest prisoner (P) and observes his own reflection in P's eyeball. This should be sufficient to identify the color on the paper. Then N walks to the correct row and stands.

 

"justifications"

* no prisoner has communicated with any other prisoner after the first two have established the rows' locations--N simply uses P as a mirror--P sent no message

* each prisoner (after the first two) commits to his position once and does not change it.

* each prisoner enters the room after all prior prisoners have commited their positions.

[wolfgang]

I can add something which may help you... The raws may face the door or the opposit direction!

Edited by wolfgang, 18 January 2013 - 07:21 PM.

[araver]

So far I'm at a loss here .. just thinking about the 2-color-version of the problem makes my head spin for a second

 

Spoiler for ...

Assuming there were only Blue and Red (B&R) colors and 3 persons 1,2,3 ... it could work. As far as I understand the puzzle. 
Ignore the all colors are used for one sec and / or assume that only one of 1&2 is allowed to move.
And also assume that all of them face the door to see the newcomers (otherwise knowledge is potentially lost)
 
1 enters the hall, takes a position.
 
2 enters the hall, looks at 1's color and takes a position behind 1. 1 also sees 2's color. Each still does not know own color.
 
3 enters the hall, looks at 1 and 2, he sees their color and they see his.
 
1 and 2 are either the same color (RR, BB) or different (BR). 
* If same, 3 takes a position besides them forming another row.
* If different he stands behind them.
 
Now, since 1 and 2 know each other's colors, 3 basically transmits one bit (1/0) of info to both of them. Depending on his positioning, this tells them if their color is opposite or same.
 
If he gets beside them:
* (assume the all-colors-are-used rule) no one moves game over-win (forming either BR or RB rows depending where the door is).
* (not assuming the all-colors-are-used rule) if their color matches 3 they both move behind him, else both stay where they are (no force moves assumed) - game-over win
 
If he gets behind them, exactly one of them (1&2) needs to move away from 3 to form a new row and exactly one of them will know he has to move since they know their color and 3's - game-over win
 
G(2,3,2) and GAC(2,3,2) are thus winnable where G[AC] (x,y,z) instance of the (deadly) game where x prisoners are painted y colors, at most z people can change their initial place, and AC = All Colors used).
Also GAC(2,3,1) is winnable since if all colors are used, in the case where 1&2 have the same color, the rows are formed without any of them needing to move.
 
The OP asks for GAC(N,4,2) where N>=14.
  
Above strategy seems to be sub-optimal as the placement of the first 2 is static therefore not transmitting any bit of info. Granted, there may be a way to improve this a bigger version of the game.
 
Setting aside the requirement of getting into a final position for a second, an easier problem would be if at the end of all this moving, each would know everyone else's color. The arrangement guarantees that this knowledge is gained if rows are correct in the end if both color-given order and reverse color-given order rows allow this and x>=2. Each prisoner would be able to see his own relative position and deduce his own color based on the row he is in and the other rows.
Also knowing everyone's color is equivalent to be able to color ID self (color IDing is shorter than color guessing even if the arrangement is wrong - since they see those before upon entering and all who enter after. 
 
So, instance G[AC](x,y,z) winnable implies instance C[AC](x,y,z) winnable (not sure if movement plays a definite role but it may transmit information regarding colors so we can't discard it). And I kinda think even C[AC](N,4,2) for N>5 is not winnable no matter what strategy they adopt (unless there's a trick /outside of the box thinking that I missed when trying to formalize the game instance / problem).
 
Notice that each move after the 2nd prisoner chooses his initial position transmits a bit of info to each player increasing the knowledge gain.
 
For the color ID problem (for just 2 colors) - just knowing each other's color - the knowledge can be thought of as a binary NxN matrix where 1 stands for "I know your role" and 0 stands for "no knowledge". And it's not symmetrical.
* Matrix starts empty.
* The n-th person entering adds +(n-1) bits of info for those before him (impossible to know before he entered since all before him we're blindfolded/did not see him)
* upon seeing the others adds +(n-1) bits of info to his own knowledge (impossible to know before he entered as he was blindfolded as well).
* Each positioning / movement of this n-th person may directly transmit one or more bits of info to the others YET no bit of info for this n-th person since no one is allowed to signal him anything.
* Indirectly, he may get some info (e.g. in the AC game) if either the placement of the n-1 persons before or the colors of those before him allow him to restrict his color-choice to a single one.

So, to fill the matrix from 0 to N*N in N+2 moves, the strategy needs to increase the knowledge gain at some point. Sum(i-1+i-1) only guarantees filling one half (minus the diagonal) of the matrix for the first n players entering (dumb/no strategy).
I don't see extra moves adding that much.
To double the knowledge gain, one needs a speed-up factor x2 for the placement strategy + extra moves.
Granted, near the end of the game, as placement choices (or color-choices in case of AC game) become restricted, a given strategy may speed up the knowledge gain (again, not specifically caring about ending placement here, so we're even allowing for a different end-arrangement plan), but not by much IMHO. (I might get fooled by the numbers here).
 
Adding more colors makes for an even weirder matrix. Assume 4-colors. Each player needs three bits of information (not color X, not color Y, not color Z) before he can finally color ID self. Since 4=2^2, granted two bits of info  might narrow it down and speed it up (binary-search pattern). But again, extra dimensions (extra colors) make the knowledge deficit several times bigger.
 
And lastly it's hard to come up with a constant/better performing strategy when X is increased. Each new added player adds 1 unknown (as he chooses his spot) while the number of extra moves is limited - so each of these moves need to cover up for this unknown as well.
 
Sorry, long post.
I have no idea how this might be solvable (then again I did said so in the spoiler title ).

I'm also not an optimist, and when I actually manage to prove something I usually find myself proving something is not possible, but that's   

 

Just thought I'd share my thoughts - haven't done this exercise in a very long time

EDIT: Spoiler titles don't like me.

Edited by araver, 19 January 2013 - 12:19 AM.

[bonanova]

I can add something which may help you... The raws may face the door or the opposit direction!

 

Continuing with the community solve approach, can we clarify:

1. Must all the persons in a particular row face the same direction?


2. If prisoners in say the Yellow row can face in differing directions does that constitute [illegal] communication?


3. Can the first two prisoners choose the time that they [legally] alter their position, at any time up to the last prisoner takes his place?

[bonanova]

Spoiler for araver may have hit on the key

Borrowing from araver's last post, let me suggest a framework for solving the four-color case.

• P1 enters and stands facing the door.
  No generality is lost - he has no information to act on.
   
  
• P2 enters and stands
  [in front/back of, to the left/right of] P1
  [facing toward/away from the door]
  based on the color of P1.
  Enough possibilities [and more] to tell P1 his color.
   
  
• P3 enters and stands
  [in line with/beside P1 and P2]
  [closer/farther from the door, or left/right or P1 and P2, as appropriate]
  [facing the same/opposite direction as P1]
  based on the colors and positions of P1 and P2.
   
  
• P1 then
  [does/does not alter the direction he is facing]
  [does/does not alter his alignment with P2 and P3]
  based on the colors of P2 and P3.
   
  
• P4 enters and stands so that he
  [forms a square/ell/tee together with P1 P2 and P3]
  [faces same/opposite direction as P1]
  based on the positions and colors of P1, P2 and P3.
   
  
• P2 then sets
  [does/does not alters his position and/or orientation]
  based on the colors and positions of P1, P3 and P4.
   
  
• No one in the room can move after this point.
  
  The others must know where to stand and which direction to face
  [somehow, haven't figured that part out yet]
  based on what they see when they enter.

That's a framework.
Are there enough permutations of the above variables to spell out to the next to enter what he needs to know? 
Let's assume the puzzle is solvable [see my sig] and find a way to signal the needed information forward in each case.

What role does 14 play in all of this?

Cap'n, I'm with you on that ... no clue yet.

As I said a few posts back, this is one heck of a puzzle.

 
Hey araver, LTNS!

[bonanova]

Another point to clarify.

 

Must the rows be parallel, and in particular Y-G-R-B order?

OP seems to suggest this condition.

 

+-------------------------+

|                         |

|      Y Y Y Y Y . . .    |

|      G G G . . . . .    |

Door   R R R R R R . .    |

|      B B B B B . . .    |

|                         |

|                         |

+-------------------------+

 

Or could the rows e.g. all start at the middle of the room, and grow outward toward the four walls, in any sequence?

Say Yellow to the north, Green to the south, Red to the east and Blue to the west?

[wolfgang]

 

I can add something which may help you... The raws may face the door or the opposit direction!

 

Continuing with the community solve approach, can we clarify:

1. Must all the persons in a particular row face the same direction?
2. 
   
3. If prisoners in say the Yellow row can face in differing directions does that constitute [illegal] communication?
4. 
   
5. Can the first two prisoners choose the time that they [legally] alter their position, at any time up to the last prisoner takes his place?
6. 
   

 

During making raws...some of them  can be..back to back (in any raw)...but by reaching the last prisoner,they all shoud be at the same direction