It is currently Sun Dec 15, 2019 5:43 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 43 posts ]  Go to page Previous  1, 2, 3  Next
Author Message
Offline
 Post subject: Re: Hat problem
Post #21 Posted: Thu May 02, 2013 3:00 am 
Beginner

Posts: 17
Location: Finland
Liked others: 3
Was liked: 5
Rank: EGF 2 dan
My solution is here, don't read if you want to solve it yourself. No silly tricks with time delays or anything like that.

All players follow the same strategy. Their guess is determined by the 3 colors they see.

:white: :white: :white: -> guess :black:
:white: :white: :black: -> no guess
:white: :black: :black: -> guess :white:
:black: :black: :black: -> guess :black:

They will win a bottle with probability 68.75%. Proof:

:white: :white: :white: :white: -> lose
:white: :white: :white: :black: -> win (4 permutations)
:white: :white: :black: :black: -> win (6 permutations)
:white: :black: :black: :black: -> lose (4 permutations)
:black: :black: :black: :black: -> win

They lose 5/16 of the time and win 11/16 of the time, Q.E.D.



More detailed explanations about the cases where they win:

All hats: :white: :white: :white: :black:. One player sees :white: :white: :white: and guesses correctly :black:. The other 3 players see :white: :white: :black: and guess nothing.

All hats: :white: :white: :black: :black:. Two players see :white: :white: :black: and guess nothing. The other two see :white: :black: :black: and guess correctly :white:.

All hats: :black: :black: :black: :black:. All players see :black: :black: :black: and guess correctly :black:.



I don't know if this is the optimal strategy. I also tried to include randomness in the strategy (guess white with probability p1, black with probability p2, nothing with probability p3) and to use different strategies for each player. However, I couldn't improve from 11/16.


This post by jlaire was liked by 2 people: drmwc, Joaz Banbeck
Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #22 Posted: Thu May 02, 2013 6:24 am 
Tengen
User avatar

Posts: 4838
Location: Mechanicsburg, PA
Liked others: 62
Was liked: 501
Rank: Wbaduk 7D
KGS: magicwand
Tygem: magicwand
Wbaduk: rlatkfkd
DGS: magicwand
OGS: magicwand
my percentage 87.5%
strategy : who sees 3 of same color will guess right away.and say opposite color.
when no one i is guessing it means there are two color of each. so after while you know it is 2:2. so you know what color you have.

only time you will get it wrong it when it is all same color which is 2/16
14/16 you will be correct.


edit: and i see that someone already solved it :)

_________________
"The more we think we know about
The greater the unknown"

Words by neil peart, music by geddy lee and alex lifeson

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #23 Posted: Thu May 02, 2013 7:33 am 
Lives in sente

Posts: 716
Liked others: 666
Was liked: 133
Rank: Washed up never was
Universal go server handle: Splatted
I think that the delayed guessing plans are no different from a secret signal and should be considered communication. In fact, everyone looking at their watches would become an unintended signal.

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #24 Posted: Thu May 02, 2013 10:33 am 
Lives in gote
User avatar

Posts: 434
Liked others: 64
Was liked: 93
Rank: 4 Dan European
Time delay solutions will result in everyone being shot. The guesses all have to happen at exactly the same time, pre-assigned time.

jlaire is on the right lines. However, it's possible to do better than his solution.

For LocoRon, the wine is 1995 Dom Perignon, and so well worth taking a punt at...

Clue:
The fact they are bridge players is a (minor) clue.

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #25 Posted: Thu May 02, 2013 4:22 pm 
Tengen
User avatar

Posts: 5305
Location: Banbeck Vale
Liked others: 967
Was liked: 1343
Rank: 1D AGA
GD Posts: 1512
Kaya handle: Test
I think that I am beginning to understand this problem...

drmwc wrote:
jlaire is on the right lines.

jlaire wrote:
..
...All players follow the same strategy. ...

drmwc wrote:
However, it's possible to do better than his solution.


This post by Joaz Banbeck was liked by: rhubarb
Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #26 Posted: Thu May 02, 2013 5:15 pm 
Lives in sente
User avatar

Posts: 761
Liked others: 152
Was liked: 204
Rank: the k-word
I wrote a brute force program using drmwc's hint and got a 12/16 solution. However I don't really understand it, so I won't post it for now.

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #27 Posted: Thu May 02, 2013 7:13 pm 
Tengen
User avatar

Posts: 5305
Location: Banbeck Vale
Liked others: 967
Was liked: 1343
Rank: 1D AGA
GD Posts: 1512
Kaya handle: Test
I think that I have a theoretical understanding of the problem:
It is basically an information transfer problem. I recognized that early on, and concluded that since they were not allowed to communicate, the problem was mis-stated.
However, jlaire demonstrated that there is more than meets the eye. The pre-arranged agreement is a code, and the stones that they see are the key. Different patterns of stones mean different keys, which effectively allows them to communicate.

jlaire made one slight oversight. He assumed that the
key = the stones that they see.
Whereas, actually,
key = the stones that they see AND where they see them.
This allows more keys, and, therefore, the effective transfer of more information.


This means that, as a practical matter...

. :black: :black: :white: <> :black: :white: :black: <> :white: :black: :black:


About Drmwc's clue:

This, BTW, explains what Drmwc meant by
drmwc wrote:
...The fact they are bridge players is a (minor) clue.
Bridge players think in terms of position. A bid by the opponent to your left is not the same as the same bid made by your opponent to the right.


That means that to improve on Jlaire's solution, you probably have to look here:

jlaire wrote:
...
:white: :black: :black: :black: -> lose (4 permutations)...

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #28 Posted: Thu May 02, 2013 8:11 pm 
Lives in sente
User avatar

Posts: 761
Liked others: 152
Was liked: 204
Rank: the k-word
That's not how I interpreted the hint, by the way.

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #29 Posted: Thu May 02, 2013 10:26 pm 
Tengen
User avatar

Posts: 5305
Location: Banbeck Vale
Liked others: 967
Was liked: 1343
Rank: 1D AGA
GD Posts: 1512
Kaya handle: Test
I think that Jlaire's 4 possible distributions have to be 5. When it is 2+2, there are two possible positional options: adjacent or opposite.

:white: :white: :white: :white:
:white: :white: :white: :black: (4 permutations)
:white: :black: :white: :black: (6 2 permutations)
:white: :white: :black: :black: (6 4 permutations)
:white: :black: :black: :black: (4 permutations)
:black: :black: :black: :black:


Instead of merely four instructions, like this:

:white: :white: :white: -> guess :black:
:white: :white: :black: -> no guess
:white: :black: :black: -> guess :white:
:black: :black: :black: -> guess :black:

There should be eight like this:

:white: :white: :white: -> guess :black:
:white: :white: :black: -> no guess
:white: :black: :white: -> no guess
:white: :black: :black: -> guess :white:
:black: :white: :white: -> guess :black:
:black: :white: :black: -> no guess
:black: :black: :white: -> guess :black:
:black: :black: :black: -> guess :black:

( everything to the right of the arrows is just a guess about guessing )

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #30 Posted: Fri May 03, 2013 10:11 am 
Lives in gote
User avatar

Posts: 434
Liked others: 64
Was liked: 93
Rank: 4 Dan European
I believe that something like Joaz's solution can work (although I've not checked that solution in detail).

There is a simpler approach that gets 75%.

Big clue:
Nominate someone to be dummy.

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #31 Posted: Fri May 03, 2013 11:08 am 
Gosei

Posts: 1338
Location: Finland
Liked others: 47
Was liked: 122
Rank: FGA 7k GoR 1297
drmwc wrote:
I believe that something like Joaz's solution can work (although I've not checked that solution in detail).

There is a simpler approach that gets 75%.

Big clue:
Nominate someone to be dummy.

Ok, got it now:

Ignore one player altogether (he doesn't guess, and no one is interested in his hat

The remaining three will do as follows:
- if you see two hats of different color, don't guess
- if you see two hats of same color, guess the other color

_________________
Offending ad removed


This post by tj86430 was liked by 3 people: jlaire, palapiku, rhubarb
Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #32 Posted: Fri May 03, 2013 11:44 am 
Dies in gote

Posts: 31
Location: Vancouver
Liked others: 92
Was liked: 14
Rank: mid-SDK
DGS: rhubarber
Universal go server handle: rhubarb
tj86430 wrote:
drmwc wrote:
Big clue:
Nominate someone to be dummy.

Ok, got it now:

Ignore one player altogether (he doesn't guess, and no one is interested in his hat

The remaining three will do as follows:
- if you see two hats of different color, don't guess
- if you see two hats of same color, guess the other color


In the spirit of the puzzle, an amendment:

Ignore one player altogether (he doesn't guess, and no one is interested in his hat During deliberation, before hat distribution, shoot one player.


This post by rhubarb was liked by: drmwc
Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #33 Posted: Fri May 03, 2013 11:52 am 
Lives in sente
User avatar

Posts: 761
Liked others: 152
Was liked: 204
Rank: the k-word
Nicely done!
Turns out i misinterpreted the bridge hint after all.
I interpreted it to mean that the 4 players separate into partnerships, each with its own strategy. This gives two 12/16 solutions, which are completely different from tj86430's. In particular, nobody is left out - everyone has a potential to make a guess.

The fact that there are several 12/16 solutions suggests that it could be possible to do even better... I suppose the next step is to prove that that is impossible.

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #34 Posted: Fri May 03, 2013 12:35 pm 
Lives in gote

Posts: 630
Location: Austin, Texas, USA
Liked others: 46
Was liked: 210
Go version of the hint:
There are 4 kibitzers: 1 guest, and 3 registered [1d] players.

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #35 Posted: Fri May 03, 2013 12:51 pm 
Gosei

Posts: 1338
Location: Finland
Liked others: 47
Was liked: 122
Rank: FGA 7k GoR 1297
Perhaps it would be nice to hide the previous message, since the hint is still hidden.

_________________
Offending ad removed

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #36 Posted: Fri May 03, 2013 12:57 pm 
Tengen
User avatar

Posts: 5305
Location: Banbeck Vale
Liked others: 967
Was liked: 1343
Rank: 1D AGA
GD Posts: 1512
Kaya handle: Test
tj86430 wrote:
...Ignore one player altogether (he doesn't guess, and no one is interested in his hat

The remaining three will do as follows:
- if you see two hats of different color, don't guess
- if you see two hats of same color, guess the other color


That solution is:

:white: :white: :white: :white: -> loses 1 of 1
:white: :white: :white: :black: -> wins 3, loses 1
:white: :black: :white: :black: -> wins 2 of 2
:white: :white: :black: :black: -> wins 4 of 4
:white: :black: :black: :black: -> wins 3, loses 1
:black: :black: :black: :black: -> loses 1 of 1

...and gets 12 of 16.

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #37 Posted: Fri May 03, 2013 1:07 pm 
Lives in gote

Posts: 630
Location: Austin, Texas, USA
Liked others: 46
Was liked: 210
Joaz, your solution gives the same 75% rate, and it's more complicated. So tj's answer seems better.

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #38 Posted: Fri May 03, 2013 1:38 pm 
Tengen
User avatar

Posts: 5305
Location: Banbeck Vale
Liked others: 967
Was liked: 1343
Rank: 1D AGA
GD Posts: 1512
Kaya handle: Test
yoyoma wrote:
Joaz, your solution gives the same 75% rate,...


MINE WORKS???

:lol: :lol: :lol: :lol: :lol:

I was just choosing guesses to create an example. I wasn't trying to solve the problem, just trying to show the format of a solution.


This post by Joaz Banbeck was liked by: Bill Spight
Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #39 Posted: Fri May 03, 2013 3:18 pm 
Lives in gote
User avatar

Posts: 434
Liked others: 64
Was liked: 93
Rank: 4 Dan European
palapiku wrote:
Nicely done!
Turns out i misinterpreted the bridge hint after all.
I interpreted it to mean that the 4 players separate into partnerships, each with its own strategy. This gives two 12/16 solutions, which are completely different from tj86430's. In particular, nobody is left out - everyone has a potential to make a guess.

The fact that there are several 12/16 solutions suggests that it could be possible to do even better... I suppose the next step is to prove that that is impossible.


I don't know if I should use a spoiler, but people may be grunching the thread...

Proving 75% is optimal sounds like quite an intersting problem. I have no idea how one could go about it other than brute force and ignorance.

The set of possible deterministic solutions is presumably finite, which makes brute force and ignorance plausible. However, random strategies could be used. I don't see off-hand how they can improve things, but they do have the annoying feature of making the solution space infinite, So some general nonsense result may be needed to cope with this.

Brute force and ignorance can get you an awfully long way in maths...

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #40 Posted: Thu May 09, 2013 11:08 pm 
Lives in gote

Posts: 352
Liked others: 68
Was liked: 305
Rank: maybe 2d
Solution and attempted proof of optimality:
Any individual player, conditional on that player making a guess, can be correct at most 50% of the time. So, intuitively, how is it that we can do better than 50%?

Simple: imagine we've already decided on player 1's strategy and we're now trying to choose player 2's strategy. If we can arrange it so that player 2's wrong guesses coincide with player 1's wrong guesses, whereas player 2's correct guesses happen at times that player 1 wouldn't have attempted to guess, we can increase the number of outcomes where at least one correct guess happens, without increasing at all the number of outcomes where an incorrect guess happens. As long as we can do this efficiently enough with each subsequent player, it's not hard to see why in theory we might be able to beat 50%.

There are several other classic puzzles with the same concept as this one. In all of them, the key is to choose strategies for the players that cause wrong guesses to be as densely concentrated as possible and correct guesses to be as disjoint as possible. The "bridge" strategy is very effective at this - in the cases that anyone guesses wrongly, 3 people all do so, whereas in the cases that anyone guesses correctly, there is only 1 person doing so. This results in there being 3 hat combinations guessed correctly for every 1 hat combination guessed wrongly, and since this strategy also always has someone guess, the winning percentage is precisely 3:1 = 75%.

A little bit of thought along these lines reveals that since at most 4 players can guess wrongly at once, an immediate upper bound for the best possible winning percentage for any strategy is 4:1 = 80%.

For this specific problem, there is also an interesting geometric visualization. Take all of the hat combinations to be vertices of a graph where there is an edge between two vertices if they differ in exactly one hat. In the 3-person case, this graph is simply a cube. In the 4-person case, it's a hypercube.

Saying that someone will guess a particular color for their own hat when they see a certain combination of other hats is equivalent to choosing a single edge in the graph and marking one of the vertices for that edge as "wrong" and the other as "correct". The choice of edge corresponds to the the choice of person and combination that they see, while the choice of which vertex to mark wrong/correct corresponds to color of hat we want that person to guess in that case. The goal is to maximize the number of vertices marked "correct" at least once and marked "wrong" zero times.

Visualizing it like this, it's now easy to see that 75% is optimal. In general, we will consign some number of vertices to be marked "wrong", and then by choosing all outgoing edges, we can cause all adjacent vertices to them to be marked "correct". And it's clear for any fixed choice of vertices that we'd like to be the "wrong"-marked ones, doing this is the best we can do. Now, if we choose any 4 vertices to be marked "wrong" in such a way that all other vertices are adjacent to at least one of them, we get one of the 75% solutions, because we are correct on all but 4 out of 16 vertices. We can only potentially do better by initially choosing fewer vertices to be "wrong", but if we choose 3 or fewer vertices, then since each vertex has only 4 outgoing edges, we can make at most 12 vertices "correct", which is again only 75%.

Therefore, 75% is optimal.


This post by lightvector was liked by 2 people: Joaz Banbeck, rhubarb
Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 43 posts ]  Go to page Previous  1, 2, 3  Next

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group