Yellow,Green,Red,Blue

[wolfgang]

An unknown number of prisoners( more than 14)were told a day before their execution, that they are going to be blind folded, and a colored paper(either.. yellow,green,red or blue) will be glued on forehead of each one of them( no one can see his own paper), then they should inter a big hall one by one to make 4 raws in this order( Yellow,Green,Red,Blue)i.e. a raw of Yallows, a raw of Greens etc.,each one will be unfolded when he inters the hall.No one of them is allowed to arrenge the others,each one should himslf choose where to stay, once he did,he can not change his place( only the first 2 prisoners can change their minds only once).Any kind of comunication between them is not allowed. If any one of them stands in a wrong raw, all of them will die!

All colores were used.

They should make a plane which saves all of them, can you help them?

[Rainman]

They assign values to each color: yellow = 0, green = 1, red = 2, blue = 3. The first prisoner adds the values of all the other prisoners' hats (modulo 4), then finds the corresponding color to that number and stands in that row. By doing this, everyone else will know the color of their own hat. Now the second prisoner does the same thing as the first one did. This tells the first prisoner the color of his/her hat. Then the first two prisoners change their minds if necessary, moving to the right row. And everyone else can move to the right row as well.

[plasmid]

They assign values to each color: yellow = 0, green = 1, red = 2, blue = 3. The first prisoner adds the values of all the other prisoners' hats (modulo 4), then finds the corresponding color to that number and stands in that row. By doing this, everyone else will know the color of their own hat. Now the second prisoner does the same thing as the first one did. This tells the first prisoner the color of his/her hat. Then the first two prisoners change their minds if necessary, moving to the right row. And everyone else can move to the right row as well.

I think the problem's set up in such a way that you can't use that strategy. The people are blindfolded until they enter the room. So the first person won't see anyone's color, the second person will only see the first person's color, etc.

Just for clarification, are there set positions where each row should form? In other words, should we treat this as if there are four rows of seats and all of the yellows must sit in the first row and all the greens in the second row etc.? Or instead can they form rows wherever they want, so if the first person to enter is yellow he can he stand anywhere in the room as long as all the other colors stand somewhere behind him?

[Pankaj Varma]

The suggested solution assumes that their are equal number of each color slip and the each person, when he enters can see every other forehead and count the color papers glued there. We need a more innovative solution, I guess.

[Prime]

I don't see the OP requiring each prisoner to assume his position before the next one enters the room. So why should we be adding such a restriction?

On the other hand, the OP never specified that the place for each row has been marked with like colored chairs, tile, or in any other way. Thus we must not assume that it has.

Given the above, Rainman's method needs just a slight modification.

How about, after entering the hall, they just hang out there and see what the first two guys do. Then the first prisoner just stands where he is, while the second stands on his left if the first one has a yellow piece of paper, in front for green, on the right for red, and behind for blue.

After that, the first inmate calculates modulus just like Rainman suggested and changes his position to be on the left, front, right, or rear of the the second condemned man for 0, 1, 2, and 3 respectively. Thereafter each man knows his color. Those with the same color as the first convict join him to form a row. The other criminals form their rows as appropriate in relation to that row. When all settled, the second contestant can change his position.

As for the blindfold, it is kept on until each captive enters the hall to prevent them from seeing the color when it is placed upon their heads and thereafter to hinder them from checking the same in the mirror of the dressing room.

[TimeSpaceLightForce]

Color Rows
Y _ _ _ _ _ _ _
G _ _ _ _ _ _ _
R _ _ _ _ _ _ _
B _ _ _ _ _ _ _

position
2
1
3


door
4
5
6
7
8
9
10
11
12
13
14
.
.
L

Plan: using 4-way path
Y G R B
|o o| o/ \o
|o o| /o o\

set-up stage:
1 enter and face the door
2 enter, walk behind 1 and face the door
3 enter, pass 1& 2 ( 1 of 4 ways) according to color of 1,
then stands behind 2 and face the door ..so 1 knew his own color
1 pass 2&3 (1 of 4 ways) according to color of 2,
then stands behind 3 and face the door.. so 2 knew his own color
2 pass 3&1 (1 of 4 ways) according to color of 3,
then stands behind 1 and face the door ..so 3 knew his own color


sitting down stage:
4 enter , time for 3 to sit down in color row ,
pass 1 & 2 (1 of 4 ways) according to color of 4
Now 4 knew his own color, stand in front of 1 facing door and waits for 5..

5 enter , time for 4 to sit down in color row ,
pass 1 & 2 (1 of 4 ways) according to color of 5
Now 5 knew his own color, stand in front of 1 facing door and waits for 6..

..goes on until "Last" prisoner has nothing to wait on, but also now knew his color,
just sit down. Finally, 1 & 2 sit down in color row .

[wolfgang]

They assign values to each color: yellow = 0, green = 1, red = 2, blue = 3. The first prisoner adds the values of all the other prisoners' hats (modulo 4), then finds the corresponding color to that number and stands in that row. By doing this, everyone else will know the color of their own hat. Now the second prisoner does the same thing as the first one did. This tells the first prisoner the color of his/her hat. Then the first two prisoners change their minds if necessary, moving to the right row. And everyone else can move to the right row as well.

I think the problem's set up in such a way that you can't use that strategy. The people are blindfolded until they enter the room. So the first person won't see anyone's color, the second person will only see the first person's color, etc.

Just for clarification, are there set positions where each row should form? In other words, should we treat this as if there are four rows of seats and all of the yellows must sit in the first row and all the greens in the second row etc.? Or instead can they form rows wherever they want, so if the first person to enter is yellow he can he stand anywhere in the room as long as all the other colors stand somewhere behind him?

They can form raws whenever they want

[wolfgang]

The suggested solution assumes that their are equal number of each color slip and the each person, when he enters can see every other forehead and count the color papers glued there. We need a more innovative solution, I guess.

The colors are not equal

[wolfgang]

Color Rows

Y _ _ _ _ _ _ _

G _ _ _ _ _ _ _

R _ _ _ _ _ _ _

B _ _ _ _ _ _ _

position

2

1

3

door

4

5

6

7

8

9

10

11

12

13

14

.

.

L

Plan: using 4-way path

Y G R B

|o o| o/ \o

|o o| /o o\

set-up stage:

1 enter and face the door

2 enter, walk behind 1 and face the door

3 enter, pass 1& 2 ( 1 of 4 ways) according to color of 1,

then stands behind 2 and face the door ..so 1 knew his own color

1 pass 2&3 (1 of 4 ways) according to color of 2,

then stands behind 3 and face the door.. so 2 knew his own color

2 pass 3&1 (1 of 4 ways) according to color of 3,

then stands behind 1 and face the door ..so 3 knew his own color

sitting down stage:

4 enter , time for 3 to sit down in color row ,

pass 1 & 2 (1 of 4 ways) according to color of 4

Now 4 knew his own color, stand in front of 1 facing door and waits for 5..

5 enter , time for 4 to sit down in color row ,

pass 1 & 2 (1 of 4 ways) according to color of 5

Now 5 knew his own color, stand in front of 1 facing door and waits for 6..

..goes on until "Last" prisoner has nothing to wait on, but also now knew his color,

just sit down. Finally, 1 & 2 sit down in color row .

I said in the OP",each one should himslf choose where to stay, once he did,he can not change his place".and with this method each one stays infront of 1 making a raw,so can not change his place.

[bonanova]

This is a challenge.

A two-color version requires and permits movement after taking one's position.

So I don't think it provides useful guidance for this case

The first two stand next to each other.

The third and subsequent persons inserts himself between differing colors, if there are any.

This requires movement of previous persons.

if all previous persons have the same colors, he takes an end position.

However, this results in a single line - just with the colors segregated.

In every way, the present puzzle is more demanding.

Great puzzle.

Eager to see the solution.

[Prime]

This is a challenge.

A two-color version requires and permits movement after taking one's position.

So I don't think it provides useful guidance for this case

The first two stand next to each other.

The third and subsequent persons inserts himself between differing colors, if there are any.

This requires movement of previous persons.

if all previous persons have the same colors, he takes an end position.

However, this results in a single line - just with the colors segregated.

In every way, the present puzzle is more demanding.

Great puzzle.

Eager to see the solution.

They assign values to each color: yellow = 0, green = 1, red = 2, blue = 3. The first prisoner adds the values of all the other prisoners' hats (modulo 4), then finds the corresponding color to that number and stands in that row. By doing this, everyone else will know the color of their own hat. Now the second prisoner does the same thing as the first one did. This tells the first prisoner the color of his/her hat. Then the first two prisoners change their minds if necessary, moving to the right row. And everyone else can move to the right row as well.

I don't see the OP requiring each prisoner to assume his position before the next one enters the room. So why should we be adding such a restriction?

On the other hand, the OP never specified that the place for each row has been marked with like colored chairs, tile, or in any other way. Thus we must not assume that it has.

Given the above, Rainman's method needs just a slight modification.

How about, after entering the hall, they just hang out there and see what the first two guys do. Then the first prisoner just stands where he is, while the second stands on his left if the first one has a yellow piece of paper, in front for green, on the right for red, and behind for blue.

After that, the first inmate calculates modulus just like Rainman suggested and changes his position to be on the left, front, right, or rear of the the second condemned man for 0, 1, 2, and 3 respectively. Thereafter each man knows his color. Those with the same color as the first convict join him to form a row. The other criminals form their rows as appropriate in relation to that row. When all settled, the second contestant can change his position.

As for the blindfold, it is kept on until each captive enters the hall to prevent them from seeing the color when it is placed upon their heads and thereafter to hinder them from checking the same in the mirror of the dressing room.

Hasn't Rainman already solved the puzzle? With that small modification I added, so that his solution does not rely on the preset place where to form rows.

[TimeSpaceLightForce]

Plan: NEWS
North=Y East=G West=R South=B
Color Rows
Y _ _ _ _ _ _ _
G _ _ _ _ _ _ _
R _ _ _ _ _ _ _
B _ _ _ _ _ _ _

1 enters stand in front of door "stationary"
2 enters, 1 face (NEWS) according to color of 2,
2 knew his own color, stands on his color row facing
(NEWS) according to color of 1,1knew his own color.

3 enters, 1 face (NEWS) according to color of 3,
3 knew his own color, stands on his color row
4 enters, 1 face (NEWS) according to color of 4,
4 knew his own color, stands on his color row

..goes on until last prisoner then 1 stands on his color rows

Note: 1 reset initial position as the prisoners walks their rows

hey WG this is a nice puzzle for my friends

[plasmid]

Hasn't Rainman already solved the puzzle? With that small modification I added, so that his solution does not rely on the preset place where to form rows.

I think so, now that Wolfgang clarified that people don't have to take their positions before the next person walks in.

Edit: unless he meant to say "where-ever" instead of "when-ever" in response to my question

But that doesn't generally seem to prevent people from answering.

Maybe Wolfgang will come by to mark it as answered.

Edited January 15, 2013 by plasmid

[bonanova]

To me it seems that 'Entering singly and not changing one's position once taken" are conditions with no effect, if "hanging out" is permitted. What relevance to the solution can that guidance have, other than to prohibit that option? Yet that is what adds the difficulty that I see here.

If language issues have made the point debatable, Wolfgang will have to clarify.

[Prime]

To me it seems that 'Entering singly and not changing one's position once taken" are conditions with no effect, if "hanging out" is permitted. What relevance to the solution can that guidance have, other than to prohibit that option? Yet that is what adds the difficulty that I see here.

If language issues have made the point debatable, Wolfgang will have to clarify.

I am at loss about the purpose of "Entering singly". "Not changing one's position once taken" seems to be a reasonable, good, and severe limitation upon those criminals, indeed.

Conversely, if OP requires each conman to take his place in the formation before the next inmate enters the hall, then I cannot imagine what method could possibly exist for the condemned men? After all, the rows would start forming without any knowledge of the color on the forehead of the next culprit to enter...

[wolfgang]

Plan: NEWS

North=Y East=G West=R South=B

Color Rows

Y _ _ _ _ _ _ _

G _ _ _ _ _ _ _

R _ _ _ _ _ _ _

B _ _ _ _ _ _ _

1 enters stand in front of door "stationary"

2 enters, 1 face (NEWS) according to color of 2,

2 knew his own color, stands on his color row facing

(NEWS) according to color of 1,1knew his own color.

3 enters, 1 face (NEWS) according to color of 3,

3 knew his own color, stands on his color row

4 enters, 1 face (NEWS) according to color of 4,

4 knew his own color, stands on his color row

..goes on until last prisoner then 1 stands on his color rows

Note: 1 reset initial position as the prisoners walks their rows

hey WG this is a nice puzzle for my friends

According to your method(NEWS),seems as if the first prisoner is giving a hint to the others,which is actually not allowed...see the roles in OP

[wolfgang]

To me it seems that 'Entering singly and not changing one's position once taken" are conditions with no effect, if "hanging out" is permitted. What relevance to the solution can that guidance have, other than to prohibit that option? Yet that is what adds the difficulty that I see here.

If language issues have made the point debatable, Wolfgang will have to clarify.

I am at loss about the purpose of "Entering singly". "Not changing one's position once taken" seems to be a reasonable, good, and severe limitation upon those criminals, indeed.

Conversely, if OP requires each conman to take his place in the formation before the next inmate enters the hall, then I cannot imagine what method could possibly exist for the condemned men? After all, the rows would start forming without any knowledge of the color on the forehead of the next culprit to enter...

Yes, each one should choose his place where to belong,once he did, he is not allowed to change his mind.(Except the first two ...see OP)

[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?

[wolfgang]

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.

[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.

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

[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.

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.

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

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]

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 January 18, 2013 by wolfgang

[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

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 January 18, 2013 by araver