It is currently Thu Apr 18, 2024 8:15 pm

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 43 posts ]  Go to page 1, 2, 3  Next
Author Message
Offline
 Post subject: Hat problem
Post #1 Posted: Wed May 01, 2013 2:14 pm 
Lives in gote
User avatar

Posts: 452
Liked others: 74
Was liked: 100
Rank: 4 Dan European
4 bridge players are at a table. The tournament director offers them the following proposition:

They are all randomly and simulateously assigned black or white hats. Once they are given their hat, they may not communicate with the other 3 players in any way. If they violate this rule in any way, they will all be shot.

The chances of an individual player being given a hat of a particular colour is 50%; and the hat colours are chosen independently for the 4 players.

They cannot see their own hat colour, but they can see the other 3 players' hats. Any attempt to find their own hat colour by nefarious methods (such as mirrors) will result in them all being shot.

After a deliberation period, all 4 players have the option of guessing their hat colour. The guesses will be simultaneous (or they will be shot). Each player has the option of remaining silent - this will not result in anyone being shot.

If at least one player guesses, and all the guesses made are correct, they win a bottle of champagne. Wrong guesses have no ill effect - no-one is shot.

They may discuss strategy beforehand without being shot.

The problem is to find a strategy which maximises the probability of them getting champagne, with 0% chance of them being shot.

To get things started: They could nominate 1 person to guess and the other three will abstain. This has 50% chance of champagne. (The winning strattegy is better than 50%.)

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #2 Posted: Wed May 01, 2013 3:01 pm 
Lives with ko
User avatar

Posts: 292
Liked others: 92
Was liked: 80
Rank: 1 kyu
KGS: LocoRon
drmwc wrote:
The problem is to find a strategy which maximises the porbability of them getting champagne, with 0 chance of them being shot.


Get a job and pay for the champagne like a normal person.


This post by LocoRon was liked by 3 people: drmwc, ez4u, Splatted
Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #3 Posted: Wed May 01, 2013 3:55 pm 
Tengen
User avatar

Posts: 4844
Location: Mechanicsburg, PA
Liked others: 62
Was liked: 505
Rank: Wbaduk 7D
KGS: magicwand
Tygem: magicwand
Wbaduk: rlatkfkd
DGS: magicwand
OGS: magicwand
drmwc wrote:
4 bridge players ...... than 50%.)

i have a feeing that i am missing some important info.

_________________
"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 #4 Posted: Wed May 01, 2013 4:23 pm 
Lives in gote

Posts: 589
Liked others: 0
Was liked: 114
Rank: 2 dan
I'm not sure if I'm supposed to be clever with the wording or not...I can't see a way of doing it taking it all completely at face value (though with this kind of problem, that's more likely to be my failing than anything else ;) ), but...

...depending on the nature of 'communication' and the post-deliberation-period, the players can at least exchange a little temporal information. For instance, after the deliberation period player A will immediately shout BLACK (a 50% chance) unless all three other participants are wearing white hats...in which case he hesitates, and player B knows to shout WHITE to win the game. Assuming these guys are good at keeping track of time, the first three all get a chance to hesitate and pass on a little information. That gets you slightly better than 50%, and I expect there's something a little better by being clever with binary logic or whatever...

I'm honestly not sure if this is reasonable or not, within the bounds of the problem. Even if it is, I'm not sure it helps much :) . I'd have thought it counts as communication, since information is transferred, but if absolutely no information can be transferred then surely >50% is not possible. Of course, I use 'surely' in the vaguest of senses.

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #5 Posted: Wed May 01, 2013 6:29 pm 
Lives with ko

Posts: 125
Liked others: 124
Was liked: 42
.

_________________
And the go-fever which is more real than many doctors’ diseases, waked and raged...
- Rudyard Kipling, "The Light That Failed" (1891)


Last edited by tundra on Mon Oct 09, 2017 8:56 am, edited 1 time in total.

This post by tundra was liked by: xed_over
Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #6 Posted: Wed May 01, 2013 6:55 pm 
Lives in gote
User avatar

Posts: 603
Liked others: 43
Was liked: 139
Rank: 6-7k KGS
If you see three hats, you guess the opposite color; otherwise you shut up. This should work 80% of the time; if you assume that the game is played until there's either a winning situation or wrong guesses. If the hats are given out 2/2, then nobody will ever guess, and there won't be any champagne given out.

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #7 Posted: Wed May 01, 2013 7:35 pm 
Dies with sente
User avatar

Posts: 70
Location: Milwaukee, WI
Liked others: 8
Was liked: 9
Rank: 4k
KGS: kaimat
Online playing schedule: KGS most nights after 8pm CST. Sundays available anytime but on in the morning and evening.
Some thoughts:

1. "Once they are given their hat, they may not communicate with the other 3 players in any way. If they violate this rule in any way, they will all be shot." and "They may discuss strategy beforehand without being shot."

... so it would seem they could talk (or communicate in any way) only before getting their hats. I don't know their being bridge players at a table is important (it should be noted that I don't play bridge, so maybe there is a bridge connection I'm missing) and they could just as easily be in separate rooms communicating with phones or something.

2. "The guesses will be simultaneous (or they will be shot)." and "Once they are given their hat, they may not communicate with the other 3 players in any way. If they violate this rule in any way, they will all be shot."

... so they would have to decide beforehand to have any guesses done as soon as the hats are placed on their heads in order to be simultaneous since once the hats are on they couldn't even do some kind of gesture to indicate when to guess.

3. "Each player has the option of remaining silent - this will not result in anyone being shot." and "If at least one player guesses, and all the guesses made are correct, they win a bottle of champagne. Wrong guesses have no ill effect - no-one is shot."

... so no one guessing means 0% of getting killed and 0% chance of getting champagne. If one person guesses you have a 50% chance of getting champagne and a 0% chance of getting shot, since wrong guesses don't matter. If more than one person guesses you still won't get shot and the chance of winning champagne is cut in half.

This leads me to conclude that it's best to have one person randomly guess. Please let me know if I'm missing something, but it seems like they only get shot if they try to communicate after getting their hats or trying to figure out their hat color. I don't understand why someone would risk possibly getting shot just to get some champagne.

What if not guessing also gets them shot?

And why are we talking so much about shooting people. This is supposed to be a peaceful forum :)

_________________
I came to go through Kawabata and was introduced to a whole new world.

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #8 Posted: Wed May 01, 2013 8:09 pm 
Dies in gote

Posts: 31
Location: Vancouver
Liked others: 92
Was liked: 14
Rank: mid-SDK
DGS: rhubarber
Universal go server handle: rhubarb
amnal wrote:
I'm not sure if I'm supposed to be clever with the wording or not...I can't see a way of doing it taking it all completely at face value (though with this kind of problem, that's more likely to be my failing than anything else ;) ), but...

...depending on the nature of 'communication' and the post-deliberation-period, the players can at least exchange a little temporal information. For instance, after the deliberation period player A will immediately shout BLACK (a 50% chance) unless all three other participants are wearing white hats...in which case he hesitates, and player B knows to shout WHITE to win the game. Assuming these guys are good at keeping track of time, the first three all get a chance to hesitate and pass on a little information. That gets you slightly better than 50%, and I expect there's something a little better by being clever with binary logic or whatever...

I'm honestly not sure if this is reasonable or not, within the bounds of the problem. Even if it is, I'm not sure it helps much :) . I'd have thought it counts as communication, since information is transferred, but if absolutely no information can be transferred then surely >50% is not possible. Of course, I use 'surely' in the vaguest of senses.


Following up on this, a request for clarification:
When you say that the guesses will be simultaneous, which of the following do you mean?

1. There is a fixed time at which guesses are permitted. No one may guess at any other time.

-or-

2. At any time after the deliberation period ends, guesses are permitted. No guess may be made at a later time than the first guess, but multiple guesses may be made at once.

...because in case 2 the players can learn something via the time it takes to guess, which might be construed as not communicating. My guess is you've got option 1 in mind (otherwise you could probably get 100%, though I'm not positive; sounds like Muddy Children).

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #9 Posted: Wed May 01, 2013 8:10 pm 
Dies with sente

Posts: 100
Liked others: 0
Was liked: 11
Rank: IGS 16 kyu
KGS: bgrieco
IGS: bgrieco
Online playing schedule: at night 21:00 - 00:00 UTC-3
This problem is also known as the "muddy children". Instead of hats. Kids have mud on their faces, which they cannot see.
It's an interesting example on use of Kripke's structures for Modal Logic.
Not spilling the beans beyond this point though :cool:

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #10 Posted: Wed May 01, 2013 8:56 pm 
Judan
User avatar

Posts: 5539
Location: Banbeck Vale
Liked others: 1103
Was liked: 1456
Rank: 1D AGA
GD Posts: 1512
Kaya handle: Test
This is not the "Muddy Children" problem. It that, the children's answers are sequential. In the bridge problem, the answers are simultaneous.

As the problem is stated, with simultaneous answers, and dreadful penalty for ilicit communication, there is no information transferred between players. Thus each player is effectively in his own informaton universe. The best one can do is 50%. If a second guesses, the chances of winning the bottle are 25%.

My conclusion is that Drmwc accidentally mis-stated the problem, or he just likes to shoot people. :lol:


My best guess about the mis-statement is that there are multiple rounds.

_________________
Help make L19 more organized. Make an index: https://lifein19x19.com/viewtopic.php?f=14&t=5207

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #11 Posted: Wed May 01, 2013 8:58 pm 
Oza

Posts: 2356
Location: Ireland
Liked others: 662
Was liked: 442
Universal go server handle: Boidhre
Joaz Banbeck wrote:
This is not the "Muddy Children" problem. It that, the children's answers are sequential. In the bridge problem, the answers are simultaneous.

As the problem is stated, with simultaneous answers, and dreadful penalty for ilicit communication, there is no information transferred between players. Thus each player is effectively in his own informaton universe. The best one can do is 50%. If a second guesses, the chances of winning the bottle are 25%.

My conclusion is that Drmwc accidentally mis-stated the problem, or he just likes to shoot people. :lol:


My best guess about the mis-statement is that there are multiple rounds.


Nope. A mistake he did make but you're incorrect.

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #12 Posted: Wed May 01, 2013 9:10 pm 
Oza

Posts: 2494
Location: DC
Liked others: 157
Was liked: 442
Universal go server handle: skydyr
Online playing schedule: When my wife is out.
Is there a known pool of hats from which the players hats are selected?

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #13 Posted: Wed May 01, 2013 9:12 pm 
Dies in gote

Posts: 31
Location: Vancouver
Liked others: 92
Was liked: 14
Rank: mid-SDK
DGS: rhubarber
Universal go server handle: rhubarb
Muddy Children does, I think, need the children to know at the outset that at least one of them is muddy. (Analogue: know that at least one of the participants has a white hat, or that at least one has a black hat.)

I'll probably feel dumb when the answer's posted, but I don't immediately see it.

@skydyr: I think it's to be understood as each of the participants' being selected by a separate (independent) coin toss.

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #14 Posted: Wed May 01, 2013 9:21 pm 
Beginner

Posts: 17
Location: Finland
Liked others: 3
Was liked: 5
Rank: EGF 2 dan
Joaz Banbeck wrote:
The best one can do is 50%. If a second guesses, the chances of winning the bottle are 25%.

Nope. Here's a simple counterexample.

The bridge players agree on the following strategy:

- If you see 3 hats of the same color, guess the other color.
- If you see 2 hats of the same color, guess that color.

This leads to everybody giving the correct guess when the colors are distributed 1:3. That distribution happens exactly 50% of the time, so there's a 50% chance that they will win the bottle, even though everybody makes a guess.


This post by jlaire was liked by: Joaz Banbeck
Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #15 Posted: Wed May 01, 2013 9:48 pm 
Oza

Posts: 2356
Location: Ireland
Liked others: 662
Was liked: 442
Universal go server handle: Boidhre
Boidhre wrote:
Nope. A mistake he did make but you're incorrect.


I was being dense, ignore me. :)

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #16 Posted: Wed May 01, 2013 10:35 pm 
Judan
User avatar

Posts: 5539
Location: Banbeck Vale
Liked others: 1103
Was liked: 1456
Rank: 1D AGA
GD Posts: 1512
Kaya handle: Test
jlaire wrote:
Nope. Here's a simple counterexample...


I was being dense too. :shock:


However, the counterexample still does not get above 50%, so I still think that Drmwc forgot something.

_________________
Help make L19 more organized. Make an index: https://lifein19x19.com/viewtopic.php?f=14&t=5207

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #17 Posted: Wed May 01, 2013 11:25 pm 
Beginner

Posts: 17
Location: Finland
Liked others: 3
Was liked: 5
Rank: EGF 2 dan
Joaz Banbeck wrote:
However, the counterexample still does not get above 50%

It wasn't supposed to. :lol:

I have found a strategy that gives 10/16 = 62.5%. Edit: make that 11/16 = 68.75%.

I think it's crazy how much effort people have spent on looking for loopholes in the wording. I think the problem statement was very clear on first reading.


This post by jlaire was liked by: GoRo
Top
 Profile  
 
Offline
 Post subject: Hat problem
Post #18 Posted: Thu May 02, 2013 12:07 am 
Oza

Posts: 2356
Location: Ireland
Liked others: 662
Was liked: 442
Universal go server handle: Boidhre
Yeah, my problem was I read it and my brain went, "so he didn't rule out an infinite pool of hats and I got all confused.

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #19 Posted: Thu May 02, 2013 1:42 am 
Gosei

Posts: 1348
Location: Finland
Liked others: 49
Was liked: 129
Rank: FGA 7k GoR 1297
jlaire wrote:
I think it's crazy how much effort people have spent on looking for loopholes in the wording. I think the problem statement was very clear on first reading.

I think the stament was clear except for how the guessing is implemented: whether a time element can be utilized or not. I believe not, but if that is the case then it would be clearer to say e.g. that each player writes down their guess so that no one can see when and what others write, and the guesses are revealed simultaneously; not writing is permitted and equals not guessing.

If a time element could be utilized, a simple strategy would be e.g. that the players decide who will go first. That player will look at the player on the right, and if he sees a white hat, he will immediately guess something. If he sees a black hat he will stay silent, and after a while the next player will guess black. This strategy has 75% chance of success (whenever the second player has a black hat and 50% of the time when he has a white hat)

_________________
Offending ad removed

Top
 Profile  
 
Offline
 Post subject: Re: Hat problem
Post #20 Posted: Thu May 02, 2013 2:17 am 
Gosei
User avatar

Posts: 2011
Location: Groningen, NL
Liked others: 202
Was liked: 1087
Rank: Dutch 4D
GD Posts: 645
Universal go server handle: herminator
If a player sees three hats of the same color, he immediately guesses the other color.

If all hats are the same color, this means all players immediately guess wrong.

If the colors are divided 3-1, only one player guesses immediately, and his guess is correct.

If, after 10 seconds, nobody has made a guess, then the hats must be divided 2-2. One player is preassigned to guess after 10 seconds the color that makes it 2-2 (i.e. if he sees WWB, he guesses B, if he sees WBB, he guesses W).

This strategy fails if all hats are the same color (1/8 chance), succeeds in all other cases (7/8 chance).

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 43 posts ]  Go to page 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