[M] 5 hats puzzle

[SURI]

You and four 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, blue, green, white or black (for simplicity we can assume
cap has numbers 1, 2, 3, 4 or 5 printed on top). 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.

The host will then take one by one to the interrogation room and asks
about the color/number of his hat. Here the condition is at least one
should be correct otherwise you are all gets killed by the host.

Before going to the party, You & Your friends need to define a
strategy such that at least one should guess correct. Are you able to
go to the party with your friends and get out?

[Shyam Prakash Velupula]

First try..

Once all the 5 friends are given hats, they assemble and does the following

=>Raise hand if one sees no duplicates (note that he can't see his own)<=

Ex: A) 1 2 3 4 5 ==> everyone raises, implies all unique, so each individual knows what color/number his has got

      B) 1 1 3 4 5 => First two persons raise their hands, rest won't. Based on this first two will know that their color is same

      C) 1 1 2 2 3 => only one guy raises hand (the last one), this indicates the other groups about two dups
          or 1 1 1 2 2 (all 1 1 1 raises hands indicating dups)

      D) else every one picks the MAX colour/number seen

           ex: 1 1 1 3 2 or 1 1 1 1 2 or 1 1 1 1 1

I know, the explanation is crude. I will think of something better and easier in the mean time.

Thanks
Shyam Velupula

--
You are limited only by your imagination

[SURI]

Shyam, I guess your solution requires few more details..

>       D) else every one picks the MAX colour/number seen
>
>            ex: 1 1 1 3 2 or 1 1 1 1 2 or 1 1 1 1 1

In the above case "1 1 1 1 2", as per your words first 4 will say
number 2 and the last one says 1 (this is what the max number they can
see).

Can we get a one liner or so to explain why your solution works?

-- SURI

[Shyam Prakash Velupula]

Ambiguity.

I mean to say max repeated color/number.

To put it in one line: "I pick the max repeated color (non ambiguous) based on what I see, or decipher my color based on number of hand raises (excluding mine)"

Thanks
Shyam Velupula

[Shyam Prakash Velupula]

Clean version of the same


Rules:

1. Raise hand if "I" see all unique colored/numbered hats (this tells other 4 that - no dups from my view)
2. Raise hand if "I" see two sets of dups (this tells the other 4 about existence of dup colors/numbers)
3. If every one raises their hand, it means, all the caps are unique (in color/number)
4. Else pick the color/number of a hat that repeated max (or) interpret had raises of other 4 (if any)


Thanks
Shyam Velupula

[bhargava]

If hand based signalling is allowed, then

Before going to party assign numbers to all the people 1 2 3 4 5
1 will be the leader, 2 3 4 5 will help 1 to guess his colour

If 1's hat colour is A - 2 will raise hand
If 1's hat colour is B - 3 will raise hand
If 1's hat colour is C - 4 will raise hand
If 1's hat colour is D - 5 will raise hand
If no body raises their hand, 1 would assume his hat colour is E

We only require one person to answer correctly, 1 would be able to correctly guess his hat colour

[SURI]

As usual you both rock...

It seems both are right here.. But Hand raising is also a kind of
information sharing, hence it is not allowed.

Once you get your hats then your eyes & brain should work nothing
else.. No eye signaling also :). You need to open your mouth in the
interrogation room.

One more thing to remember : Success/failure of 1 st person cannot be
known to the other one. i.e. result will be announced after
interrogating all 5 persons.

Hope this clarifies.. Now start trying this again ...

-- SURI

[SURI]

It seems no one seems interested/capable to attend my party .. :)

-- SURI

[Sridivakar Inakonda]

Abe, its death party, who wants attend.... :-)

[SURI]

That is why there is fun while coming out from such conditions..

What else you need ??

-- SURI

[Shyam Prakash Velupula]

Suresh,

Wait for a couple of days more before reveling anything.

- Shyam

[bhargava]

For 3 people 3 colours

1 1 1        1 2 1          1 3 1
1 1 2        1 2 2          1 3 2
1 1 3        1 2 3          1 3 3
2 1 1        2 2 1          2 3 1
2 1 2        2 2 2          2 3 2
2 1 3        2 2 3          2 3 3
3 1 1        3 1 1          3 3 1
3 1 2        3 1 2          3 3 2
3 1 3        3 1 3          3 3 3

The numbers in the bold is the replies for the corresponding people

Example: If C sees 1 1 for A and B, C will answer 1
If B sess 1 and 2 for A and C, B will answer 1

There could other ways in which you could assign these, each person is responsible for winning 9 cases

I would prefer death over writing this 5^5 :)

[Rajesh Inakota]

Let there are priorities to the hat, let's assume is hat number itself is priority.

if one sees the hat before him is higher one, he moves forward and tries to stand before him.

by the end everyone sees other :)

--
Regards,
Rajesh.I

[Rajesh Inakota]

 51111

then 1 back to 5 tries to stand before him, simillary everyone will make 5 to go end ..

by now 5 knows for sure he has 5th hat.

this logic can be applied  

--
Regards,
Rajesh.I

[Shyam Prakash Velupula]

How different is this from using hand gesturing?

I mean, it's kind of signalling right?

- Shyam

[Shyam Prakash Velupula]

Bhargav,

I didn't understand the answer. Can you please elaborate a bit?

- Shyam

[Rajesh Inakota]

There is biggest flaw in this answer, if he knows his hat number then only he can move .. :P it is not even gesturing it is blunder.

--
Regards,
Rajesh.I

[bhargava kumar]

Shyam,

I will try to explain it as best as i can

Lets pick the case

1 1 1

In this case C sees, 1 1 for A and B, and will answer 1, he would correct for 1 1 1, and he would wrong for 1 1 2 and 1 1 3.
So either A or B should ensure they report correct value for 1 1 2 and 1 1 3 combination.
I will assign the combination 1 1 2 to B, If B sees 1 2 for A and C, then  B will always say 1
I will assign the combination 1 1 3 to A, If A sees 1 3 for B and C, then  A will always say 1

So you will have

1 1 1

1 1 2
1 1 3

If B is saying 1 for 1 1 2, he would be incorrect the combination 1 2 2 and 1 3 2, so A and C should win those 2 cases
For 1 2 2, i will say that A will answer 1, i.e if A sees 2 2 for B and C, A will always answer 1
If C sees 1 3 for A and B, C will always say 2

So you will have

1 1 1

1 1 2
1 1 3

1 2 2
1 3 2

If A is saying 1 for 1 1 3, he would incorrect for 2 1 3 and 3 1 3 combination
I will assign 2 1 3 to C and 3 1 3 to B
i.e if C sees 2 1 for A and B, C will always answer 3
i.e if B sees 3 3 for A and C, B will always answer 1

So you will have

1 1 1

1 1 2
1 1 3

1 2 2
1 3 2
2 1 3
3 1 3

Keep doing this, and  you should end up assigning 9 cases to each person to win.


C will see 3 values for A and B, total of 9 different combinations, C will fix what is going
to answer to all those 9 combinations, and he will ensure that the team wins for 9
cases out of the 27.
Same goes for B and A.

The mapping tables for A B C will not be the same

For A

1 1   -> 3  ( 3 1 1)
1 2   -> 3  ( 3 1 2)
1 3   -> 1  ( 1 1 3)
2 1   -> 3  ( 3 2 1)
2 2   -> 1  ( 1 2 2)
2 3   -> 2  ( 2 2 3)
3 1   -> 1  ( 1 3 1)
3 2   -> 2  ( 2 3 2)
3 3   -> 3  ( 3 3 3)

On Tue, Jul 12, 2011 at 12:19 PM, bhargava <bhargav...@gmail.com> wrote:

For 3 people 3 colours

1 1 1        1 2 1          1 3 1
1 1 2        1 2 2          1 3 2
1 1 3        1 2 3          1 3 3
2 1 1        2 2 1          2 3 1
2 1 2        2 2 2          2 3 2
2 1 3        2 2 3          2 3 3

3 1 1        3 2 1          3 3 1
3 1 2        3 2 2          3 3 2
3 1 3        3 2 3          3 3 3

[Shyam Prakash Velupula]

Brilliant.

Bhargav, I haven't checked for any edge case but I am convinced with your answer.

Thanks

[bhargava]

Now the question to suri is, prove if this works for 5 persons, 5 colors :)

[SURI]

Good work Bhargav, But you are not up to the mark that I was expecting..

I would have accepted your solution if i would have asked the same Q for 3 hats....But it is for 5 hats..

I will verify your solution for the corner cases but still your solution is not scalable enough to do it for 5 hats easily.. 

Hence I would expect a better scalable solution.. I am sure you can do this...

Your method with assigning some combinations to some users is not random basis, your assignment should be optimal enough to accommodate  all the combinations.. 

     Any standard way to assign the combinations when working with more than 3 hats ?

     Any thoughts on the proof that there is a possibility that we can always assign the combinations successfully.

-- SURI

[SURI]

It seems everybody give-up this problem.

Let me give you some hints here..

First of all it is not a problem which requires too much paper work
(You donn't require to work on each pattern to figure out the correct
combinations) rather it contain the simple math rule which will ensure

that at least one should guess correct.

i.e. You can solve this without using a pen-paper.

Second, the solution you would get is generic, this can be applied to
any number of friends & hats (number of friends & number of hats
should be same).

Third, If we consider 2 friends and 2 hats.
Simple rule "first one always call opposite color and second
one always calls the same color that they can see". This will ensure
that at least one is always correct. Think about the reason why this
is always right and try to project it to 'say number 50'.

-- SURI

On Jul 12, 12:10 pm, Rajesh Inakota <rajesh.inak...@gmail.com> wrote:
> There is biggest flaw in this answer, if he knows his hat number then only
> he can move .. :P it is not even gesturing it is blunder.
>

> On Tue, Jul 12, 2011 at 12:31 PM, Shyam Prakash Velupula <velup...@gmail.com

>
>
>
>
>
>
>
>
>
> > wrote:
> > How different is this from using hand gesturing?
> > I mean, it's kind of signalling right?
>
> > - Shyam
>

> > On Tue, Jul 12, 2011 at 12:22 PM, Rajesh Inakota <rajesh.inak...@gmail.com

> > > wrote:
>
> >>  51111
>
> >> then 1 back to 5 tries to stand before him, simillary everyone will make 5
> >> to go end ..
> >> by now 5 knows for sure he has 5th hat.
>
> >> this logic can be applied
>
> >> On Tue, Jul 12, 2011 at 12:19 PM, Rajesh Inakota <
> >> rajesh.inak...@gmail.com> wrote:
>
> >>> Let there are priorities to the hat, let's assume is hat number itself is
> >>> priority.
>
> >>> if one sees the hat before him is higher one, he moves forward and tries
> >>> to stand before him.
>
> >>>  by the end everyone sees other :)
>
> >>> On Tue, Jul 12, 2011 at 10:51 AM, Shyam Prakash Velupula <
> >>> velup...@gmail.com> wrote:
>
> >>>> Suresh,
>
> >>>> Wait for a couple of days more before reveling anything.
>
> >>>> - Shyam
>

[SURI]

I will wait for a day before posting my version of the solution to
this problem.
If anybody wants to have another try then go ahead today..

-- SURI

[SURI]

Here is my answer to the specified problem..

For better understanding :
Assume caps are numbered as 0, 1, 2, 3, and 4.

1. 5 friends also label themself as 0, 1, 2, 3, and 4 before attending
the party.
2. Each persons prediction is as follows (Sum(Other_4_Cap_Numbers) +
prediction) mod 5 = Own_Label.
i.e. Say first person assumes that the total sum of caps mod 5 is
equal to 0.
second person assumes that the total sum of caps mod 5 is
equal to 1.
third person assumes that the total sum of caps mod 5 is
equal to 2.
forth person assumes that the total sum of caps mod 5 is
equal to 3.
fifth person assumes that the total sum of caps mod 5 is
equal to 4.
based on the above assumptions every one come up with their
own predictions. Catch here is at least one of their prediction is
always right.


A) Sample case : 2 3 3 0 1
person 1 calculation : (7 + prediction) mod 5 = 0 ==> Says
prediction as 3
person 2 calculation : (6 + prediction) mod 5 = 1 ==> Says
prediction as 0
person 3 calculation : (6 + prediction) mod 5 = 2 ==> Says
prediction as 1
person 4 calculation : (9 + prediction) mod 5 = 3 ==> Says
prediction as 4
person 5 calculation : (8 + prediction) mod 5 = 4 ==> Says
prediction as 1
In this case 5th person is correct.

B) Sample case : 4 0 0 1 3
person 1 calculation : (4 + prediction) mod 5 = 0 ==> Says
prediction as 1
person 2 calculation : (8 + prediction) mod 5 = 1 ==> Says
prediction as 3
person 3 calculation : (8 + prediction) mod 5 = 2 ==> Says
prediction as 4
person 4 calculation : (7 + prediction) mod 5 = 3 ==> Says
prediction as 1
person 5 calculation : (5 + prediction) mod 5 = 4 ==> Says
prediction as 4
In this case 4th person is correct.

Now it is your job is to figure out why this solution works..

-- SURI

[SURI]

Ok let me explain why this solution works..

Let S(A) is the sum of the numbers (0,1,2,3,4) on the hat.
In 5 hats case:
S(A) mod 5 == 0 or
S(A) mod 5 == 1 or
S(A) mod 5 == 2 or
S(A) mod 5 == 3 or
S(A) mod 5 == 4

At least one of the above formulate must be true for any combination
"because it is obvious"
Hence at least one must be correct.

Next question would be "which person will guess correctly in which
cases?"
To answer this question lets look at one example.

Q1) Example case : 4 0 0 1 3
==> S(A) = 8
==> 8 mod 5 = 3 ==> the person who is assuming that the remainder is
3 will guess correctly.

Q2) Next question would be "In best case, how many of them guess
correctly? "
I am sure, by this time must know this answer.

Consider the same example above :
-> Total sum is fixed i.e. 8
-> 8 mod 5 = 3 which is also fixed.

Take a person (at 3rd position) who is assuming that the remainder
is 2. Assume that he guesses correctly.
When other 4 numbers are fixed and you have choice of (0,1,2,3
or 4). If he has to say correct he has to guess the number as 0 but
then the remainder becomes 3 which is contradiction.

Hope this clarifies......

Cheers,
Suresh