3 hats problem

[bhargava]

You and two of your friends are on your way to a death-party. Once you get there you will each be given a hat at random that will be either red or black. Once you're wearing your hats you'll be able to see the colour of your friends' hats but you won't be able to see your own. As you well know, the host will then say:
"On the count of 3, I want each of you to simultaneously perform one of two actions: Shout out the colour of your own hat, or say nothing."

Then the rules are as follows:
If at least one of you gets it right and no one gets it wrong, you go free.
If anyone gets it wrong, you're all dead.

Your task is to devise a strategy to maximise your chances of survival. 

[Rajesh Inakota]

I dont want to go to death party .... hat free na :P .. just kidding .. good question ..

--
Regards,
Rajesh.I

[Rajesh Inakota]

is there count for number of hats

3 red hats 2 black hats some thing like that

--
Regards,
Rajesh.I

[bhargava kumar]

You are likely to get red/black with equal probability

[Rajesh Inakota]

because no one will have clue of what's on there head .. without counting tracking for atleast one would be difficult

--
Regards,
Rajesh.I

[Rajesh Inakota]

Can they pass messages, or some gestures ?

--
Regards,
Rajesh.I

[bhargava kumar]

no

[SURI]

Do they really want to live after these many conditions ?

[bhargava kumar]

they can decide not to live, chose an answer that increases their chances of
getting killed, but if you can manage that you can probably manage improving
your chances of survival :)

[Rajesh Inakota]

Nenu adhe anukutunna, party ki veldam avasarama ... ippudu (rajesh, suri, bhargav) velthe .. yevaru theerigi vastaru .. :P

On Thu, Jul 7, 2011 at 6:37 PM, SURI <koorel...@gmail.com> wrote:

Do they really want to live after these many conditions ?

--
Regards,
Rajesh.I

[Rajesh Inakota]

Without gestures or count of hats, I think this problem is NP hard.

--
Regards,
Rajesh.I

[bhargava kumar]

1. If at least one of you gets it right and no one gets it wrong, you go free.
2. If anyone gets it wrong, you're all dead.

The above 2 points can help you do better than 50% chances of survival.

[bhargava kumar]

vastee andharu vastaru, lekka potte andharu pottaru :)

[SURI]

Surely bhargav will be back.. I am not sure about both of us :)

I am not good at these problems but it is my initial attempt...
Correct me if am wrong.


1. Probability of getting Red when other two are Red is 1/4
2. Probability of getting Black when other two are Red is 3/4
3. Probability of getting Black when other two are Black is 1/4
4. Probability of getting Red when other two are Black is 3/4
5. Probability of getting Red or Black when other two are Red & Black
is 1/2

Hence i would suggest If other two having same color then go for
opposite color otherwise keep mouth shut.

-- SURI

On Jul 7, 6:10 pm, Rajesh Inakota <rajesh.inak...@gmail.com> wrote:
> Nenu adhe anukutunna, party ki veldam avasarama ... ippudu (rajesh, suri,
> bhargav) velthe .. yevaru theerigi vastaru .. :P
>

[bhargava kumar]

1. Probability of getting Red when other two are Red is 1/4

[bhargava] explain with example. If A and B have red, the probability of C having red is still 1/2.
They are all independent events
1-4 are wrong

[Rajesh Inakota]

Probability of Red hat or Black hat is 1/2

Let's think that one person is incharge.
If he sees two Red/two white on other person, then having white on his head is more probable, so he will say white.
If the incharge is not answering then those who see two red/two white only should answer.

Suri,
 needhanilo, if three have red hats/ white hats, then every one will shout white, so everyone will die.

--
Regards,
Rajesh.I

[Rajesh Inakota]

hmm,

if they are picking from the basket of red and black hats, then it matters i guess.

--
Regards,
Rajesh.I

[bhargava kumar]

If the incharge is not answering then those who see two red/two white only should answer.

[bhargava] All of them should answer simultaneously or keep their mouth shut

[Rajesh Inakota]

hmm .. lets make second incharge too ..

--
Regards,
Rajesh.I

[bhargava kumar]

Hint: The probability calculations are incorrect, but the answer is correct.
You just need to change the explanation

[Suresh Kumar Maridi]

More Hint: Its not probability.. its reducing the confusion for the next person  ..

More Hint: Suppose the first person sees both red or both black caps, what would/should he say? How does it affect the response of the next person?

--
Suresh Kumar Maridi

"it is not our abilities that show what we truly are...... it is our choices"
       - Albus DumbledorE

[Shyam Prakash Velupula]

Suresh,

The condition is that "all of them have to say the color of their hat or say nothing, SIMULTANIOUSLY,

-- శ్యాం  ప్రకాష్ 

--
You are limited only by your imagination

[SURI]

If I can assume like the total number of Red & Black are equal "across
the universe" then my explanation still holds true (actual probability
numbers may be different).
If the above assumption holds then probability of getting opposite
color is more when there is same color of hats for other two.

Any comments?

-- SURI

On Jul 7, 6:39 pm, bhargava kumar <bhargavakum...@gmail.com> wrote:
> Hint: The probability calculations are incorrect, but the answer is correct.
> You just need to change the explanation
>

> On Thu, Jul 7, 2011 at 6:55 PM, bhargava kumar <bhargavakum...@gmail.com>wrote:
>
>
>
>
>
>
>
> > 1. Probability of getting Red when other two are Red is 1/4
> > [bhargava] explain with example. If A and B have red, the probability of C
> > having red is still 1/2.
> > They are all independent events
> > 1-4 are wrong
>

[Shyam Prakash Velupula]

Suresh,

Your reasoning sounds right to me.

[Rajesh Inakota]

Suri,

 They are independent events, every pick by king for red or black is completely independent. It will be irrespective of number of black or red hats. It is the choice of king to make. For every person choosing red or black holds same probability.

Intutively we feel that if one is consumed, then consuming other will have more probability, that holds only when we play blind fold from the same deck of hats. When we keep on exhausting one type of hat then probability of other will increase. This won't hold here I guess.

On Thu, Jul 7, 2011 at 11:56 PM, SURI <koorel...@gmail.com> wrote:

--
Regards,
Rajesh.I

[Suresh Kumar Maridi]

As the hats seem to be independent events..  

I am thinking these two rules: 

1. If you see two hats of the same color , go with the same color

2. If you see two different colors , go with the color of the next person.. ( p1 will say color of p2.. , p2 of p3, p3 of p1 )

            P1  P2  P3  Result

-------------------------------------

RRR      R    R   R      all correct ( Rule 1)    

RRB      R    B  R      P1 correct (Rule 2), 

RBR      B    R  R      P3 correct (Rule 2)

RBB      B    B  R      P2 correct (Rule 2)

BRR      R    R  B      P3 correct ( Rule 2)

BRB      R    B  B       P3 correct ( Rule 2)

BBR      B    R  B     ( P1 correct Rule 2)

BBB      B   B   B      all correct Rule 1

On count of 3, everyone will follow these rules and give the response  simultaneously... 

[Suresh Kumar Maridi]

I am thinking in boolean and error-detection codes .. 

I am thinking these two rules: 

1. If you see two hats of the same color , go with the same color

2. If you see two different colors , go with the

On Fri, Jul 8, 2011 at 8:15 AM, Rajesh Inakota <rajesh....@gmail.com> wrote:

[Rajesh Inakota]

I didn't understood it completely, but how will they choose among themselves P1 or P2 or P3.

Because they don't have any idea what's on their head, to consider correctness even if they follow P1 P2 P3.

--
Regards,
Rajesh.I

[bhargava]

Incorrect. The probability stays same 1/2.

[bhargava]

1. If at least one of you gets it right and no one gets it wrong, you go free.
2. If anyone gets it wrong, you're all dead.

Even if one person gets wrong, everybody dies. Its not enough if one person gets is right, if others get it wrong, they are all dead

[bhargava]

Suresh,

If i have a bucket with 10 red hats and 10 black hats,

I pick one and give it to you, the probability of getting black hat is 1/2 and red hat is 1/2.

Your understanding is i am going the next hat from the bucket directly, so you are very likely to get red hat as there are 10 red hats and 9 red hats.

But to ensure that the probability stays 1/2 for everybody is i can add another black hat into the bucket and make them 10:10 and pick another hat for the next person.

All i need to ensure which picking hat for anybody is to ensure that the bucket has equal no of black and red hats. I could ensure that before picking the hat for each person.

--bhargava

[SURI]

As per your explanation..

Probability of having a color hat is always 1/2 for any combination
of hats on the other two. If this is the case then i don't see any way
strictly one can conclude a color based on the others hats. Hence we
can eliminate this option and assume all they are blind folded.

******** AND THEY ALL HAVE ONLY ONE CHANCE TO SAY [NOT ONCE CHANCE PER
PERSON] *********

I am clueless !!!

-- SURI

[bhargava kumar]

If they are blindfolded, then you can't do better than 50 %.

The answer lies in the option given to you
"You can optionally keep your mouth shut"

If everybody had to speak up, then you are as good as blind-folded

[Shyam Prakash Velupula]

Bhargav,

Thats what I was going to ask.

What if all keep mum? all of them get freed?

Thanks
Shyam Velupula

[bhargava kumar]

all of them get killed :) At least one has to speak up

[SURI]

I got your point ..

Case Shayam raising is may not possible since having all different
hats is not possible.. At lest two of them should have same color.
Hence at least one will speak up.

If something has to say then the person, who can see the same color
hats on other two, should say some thing...... WHAT IS IT ? HOW ??

Bhargav, I am assuming that the call out should be immediate one cant
take the call based on the calmness of the other two. Confirm if this
assumption is false !

-- SURI

On Jul 8, 11:08 am, bhargava kumar <bhargavakum...@gmail.com> wrote:
> all of them get killed :) At least one has to speak up
>
> On Fri, Jul 8, 2011 at 11:35 AM, Shyam Prakash Velupula

> <velup...@gmail.com>wrote:

>
>
>
>
>
>
>
> > Bhargav,
>
> > Thats what I was going to ask.
>
> > What if all keep mum? all of them get freed?
>
> > Thanks
> > Shyam Velupula
>

> > On Fri, Jul 8, 2011 at 11:33 AM, bhargava kumar <bhargavakum...@gmail.com>wrote:
>
> >> If they are blindfolded, then you can't do better than 50 %.
>
> >> The answer lies in the option given to you
> >> "You can optionally keep your mouth shut"
>
> >> If everybody had to speak up, then you are as good as blind-folded
>

[Shyam Prakash Velupula]

OK then,

Though probability of getting black/red is 1/2 here.

At least two people will get the same colored hat. The guy who can see same colored hats on the other two shouts the opposite color (as his hat).

This is because of nature of probability ;-)
Probability of picking same number of  red and black hats over N iterations is 1/2.

In our case N = 3. So to yield the 1/2 probability, opposite colored hat has higher chances of getting picked.

Does this sound reasonable?

Thanks
Shyam Velupula

[Rajesh Inakota]

in case of 3 same color hats all will shout .. :)

--
Regards,
Rajesh.I

[Shyam Prakash Velupula]

Yes, but the chance of this happening is just 1/3 vs one of the 3 getting a different colored hat is 2/3?

Based on my reasoning, if all shout, they are dead. If one shouts, they all survive.

Thanks
Shyam Velupula

[bhargava kumar]

Suresh,

Your assumption is right

Rajesh

The statement 'in case of 3 same color hats all will shout' is second clue.

Shyam,

Probability of picking same number of  red and black hats over N iterations is 1/2.

This is not correct. It would be nC(n/2)

http://www.fourmilab.ch/rpkp/experiments/statistics.html
refer to four flips example

On Fri, Jul 8, 2011 at 11:51 AM, Rajesh Inakota <rajesh....@gmail.com> wrote:

[bhargava kumar]

The problem is not heavily dependent on probability.
Write down the cases

BBB
BBR
BRB
BRR.
......

and check why the solution works

[SURI]

Please don't say like.. Out of 8 permutations :
Changes of picking the Black is more when other two are Red -- 3/4
(RRR, RRB, RBR, BRR). LLy for RED and When they are mixed then
probability is 1/2.

-- SURI

On Jul 8, 11:31 am, bhargava kumar <bhargavakum...@gmail.com> wrote:
> The problem is not heavily dependent on probability.
> Write down the cases
>
> BBB
> BBR
> BRB
> BRR.
> ......
>
> and check why the solution works
>
> On Fri, Jul 8, 2011 at 11:55 AM, Shyam Prakash Velupula

> <velup...@gmail.com>wrote:

>
>
>
>
>
>
>
> > Yes, but the chance of this happening is just 1/3 vs one of the 3 getting a
> > different colored hat is 2/3?
>
> > Based on my reasoning, if all shout, they are dead. If one shouts, they all
> > survive.
>
> > Thanks
> > Shyam Velupula
>

[Shyam Prakash Velupula]

Based on the same logic,

See if Jeff can convince you Suresh.

http://www.codinghorror.com/blog/2008/12/finishing-the-game.html

[bhargava kumar]

the solution to this problem works similarly.


BBB
BBR
BRB
BRR
RBB
RBR
RRB
RRR

If we consider the solution "if a person sees the the same color on the other two, he will answer the opposite color"

In case of BBB/RRR - all three 3 would answer, all three would be incorrect

In case of BBR/BRB/RBB - only one one would answer, the answer would be R, it would be correct and all will survive
In case of RRB/RBR/BRR - only one one would answer, the answer would be B, it would be correct and all will survive

With this strategy you will survive with 6/8 probability


Another way of looking at the solution is

If A sees same red on other two, he will answer black, he has a choice of answering Black/Red
Similarly B and C get 2 choices, resulting in 6 cases where answers would come out

In case RRR, 3 of the above cases are covered and all of them wrong. The other 3 cases always result in the correct answer and the combinations would be

RRB - only C would open his mouth and answer it as Black
RBR - only B would open his mouth and answer it as Black
BRR - only A would open his mouth and answer it as Black
The 3 cases where A/B/C could be wrong is actually a single case RRR

[SURI]

Thanks for explanation..

May be i need to review my probability basics.

I will give you another problem similar to this but deterministic one.
Watch out for next new thread from me.

-- SURI

> <velup...@gmail.com>wrote:

>
>
>
>
>
>
>
> > Based on the same logic,
>
> > See if Jeff can convince you Suresh.
>
> >http://www.codinghorror.com/blog/2008/12/finishing-the-game.html
>