470 replies to this topic

[unreality]

There are so many answers which have been said to be "right" or "close to right" i'm confused... which is the right answer? at least the most right answer so far? You can just point me to whose post

[bonanova]

Spoiler for Here's my idea

First guy is a coin toss - let's wish him good luck.
His job is to establish the parity of black hats visible to him.
He says "Black" if he sees an odd number of black hats; "Red" otherwise.
By paying attention to what has been said, each prisoner will know his hat's color.

Example:
Second to speak hears "Black" and sees an even number of black hats.
He knows his hat is black [odd changed to even - must be his is black] and says "black".

Third guy has heard "black" and "black" and sees an even number of black hats.
He knows his hat is red [even stayed even - his hat can't be black] and says "red".

And so on, to the front of the line.

General algorithm:
The first time you hear "black", say to yourself "odd".
Each time your hear "black" after that, change the parity: "even", "odd", ... etc.
When it's your turn, if the black hats you see match the running parity, you're Red; Black otherwise.
Call out your color.</div></div></div>

[unreality]

Ah I see now! Awesome!

[spoxjox]

bonanova cracks it out of the ballpark! Great job!

This is really fascinating to me. I consider myself a reasonably intelligent person, yet it took lots of hints and many tries by others before I stumbled upon a workable solution. Then, when the problem was made just a bit more general, my best solution was to keep two completely separate ideas in mind while you worked through the problem. It would have worked...but only if the prisoners had excellent memories and the ability to keep juggling two or three changing sums the whole time.

Then bonanova introduces what is, in effect, a simplified version of my solution -- and it's perfect! Easy (easier than my original, even), 100% effective, and works for any number of prisoners.

I wonder: What is it that allows people to step outside their own mental processes and see a result like this? When I read it, it's so obvious that, had I not tried to solve it myself, I would have perhaps assumed that it was easy, that surely I would have figured it out in a minute or so on my own. It takes real genius to say something new and to which hearers respond, "Yes, that's obvious."

[roolstar]

Good Job Bonanova (as usual), I always liked your way of thinking.

Now there's a thing about these kind of puzzles. For me, I enjoy the journey of finding the solution 10 times more than the analysis of the solution. And that's because I never know where I would end up!

And here's where this puzzle lead me:

What if RED and BLACK were replaced with 0 and 1!!!!
Would the solution for this puzzle represent a new compression technique, where one number at the beginning can make the rest of the series known? in other words, would this reduce file sizes?

I realise it needs a "little" adjustment but my intuition tells me there's something there....

Good job everyone!!

[bonanova]

What if RED and BLACK were replaced with 0 and 1!!!!
Would the solution for this puzzle represent a new compression technique, where one number at the beginning can make the rest of the series known? in other words, would this reduce file sizes?

Probably not - you're only specifying parity of one of the types, not the sequence itself.
If you're interested, there's a simple compression technique called run-length coding;
starting with one of the values, you list the number of consecutive values in the string.

For example, [if red and black became 0 and 1] you might have 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0.
That would reduce to 3 2 1 4 3 1 2 2 1 1 4 2 1 3 2 reducing 32 values to 15.
Run length coding can be very efficient if the "runs" are long [tens or hundreds] but inefficient if there are many runs of length 1 and 2.

Data compression [and encryption] techniques are extremely interesting fields of study.
Check out Wikipedia here and here or do some Google searches on them.

- bn

[Sharpie357]

YOU COULD JUST ASK YOUR OTHER CELLMATES, "WHAT COLOR IS MY HAT???" IF YOUR CELLMATES AREN'T SICK AND CRUEL, THEY WOULDN'T LIE, GUARANTEEING YOUR SURVIVAL.

[Aatif]

19 it is. With 20th having 50% probability.

Spoiler for Hats on the line

Had solved it long time ago. One of my favs.
Anyway .. my logic is that:
20th says Red if the no. of Red hats he see is Even. Says Black if its Odd.
Rest is simple!
If 19 sees no. of even Red hats in front of him and he heres Black from the 20th he knows he's got to be Red. if he heard Red, then he knows he got to be Black and so on ....

[roolstar]

Probably not - you're only specifying parity of one of the types, not the sequence itself.
If you're interested, there's a simple compression technique called run-length coding;
starting with one of the values, you list the number of consecutive values in the string.

For example, [if red and black became 0 and 1] you might have 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0.
That would reduce to 3 2 1 4 3 1 2 2 1 1 4 2 1 3 2 reducing 32 values to 15.
Run length coding can be very efficient if the "runs" are long [tens or hundreds] but inefficient if there are many runs of length 1 and 2.

Data compression [and encryption] techniques are extremely interesting fields of study.
Check out Wikipedia here and here or do some Google searches on them.

- bn

I agree...

In fact I gave up on the idea after the post since every prisoner has to count the ones in front of him to determine him/herself, which means replacing every 0 & 1 will still be another number (not very effective for compression I guess)!

[unreality]

This is an awesome riddle btw I voted 5 stars ;D