BBO Discussion Forums: Another puzzle ... - BBO Discussion Forums

Jump to content

  • 2 Pages +
  • 1
  • 2
  • You cannot start a new topic
  • You cannot reply to this topic

Another puzzle ...

#21 User is offline   Blofeld 

  • PipPipPipPipPip
  • Group: Full Members
  • Posts: 775
  • Joined: 2005-May-05
  • Location:Oxford
  • Interests:mathematics, science fiction, Tolkien, go, fencing, word games, board games, bad puns, juggling, Mornington Crescent, philosophy, Tom Lehrer, rock climbing, jootsing, drinking tea, plotting to take over the world, croquet . . . and most other things, really.

  Posted 2007-November-21, 13:04

I will say that there's a fairly easy optimality proof for the best solution(s).
0

#22 User is offline   mink 

  • PipPipPipPipPip
  • Group: Full Members
  • Posts: 667
  • Joined: 2003-February-19
  • Gender:Male
  • Location:Germany

Posted 2007-November-21, 13:48

Each prisoner can see only one of 2 different situations:

A: All other hats have the same color
B: One of the other hats has a different color than the other 2

If the distribution of colors is 3-1, they succeed if they guess the other color in A. They also succeed if the guess the majority color in B. Only one of these strategies is needed; they could well pass in the other case.

If the distribution of colors is 2-2, they succeed if they guess the minority color in B. If one sees A he knows it cannot be 2-2.

If the distribution is 4-0, the succeed if the guess the same color in A. If somebody sees B, he knows it cannot be 4-0.

The last 2 strategies can be combined, thereby winning in all 2-2 cases and in both 4-0 cases. But they can also agree on one of the 3-1 strategies. No matter on what they decide, they have always a 50% probability to get it right.

If the 3-1 strategy and the 2-2 strategy could be combined in some way, they might achieve a success rate of 87.5%, but I doubt that that is possible given they have to guess simultaneously.

Karl
0

#23 User is offline   han 

  • Under bidder
  • PipPipPipPipPipPipPipPipPipPip
  • Group: Advanced Members
  • Posts: 11,797
  • Joined: 2004-July-25
  • Gender:Male
  • Location:Amsterdam, the Netherlands

Posted 2007-November-21, 17:28

Blofeld, on Nov 21 2007, 09:58 AM, said:

I'm intrigued, now, Han - what did you think the problem was? There's obviously a range of interesting problems here.

I understood the problem, just not the solution. I know the solution to the 4-person problem now but I haven't had a chance to really think about it. I haven't thaught about the n-person problem yet so please don't give away the solution to that Owen.
Please note: I am interested in boring, bog standard, 2/1.

- hrothgar
0

#24 User is offline   han 

  • Under bidder
  • PipPipPipPipPipPipPipPipPipPip
  • Group: Advanced Members
  • Posts: 11,797
  • Joined: 2004-July-25
  • Gender:Male
  • Location:Amsterdam, the Netherlands

Posted 2007-November-30, 20:50

Well, perhaps Owen could post the solution. I have found a fairly easy way to show that you cannot do better than 3/4 with 4 people, but I'm ashamed to admit that I do not know the best solution when there are n people. All I know is that the probability of success goes to 1.
Please note: I am interested in boring, bog standard, 2/1.

- hrothgar
0

#25 User is offline   zasanya 

  • PipPipPipPipPip
  • Group: Full Members
  • Posts: 747
  • Joined: 2003-December-24
  • Gender:Male
  • Location:Thane,Mumbai,Maharashtra,India
  • Interests:Chess,Scrabble,Bridge

Posted 2007-December-01, 11:40

I have come to the onclusion you cant do better than 75%.You have to treat each pproblem as if it was 3 people problem .Please tell me i am wrong.
Aniruddha
Do unto others as you would have others do unto you.
"Mediocrity knows nothing higher than itself, but talent instantly recognizes genius".
0

#26 User is offline   david_c 

  • PipPipPipPipPipPip
  • Group: Advanced Members
  • Posts: 1,178
  • Joined: 2004-November-14
  • Location:England
  • Interests:Mathematics;<br>20th century classical music;<br>Composing.

Posted 2007-December-01, 12:12

Hannie, on Dec 1 2007, 03:50 AM, said:

Well, perhaps Owen could post the solution. I have found a fairly easy way to show that you cannot do better than 3/4 with 4 people, but I'm ashamed to admit that I do not know the best solution when there are n people. All I know is that the probability of success goes to 1.

I've seen this problem before, and I think I was told it hadn't been solved for general n. Though your observations are clearly true.
0

#27 User is offline   jtfanclub 

  • PipPipPipPipPipPipPip
  • Group: Advanced Members
  • Posts: 3,937
  • Joined: 2004-June-05

Posted 2007-December-01, 13:26

OK....

I tell the guard in advance "I'm guessing whatever Max guesses", while Max isn't in the room.

Max comes out, and announces the color of my hat.

I have, simultaneously, guessed the same color.

I will always be right.
0

#28 User is offline   david_c 

  • PipPipPipPipPipPip
  • Group: Advanced Members
  • Posts: 1,178
  • Joined: 2004-November-14
  • Location:England
  • Interests:Mathematics;<br>20th century classical music;<br>Composing.

Posted 2007-December-01, 14:07

Also, if you like this problem, try doing the n=7 case. (I believe this is the smallest value of n for which you can do better than 3/4.) There's a relatively simple way to do better than 3/4 here, by
Spoiler
. But it's possible to do even better than this.
0

#29 User is offline   Blofeld 

  • PipPipPipPipPip
  • Group: Full Members
  • Posts: 775
  • Joined: 2005-May-05
  • Location:Oxford
  • Interests:mathematics, science fiction, Tolkien, go, fencing, word games, board games, bad puns, juggling, Mornington Crescent, philosophy, Tom Lehrer, rock climbing, jootsing, drinking tea, plotting to take over the world, croquet . . . and most other things, really.

Posted 2007-December-01, 19:30

(I don't have the time to post a properly explained solution now; someone else is welcome to, or I shall in a couple of days. Some comments, in hidden text:)

Spoiler


Challenge: What's the best you can do with three people, and three possible hat colours?
0

#30 User is offline   david_c 

  • PipPipPipPipPipPip
  • Group: Advanced Members
  • Posts: 1,178
  • Joined: 2004-November-14
  • Location:England
  • Interests:Mathematics;<br>20th century classical music;<br>Composing.

Posted 2007-December-03, 06:57

Blofeld, on Dec 2 2007, 02:30 AM, said:

Further generalisation of the problem: allow k hat colours instead of just 2. Now I can't even prove that the probability of success goes to 1 as n goes to infinity (for fixed k), though I think it's the case.

Let p ( win ) / p ( someone guesses wrong ) = R. Then

(i) R can be made arbitrarily large, as n goes to infinity. (Strategy: if you don't see anyone with a hat of a certain colour, then guess that colour. Otherwise don't guess. A bit boring to check that this works, but it "obviously" does.)

(ii) Given a strategy for n people with a certain value of R, there is an obvious strategy for s.n people which has the same ratio R, such that p ( no-one guesses ) goes to 0 as s goes to infinity.

Of course, the bound that you get is awful, but ...

Quote

Challenge: What's the best you can do with three people, and three possible hat colours?

Spoiler

0

  • 2 Pages +
  • 1
  • 2
  • You cannot start a new topic
  • You cannot reply to this topic

1 User(s) are reading this topic
0 members, 1 guests, 0 anonymous users