17
$\begingroup$

Where: Hackanoogie Prison. When: Who cares?

The Master Key Keeper had had a really good day and in a fit of insanity and niceness decided to let all the inmates to go free if they manage to carry out the following task.

"Guys", he calls over the P.A system (it's very informal there on Tuesday mornings) "During the night the Key Keepers were extremely bored and crept into everyone's rooms and painted a red or blue dot on every persons nose".

"We will open the door to the chocolate-fountain room (as it is the largest room in the prison) and everyone must go inside". He paused to take a swig from the ever-smoking ever-present flask by his side. "If the red-dots and the blue-dots successfully manage to sort themselves out and stand on two opposite sides of the room -" he paused for dramatic effect "you will all be let free!".

"Needless to say, you cannot possibly see what is on your, or anyone else's, noses right now because you are currently standing in pitch black darkness. You may discuss a strategy now, but when you enter the room (which will be lit) - No talking, winking, burping or any communication of any kind. Oh! by the way as soon as you take your place - we will mace you (the painless, raspberry flavor type) and you will get blinded!"

"Off you go" he giggles as he falls backwards through window and into the Venus flytrap.

Lo and behold! the inmates manage to complete the task successfully. How did they do it?

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ Welcome to Puzzling, and great first puzzle! Only issue I have with it is that "communication" is fairly ill-defined - what exactly counts as communicating? Wouldn't any form of action be considered communication? $\endgroup$
    – Deusovi ♦
    Commented Feb 9, 2016 at 7:58
  • 1
    $\begingroup$ I think for this question to not be closed as too broad you'll need to precisely lay out what is an acceptable action and what is not. I'm not going to vote to close right now, but "communication" is worryingly vague. $\endgroup$
    – Deusovi ♦
    Commented Feb 9, 2016 at 8:35
  • 2
    $\begingroup$ @Ben I feel like you have accepted an answer because it was closer to the solution which you originally envisaged (QBrute's).. when a better answer actually exists (Pangloss's). Both answers are great and should be upvoted.. but I feel Pangloss's more clearly solves the problem as defined. $\endgroup$
    – Arth
    Commented Feb 9, 2016 at 14:17
  • 1
    $\begingroup$ @Arth agreed. But Pangloss's answer works only if they all go in at the same time and can see everyone else's face before choosing where to stand. QBrute's allows even when they enter one by one and told to take their places. (granted entry type not specified in question... but QBrute's will cover more scenarios) $\endgroup$
    – Ben
    Commented Feb 9, 2016 at 14:25
  • 2
    $\begingroup$ @Ben I'd argue that the separation and order of "everyone must go inside ... manage to sort yourselves out" indicates that everyone is in room to start with. It also appears that once someone has taken their place they are blind, shuffling line positions without any 'communication' once blinded will be tricky and the final separation is less clear. All this works in favour of Pangloss's answer. $\endgroup$
    – Arth
    Commented Feb 9, 2016 at 14:34

9 Answers 9

Reset to default
19
$\begingroup$

Any two prisoners enter the room and stand side by side in the middle of the room. All other prisoners either have to:

- Position themselves on either side of the already positioned prisoners, if they all have the same color.
- Position themselves inbetween two prisoners, that have different colored noses.

After all prisoners are in place, they will be perfectly separated by color.


The trick here is that even though at the end of the day we will have one line of people - all the blues will be on one side and all the reds will be on the other. The 'two opposite sides of the room' doesn't have to be completely separate and wherever the blue and red meet, draw a mental line down the room and they will ,ipso facto, be standing on opposite sides of the room!

Improve this answer
$\endgroup$
14
  • 3
    $\begingroup$ This was exactly my solution! How do they get to opposite sides without someone having to guess though? $\endgroup$
    – Deusovi ♦
    Commented Feb 9, 2016 at 12:06
  • 2
    $\begingroup$ @Ben This solution doesn't work. They won't be on opposite sides of the room - that's why I said there was a 50/50 chance at the end. $\endgroup$
    – Deusovi ♦
    Commented Feb 9, 2016 at 12:10
  • 9
    $\begingroup$ I don't agree. This solution is beautiful, but the result is an arrangement that is only separable by someone else; the inmates are not separated as was requested. $\endgroup$
    – bers
    Commented Feb 9, 2016 at 13:55
  • 5
    $\begingroup$ @Ben: The question specifically said they needed to be separated on opposite sides of the room. Of course I assumed that they needed to be separate! (In any case, I think Pangloss's solution is better.) $\endgroup$
    – Deusovi ♦
    Commented Feb 9, 2016 at 17:28
  • 6
    $\begingroup$ Let's say I'm the last prisoner, and my nose is red...I first take my place in line. The person who entered before me knows the color of their nose now, and so does everyone else (Because they can see where the color change happens). Now I choose an arbitrary side of the room to go to, and everyone else follows suit. EDIT: Also I think this solution is more graceful than Pangloss's, since we don't live in the best of all possible worlds and therefore can't rely on 100s of inmates all counting 100s of other inmates correctly. $\endgroup$
    – progressiveCavemen
    Commented Feb 10, 2016 at 16:36
49
$\begingroup$

The prisoners agree that:

Each prisoner who sees an even number of blue noses goes to a predetermined side of the room (perhaps the side with the door through which they entered). Each prisoner who sees an odd number of blue noses goes to the opposite side of the room.

Each prisoner with a blue nose will:

See either an even or an odd number of blue noses, one fewer than the total of blue noses.

Each prisoner with a red nose will:

See The total number of blue noses, which also will be either even or odd, but not the same as the number that the blue-nosed prisoners see.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ This one is so easy and yet the best anwser for the (unedited) problem. $\endgroup$
    – Wa Kai
    Commented Feb 9, 2016 at 14:12
  • $\begingroup$ How does this work? blues who enter next to each other go to different sides $\endgroup$
    – Bishop
    Commented Feb 9, 2016 at 18:32
  • 3
    $\begingroup$ Right, @Bishop, this solution assumed that all prisoners can see all the others before they take their places. This way, they truly don't communicate any information by their actions. They can even take their places after being blinded. $\endgroup$
    – humn
    Commented Feb 9, 2016 at 19:44
6
$\begingroup$

Everyone will line up in a straight line.

If you don't see two types of people, stand at the end.

Otherwise,

stand in between the two groups.

This way, everyone will know their dot color based on how the next person stands. The last person gets no information about their color, so it's just a 50/50 shot when the two groups walk to the sides of the room.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Very nearly there... but you still have a 50/50 chance? The last part is lateral thinking... $\endgroup$
    – Ben
    Commented Feb 9, 2016 at 8:13
  • 1
    $\begingroup$ @Ben: If the last person is red they move to the north/south side, otherwise they move to the east/west sides? Any answer would be some form of communication. $\endgroup$
    – Deusovi ♦
    Commented Feb 9, 2016 at 8:15
  • $\begingroup$ nope :-). That's the lateral part... $\endgroup$
    – Ben
    Commented Feb 9, 2016 at 8:20
  • $\begingroup$ I'm new here, when do I post my answer? Does an answer always need to be posted? $\endgroup$
    – Ben
    Commented Feb 9, 2016 at 8:28
  • $\begingroup$ @Ben: You don't need to post an answer at all. Generally, if people decide to post their answer they'll wait a couple days before doing it; they'll either accept the closest answer or upvote it and accept their own. $\endgroup$
    – Deusovi ♦
    Commented Feb 9, 2016 at 8:33
5
$\begingroup$

Without looking at any of the answers the strategy is:

All the people who see an even number of blue noses go to section A.
All the people who see an odd number of blue noses go to section B.

This works because:

There are b blue noses.
Those with a blue nose see b-1 blue noses.
Those with a red nose see b blue noses.
So one set sees an even number the other an odd number.
By separating on that criterion they group the red noses together and likewise the blue noses.
Of course they could choose red noses, odd to section A, etc and it'll still work.
The main objective is they all agree on a single strategy.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ nicely explained, same as Pangloss above. This answer only works if everyone goes in to room at same time. The accepted answer works even if led in one-by-one. (i know - it wasn't specified in the question) $\endgroup$
    – Ben
    Commented Feb 9, 2016 at 18:27
3
$\begingroup$

Step 1

One person is chosen to make the first move. If he sees an even number of red noses he goes to the left, if he sees an odd number he goes to the right.

Step 2

Now everyone else counts the number of red noses, excluding the first person (in case he is red). If they agree with his choice (odd or even), they are blue. If not, a red nose is missing, which has to be them self.

Step 3

Depending on the color of the first person, the people with the same color will join him, and the rest will go the the opposite side.

Improve this answer
$\endgroup$
3
$\begingroup$

I came up with this answer, which can be generalized nicely for multiple colors:

Inmates are assigned numbers $1$ through $n$. In the room, every inmate $i$ determines the parity of blue noses of all other inmates, which we call $b_i$ and is either even ($e$) or odd ($o$). Inmate $1$ then chooses the left side of the room if $b_1 = e$, and right otherwise (or any similar scheme). Inmates $2$ through $n$ (in that order) know $b_1$ from the side that inmate $1$ chose, as well as $b_i$. They follow him if $b_i = b_1$, and choose the opposite side otherwise.

So there one bit of information is "communicated" without explicit communication, which helps solve the problem for two colors. For more than two ($m$) colors, ...

...we would need to transmit $m-1$ bits of information ($m-1$ parities), because the final parity can be obtained knowing the total number of inmates. The room must have $m$ different spots to allow for $m$ groups to separate. If these spots can be ordered (encoded) somehow, then by choosing one spot, inmate $1$ can transmit $\log_2 m$ bits of information (using an encoding similar to the one above). So as long as $\log_2 m > m - 1$, this is enough information for the others to know inmates $1$s observed parities of all colors, and hence their own color. Unfortunately, this does not hold for $m > 2$. So one needs an additional constraint for an arbitrary number of colors: The room must have at least $2^{m-1}$ definable spots. For smaller $m$, this should be doable; for example, $m=4$ means $8$ spots are necessary, that's just how many directions a compass has.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This is basically a variant of Pangloss's (which is simpler) and Kruga's answer. I still like my generalization :) $\endgroup$
    – bers
    Commented Feb 9, 2016 at 13:52
1
$\begingroup$

They will randomly split into two groups (Group 1 and Group 2). One random person from (let say) Group 1 will count the number of red and blue dots from the other side. There are three possibilities: same amount of red and blue colored noses, red is more or blue is more;

Possibility 1 (Red and Blue is more)

If blue is more, that one random (chosen maybe, does not matter since everyone needs to move one by one) person (let say Person 1) from Group 1 will switch any red one from Group 2 with himself. Then one another person (Person 2 from Group 1) will check Person 1's nose and if Person 1's nose is red, then he will switch himself with him. As a result Person 1 will know his nose is red and stay in Group 1. Otherwise, Person 2 will switch himself with someone else whose nose is red from Group 2. and this goes on. At the end the group 1 will be all red, and group 2 will be all blue. Same thing can be applied to If red is more.

Possibility 2

1 If the number of people whose nose has red or blue dots are the same in Group 2, one random person from Group 2 will randomly switch himself with someone from Group 1. If the balance does not change Person 2 will switch himself with Person 1. So Person 1 will know his nose color and stay in Group 2. and this will go on just like in Possibility 1 after one color overrides.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Great answers! They work... but I should have been clearer: no covert hinting as to another's colors - that's included in no communication $\endgroup$
    – Ben
    Commented Feb 9, 2016 at 8:11
  • $\begingroup$ @Ben "You may discuss a strategy now, but when you enter the room (which will be lit) - No talking, winking, burping or any communication of any kind." means they can discuss the strategy before they go into the room. I do not understand what do you mean by covert hinting at this point. They do not communicate, just switching sides without talking touching, the only thing they do count by themselves? $\endgroup$
    – Oray
    Commented Feb 9, 2016 at 8:15
  • 1
    $\begingroup$ what I mean is that even if they do work out their own color - they don't act upon it. The answer is not dependent on knowing your color... $\endgroup$
    – Ben
    Commented Feb 9, 2016 at 8:22
  • $\begingroup$ @Ben I believe there might be more than one answer to one question. So, according to your definition in the question, this answer seems to be valid to me. "They do not act upon something" is not a valid excuse not to accept this answer to be honest. IF you are looking for an answer exactly just like your own answer, you should draw your boundaries accordingly. so I believe you should define your question better at this point not to get any answer like this one more. $\endgroup$
    – Oray
    Commented Feb 9, 2016 at 8:27
  • $\begingroup$ I updated the question $\endgroup$
    – Ben
    Commented Feb 9, 2016 at 8:42
1
$\begingroup$

The fountain is the key.

Assumptions:

1. There is chocolate fountain in the the middle of the room. "We will open the door to the chocolate-fountain room"

2. You can move as much as you want, till you place yourself on on of the sides of the room "as soon as you take your place - we will mace you"

Solution:

1. First prisoner gets in and stand on one side.

2. Second prisoner gets in and goes around fountain not stopping.

3. Next prisoner gets in and:

if prisoner moving around fountain is "blue", he goes the "same" direction (clockwise or counter-clockwise)

if prisoner moving around fountain is "red", he goes the "opposite" direction.

4. Now one of the prisoners traveling around fountain knows his color.

If there are more prisoners in queue, the one who knows goes to his group. New prisoner will start at step 3.

If there are no more prisoners, the one who knows will check color of the other prisoner:

If the other one is blue, the one who knows go to his group. If the other one is red, the one who knows will circle around fountain, till the other one will leave.

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

I'm only giving this answer because I saw a lateral-thinking tag.

All the prisoners bloody the tips of their noses. This gives them a red mark regardless of the previous color. All the prisoners then group on the same wall.

Improve this answer
$\endgroup$

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