Brain Teasers

[aphexcoil]

Quote from jaan:


the THP caused a huge splash in the math community, being a seemingly simple puzzle yet challenging the very foundations of modern information theory.

You aren't kidding. It has potential huge implications for hamming codes, information compression, etc.

For those who don't know the puzzle, here it is: (Try to really think it over before searching the net for a solution).

THE THREE HAT PROBLEM:

Three men enter a room and are each given a colored hat that is based on a coin-flip. The two hat colors are red and blue. While inside the room, they are not allowed to communicate in ANY way. The only communication that is allowed is a (big hint here) strategy to use before entering the room.

The rules are simple. In order to win, one person must correctly pick the color of his hat and no one is allowed to guess incorrectly. When it is your turn to guess the color of your hat, you may pass.

If two people pass and the third randomly guesses hit hat color, there is a 50% chance the team of three men will win.

Can you come up with a strategy they can use that will give a greater chance of winning?

 

[stu]

6 SOCKS for krist sakes

 

[hii a_ooiioo_a]

Daniel gave the correct solution, and the correct reasons.

This is more of a brain-twister than a brain-teaser.


It all is based on getting into what the red-dot monks were thinking about what the other red-dot monks were thinking about what they were thinking . . . .

It's like looking in a hall of mirrors. The only mirror the monks had was the mental deduction process of the other monks.

It works like "I know that you know that I know that you know that I know that you know that . . ."

 

[aphexcoil]

Quote from hii a_ooiioo_a:


It works like "I know that you know that I know that you know that I know that you know that . . ."

Another great example of pure game theory.

 

[jaan]

Quote from jaan:
3. the monks get the one bit of information of whether they are infected or not by comparing the number of spots they see on others to the number of days that have passed. hence:

whoa, now i'm really starting to see the weirdness of this... the problem is that nobody has told the monks to use that particular algorithm (comparing the number of spots to number of days passed) in the first place!

while it is trivial that this algorithm should be used for N=1 (because if you don't see anybody else with a spot, then the N must be 1 and you should go kill yourself), it is quite difficult to prove that the same algorithm should be used for N>1!

the only proper proof i can imagine would use mathematical induction -- ie stating that the theorem holds for N=1, and proving that for each N that the theorem holds, it would also hold for N1=N+1. but the proof would definitely not be trivial not to mention intuitive.

- jaan

 

[DTK]

I'm going to join the self destruction club with Gordo, but only if the dot appears beofre and looks like it will last through the weekend. I think I may be a little old to be having these worries though.

Quote from hii a_ooiioo_a:

Thank you


I'm now going to look in the mirror, and if I see a red dot on my forehead I am going to kill myself.

 

[aphexcoil]

Quote from jaan:

but the proof would definitely not be trivial not to mention intuitive.

- jaan

Mathematical logic problems like these are usually very difficult to solve.

When I first heard the Monty Hall problem, it took me some time to grasp what was taking place. Sooner or later you get used to being amazed.

 

[DTK]

If this read:

To have gold is good;
To be stoned is nothing;
To break glass that's fragile;
To be cold is cruel 'cuz it means the liquor is wearing off.
Unmetaphored, what am I?

I would have to say a ROCKSTAR.

Quote from aphexcoil:

To be gold is to be good;
To be stone is to be nothing;
To be glass is to be fragile;
To be cold is to be cruel.
Unmetaphored, what am I?

 

[jaan]

Quote from aphexcoil:
When I first heard the Monty Hall problem

that's really cool, thanks for mentioning it (i hadn't heard it before).

- jaan

 

[aphexcoil]

Quote from DTK:

If this read:

To have gold is good;
To be stoned is nothing;
To break glass that's fragile;
To be cold is cruel 'cuz it means the liquor is wearing off.
Unmetaphored, what am I?

I would have to say a ROCKSTAR.

The answer is "heart"