Say theres a lot of little teddy bears.
One day, an evil goblin king enslaved these poor teddy bears, and put these evil magical headbands on their heads. Then he sent the bears to go work in the mountains.
Now these magical headbands are cursed, so the bears aren''t able to take them off by any means. Each headband is also either black or white. As the bears cannot take off their headbands, each bear is unable to tell the colour of his or her own headband. Due to the cursed headbands, each bear is not able to inform other bears what colour headband they have. So simply put - there is no way of observing what colour headband a bear wears himself, and due to the evil power of the headbands (and because teddy bears can't talk) there is no way of alerting a fellow bear what colour headband he or she is wearing.
After one particularly tiring day of working in the mountains, the bears trudged down from the mountain, and stood side-by-side in a line-up ... as they do every evening at the stroke of midnight . The goblin king normally takes this short period of time to count them all (though there is little need to - the bears have no way of escaping anyway). However, this night was different. The evil goblin king eyed them all with his evil eyes, and boomed,
"I AM GIVING YOU ALL A CHANCE FOR FREEDOM!
IF EACH OF YOU MANAGE TO FIGURE OUT THE COLOUR OF THE HEADBAND ON YOUR HEADS, I WILL SET YOU ALL FREE!
HOWEVER, IF EVEN JUST ONE OF YOU, GUESSES WRONG ...
YOU WILL ALL ... DIE."
And so the evil goblin king cackled, evilly.
Each bear glanced at one other and nervously gulped. Now the bears knew that they had a chance to escape, but they must do so without any kind of communication with each other. In fact this is not a trick question at all, it works on the assumption that all the bears are quite brainy (they like playing these kind of problems too!).
Every evening, the bears line up as usual at the stroke of midnight and are given a short period of time to try. As the bears cannot speak, the bears with the black headbands should take one step forward, while the bears with the white headbands should remain where they are. They are not allowed to do anything else (they cannot gesture, or even interact with one other - due to the evil power of the headband). Once all the bears with the black headbands have taken a step forward, then all the bears will be set free. However, as the goblin king mentioned - if just one bear with a white headband steps forward, then they will all be killed (and turned into fluffy pillows).
I repeat, the only thing that the cursed power of the headbands lets them do, during the entire course of the day, is to let them either stay where they are during the line-up, or to take that one step forward. The cursed headbands also forbid them from communicating with each other.
But the bears know two things that should help them - that there is at least one bear with a white headband, and there is at least one bear with a black headband. They know that somehow, this will help them solve this problem. Thankfully, the goblin king didn't set a time-limit, so they can take as long as they want with this (that is, they can use as many line-ups as they wish)
How do the bears solve this? (remember, there is absolutely no way they can communicate/interact with one other, and theres no way they can observe the colour of their own headband either - ie. no glancing into reflective streams etc.)
This one's a bit tricky so the winner gets a beer.
And I repeat, this is not a trick question. Post any questions in the comments - have fun and no cheating!
Update: solution posted up in comments section.
20 comments:
hm...
One evening the king said they had a chance to be free..
So each evening they can do a line up?
Yet the problem states that if they get one wrong bear they all die. So how exactly can they have more than one line up without getting it right the first go?
Yep correct - every evening they line up as usual. Now, if for example, nothing happens at all during entire duration of the lineup (all bears stay still) - then the all go home and have to wait till the next evening.
Also, if one or more bears wearing black headbands move forward, then this is ok as well.
This continues for as long as the bears want (this is what the problem means by the bears "can use as many line-ups as they wish")
The problem ends when one of the following situations arise:
- if a bear with a white headband steps out forward (they all die)
- if all the bears with black headbands step forward (they all are set free)
i think this is really similar to a jail related incident from ages ago.
because there is at least one white headband or one black headband, all the bears line up front back front back so that they can see the colour of the headband in front of them.
lets say there is one whitehead band n the rest r black.
the bears will need to ensure the headband in front of them is always black, then the white headband will end up at the end of the line.
n vice versa, if there is one black headband and all the rest r white. the black headband will end up at the rear of the line.
but b4 they step forward or backwards, they'll prolly all have to turn 90degrees in the same direction so they dont step over each other..
= )
Do they have to stand side by side?
Nice try, sounds like it could almost work. Except it doesnt fit into context of this problem for a couple of reasons:
- Firstly, how do the bears co-ordinate this strategy? The bears are mute and the power of the headband forbids them from communicating/interacting with each other (they're not psychic either). This doesn't seem to be the kind of strategy that would work without some sort of initial verbal agreement on what to do.
- Secondly, the bears aren't allowed to turn around and move about in the line-up. "the only thing that the cursed power of the headbands lets them do, during the entire course of the day, is to let them either stay where they are during the line-up, or to take that one step forward."
You can imagine it as the bears are trapped inside their own little fluffy bodies - they are free to think all they want, but their bodies refuse to obey them (due to the evil headband). In fact the only time they have any free will at all is during the line-up - that is, to take that one step forward if they think they have a black headband on.
Keep trying though!
Yep they stand by side, and they can see all the other bears.
what a bloody long question, i cant be bothered.
Ok the solution is.
If you see a white bear and no one has moved, then you can step forward.
Once you've stepped forward you've eliminated yourself for the next round, so the next black bear can step up, unless the rest are all white.
The reason behind it is this.
You are a bear.
If you see only white bears you can step forward safely, because there is the assumption of one bear being black.
If you see one black bear, you can step forward if he didn't move. He didn't move because he see's at least one other black bear and because you can't see any other black bear, that black bear must be you.
If you see two black bears, you can step forward if neither moved. Following the previous logic, if there were only two black bears in the whole line up, one of them would have moved. This means that there is a 3rd bear; i.e. you.
If you proceed with this logic, as long as you are not the only white bear and no one has moved forward, you can take one step.
So when do you actually take your step. At the first line-up?
Gimme some sort of a timeline.
The last bear in the line would have to take the first step if no one else had made a move.
If no one else has made a move, according to my theory he should be black.
can the bears push each other?
Ok
Take the example of having 3 black bears at random out of a total of 10 bears.
1. W
2. W
3. B
4. W
5. B
6. B
7. W
8. W
9. W
10. W
We need to start from the first bear.
1 -> can see three black bears but he doesn't know what he is yet so he doesn't move
2 -> can see three black bears but he doesn't know what he is yet so he doesn't move
3 -> can see two black bears but he doesn't know what he is yet so he doesn't move
4 -> can see three black bears but doesn't know what he is yet so he doesn't move
5 -> can see two black bears but he doesn't know what he is yet so he doesn't move
6 -> can see two black bears but he doesn't know what he is. What he can also see is that the rest of the line is white.
From this thinking number 6 bear has now ruled out his chances of being black. So this is what 6 is thinking now
1. W
2. W
3. B
4. W
5. B
6. B
6 can see that there are two blacks, but they still haven't moved yet. Why? The only reason is because the other two black bears can see two black bears too. In order for 3 and 5 to see two black bears that means 6 is the black bear. So now 6 can step forward.
Now that 6 has stepped forward, 3 can see there is 1 black bear now, but doesn't know what he is yet. 5 can see that 3 is the only black left which means that he isn't white otherwise he would've stepped foward.
So now 3 can step forward because he's surrounded by white.
They would need to have some sort of time limit for that to work. Because if bear 6 took his time wondering why bear 5 is not moving, bear 7 might think he's black.
Then they all die.
Maybe they can gaze into each other's eyes...
Both of you are right (except for the eye-gazing thing)!
D's logic is sound, and is on track to the complete solution of this problem. There's only one problem ...
Tee is correct too, and points out the flaw in D's solution. There needs to be some way of the bears knowing when to step forward?
Almost there!
haha derek, i never realised u were so smart! :P
Good work, Tramaine!
Tee = Teresa not Tramaine
i dont care! tramaine deserves credit regardless hehe..
but yeah, good on ya teresa!
Solution
Alright, here goes. Now whatever solution you come up with for this problem, you have to assume a strategy something the bears can think up all on their own ('cos they can't communicate with each other). So if you dream up a solution that works well technically, but isn't intuitive, then the bears may start employing different strategies. The one thing that we can assume is that the bears will be conservative in whatever strategy they take - mainly because none of them would really want to die right? Problem is the bears can't communicate with each other, so they have to speculate upon what each other could be thinking ...
Ok so lets start with a great deal of bears, like the question states.
Say there's one bear with a black headband (B1) only, and the rest are white. This is what happens:
- Lineup 1: he looks around, sees all white bears. Concludes he's the only black bear ('cos there's at least one black bear) and thus steps forward. All bears are set free.
But what happens when there's 2 black bears?
- Lineup 1: 1st black bear (B1) looks around and sees the another black bear (B2). Both think the same thing - there seems to be only one black bear in the group, so that black bear should step forward in this lineup. However, both wait and wait for that evening's lineup to end, and notice that either haven't moved (logically, they're not going to take a risk and step forward prematurely either, beacause they wouldnt want to take the risk of getting everyone killed. So they go home after the line-up and the only reason that can explain why either haven't stepped forward is because the other bear must have seen another black bear! And that black bear must be themselves.
- Lineup 2: Both bears step forward, at the same time.
Ok. So it works with 2 black bears. If you iterate through with same logic, then you can employ the same logic for 3 bears or more. Basically if there are n black bears, all the bears will all step forward at the same time, at the beginning of the n'th lineup.
And that's about it. Feel free to ask about or correct anything. Or email me riddles (if you're as bored as I am) and I'll post them up.
Post a Comment