wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Guess the day
        
(Message started by: JocK on Nov 13th, 2004, 4:03pm)
Title: Guess the day
Post by JocK on Nov 13th, 2004, 4:03pm
Would you be willing to play the following game with me?

I write a day of the week on a piece of paper. The paper goes in an envelope that I put on the table. You don't see what I have written down.

Now, you have to guess what day of the week I have written down. When you guess wrong, I tell you whether the day I have written down is earlier or later in the week than the day you have guessed (Sun < Mon < Tue < Wed < Thu < Fri < Sat). You keep guessing till you guess right. When you guess right you may open the envelope to convince yourself that I didn't cheat.

When you guess right the first time, I pay you $3. Each time you guess wrong, the amount gets reduced by $2. So if you guess right the second time, you receive $1, when you guess right the third time you get -$1 (i.e. you pay me $1), etc.

Would you be willing to play this game a few dozens of times with me?

What would your guessing strategy be?
Title: Re: Guess the day
Post by towr on Nov 14th, 2004, 2:41am
If you put as random day of the week on the piece of paper, I'd play. But I'm sure you wouldn't, so it's harder to think up a good strategy.

[e]hmm, well, I seem to at least be able to make it a fair game, so why not.[/e]
Title: Re: Guess the day
Post by Bool on Nov 17th, 2004, 4:07am
I think random picking also will not be profitable. The best way known to search in a sorted ordered list is binary search. And it takes atmost three guesses to find out the correct one. So even if the day is chosen randomly the only days which can be found out with in two guesses are wed, mon and fri which have a probability of 3/7 to be picked up as against 4/7 for others. So even the day is chosen randomly it might not be profitable.
Title: Re: Guess the day
Post by THUDandBLUNDER on Nov 17th, 2004, 5:48am

Quote:
The best way known to search in a sorted ordered list is binary search.
What about Fibonacci search?
Title: Re: Guess the day
Post by towr on Nov 17th, 2004, 7:36am

on 11/17/04 at 04:07:58, Bool wrote:
So even if the day is chosen randomly the only days which can be found out with in two guesses are wed, mon and fri which have a probability of 3/7 to be picked up as against 4/7 for others.
But wednesday is worth 3, so wednesday, monday and friday together are worth 5, vs -4 for the other days, which gives an expected profit of 1/7th.

However if the day isn't chosen randomly but f.i. always thursday, then a binary search will always cost you (expected payoff is -1).
Title: Re: Guess the day
Post by Bool on Nov 17th, 2004, 9:26pm
ThudandBlunder, not sure what a fibonacci search is!!

Towr, what you said is right.

I think the clue lies in the statement
"Would you be willing to play this game a few dozens of times with me? "
Title: Re: Guess the day
Post by Barukh on Nov 19th, 2004, 1:46am
Hmm, I am not sure if I would dare to play against such a clever opponent as Jock...  ;D

I doubt the winning strategy exists, but why did Jock ask: “What would your guessing strategy be?”

Anyway, consider that Jock plays according to the following strategy: pick up a day according to the following probabilities: Sat, Sun = 5/24, Tue, Thu = 1/8, Mon, Wed, Fri = 1/9. Do you see the non-loosing strategy against this? I don’t…  :-/
Title: Re: Guess the day
Post by JocK on Nov 20th, 2004, 1:15pm
OK Barukh, I have to make it a bit trickier for you. :)

Would you be willing to play, if I pay you $0.10 upfront for each guessing game you play against me?
Title: Re: Guess the day
Post by Grimbal on Nov 20th, 2004, 5:11pm
come on, make it $0.11111...
Title: Re: Guess the day
Post by JocK on Nov 21st, 2004, 6:25am
OK Grimbal, well done.

hint for reaching Grimbal's result :: [hide]weekend days count twice...[/hide] ::
Title: Re: Guess the day
Post by Grimbal on Nov 21st, 2004, 11:54am
Hm... I don't know if there is a trick to get to that result, but here is what I did.
::[hide]
I analyzed it as a standard zero-sum game.

To create the payout matrix, the "chooser" side has 7 possibilities, a number from 0 to 6.   The "guesser" side is more difficult, he has to decide in one shot all the decisions.

A pure strategy for the guesser consists of a tree of all the decisions he is going to make depending on the answers.  For instance: start with 3, if smaller guess 1 then 0 or 2, if larger (than 3) guess 5 then 4 or 6.
I would write that strategy
   (3 (1 0 2) (5 4 6)) or 3102546
In the first notation, there are triplets.  The 1st item is what you guess, the 2nd is what you do if smaller, the 3rd what you do if larger.  
In the second notation, you just go from left to right, asking all the numbers that are still possible according to the previous answers.
Another strategy would be:
  (4 (1 0 (2 - 3)) (6 5 -)) or 4102365
(the - are placeholders for impossible situations)

Anyway, there are 7 pure strategies for the chooser, and 429 pure strategies for the guesser.  (it is the number of binary trees with 7 elements).  I computed the payout matrix for all these 7x429 possible plays.  For each number the "chooser" chooses and each strategy the "guesser" chooses to use, there is a payout of $3, $1, $-1, etc. according to the given rule.

In this game there is no saddle point.  I.e. there is no strategy for a player that has no counter-strategy for the other player.  Both players would keep trying to switch strategy to counter the other's strategy.  The way out of this is that the players adopt a mixed strategy, that is, play a number of strategies and choosing randomly among these.

Normally, there is an optimization algorithm that will sort out the strategies, remove some and come out with a square payout matrix.  It would then solve the matrix to get an optimal mixed strategy for each player.  I don't remember that algorithm.  I solved it heuristically, by adjusting repeatedly both player's choice of strategies by increasing the probability for those that may the most.  After a (large) number of iterations, 6 guessing strategies seemed more promising than the others.  I took these and solved the system by mixing these strategies to get a constant payout whatever the chooser chooses.

The result is:
strategy:probability
3102546  5/18
3012654  3/18
2015436  4/18
2014365  1/18
4102365  4/18
4201365  1/18

Which translates to:

start with 3 with probability 8/18, then
- guess 1 or 5 with probability 5/8
- guess 0 or 6 with probability 3/8
start with 2 with prob. 5/8, then
- if smaller, guess 0 and then 1
- if larger, guess 5 with prob. 4/5, and if smaller, guess 4
- if larger, guess 4 with prob. 1/5, and if larger, guess 6
start with 4 with prob. 5/8, then
- if larger, guess 6 and then 5
- if smaller, guess 1 with prob. 4/5, and if larger, guess 2
- if smaller, guess 2 with prob. 1/5, and if smaller, guess 0

This guarantees that the payout for the chooser is exactly $0.111... whatever he chooses.

For the chooser, I took these 6 guessing strategies and searched how to make the payout constant for all of them.
I actually would need 7, but the symetry pointed to one solution.
The chooser strategy that balance all of these payouts is:
choose any value 1..5 with 1/9 probability, or 0 or 6 with 2/9 probability.  That guarantees that whatever the strategy is used for guessing, the payout is not more than $-0.111...
[/hide]::
Title: Re: Guess the day
Post by JocK on Nov 21st, 2004, 3:43pm

on 11/21/04 at 11:54:19, Grimbal wrote:
The chooser strategy that balance all of these payouts is:
choose any value 1..5 with 1/9 probability, or 0 or 6 with 2/9 probability.  That guarantees that whatever the strategy is used for guessing, the payout is not more than $-0.111...
[/hide]::

Yes, that is what I hinted at: as 'chooser' select Saturday or Sunday each with probability 2/9, and the five weekdays each with probability 1/9. Agaist this 'chooser strategy' all guessing strategies yield an expected payout of -$1/9 (or worse).

So with this simple selection strategy you actually can play this game with a normal deck of cards. Just use the following 18 spotcards ranging from 2 till 8: 4 deuces (Club-2, Diam-2, Heart-2 and Spade-2), 4 eights (Club-8, Diam-8, Heart-8 and Spade-8 ), and 2 cards each of 3 till 7. Using these 18 cards each time you simply shuffle and randomly select a card. A guesser with some (intuitive) knowledge of binary searches might be tempted to try and beat the person who is so stupid to randomly select a card and will repetitively guess numbers from 2 till 8... :)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board