Author |
Topic: Guess the day (Read 828 times) |
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
 |
Guess the day
« on: Nov 13th, 2004, 4:03pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Guess the day
« Reply #1 on: Nov 14th, 2004, 2:41am » |
Quote Modify
|
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]
|
| « Last Edit: Nov 14th, 2004, 2:44am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Bool
Newbie
Gender:
Posts: 7
|
|
Re: Guess the day
« Reply #2 on: Nov 17th, 2004, 4:07am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Guess the day
« Reply #3 on: Nov 17th, 2004, 5:48am » |
Quote Modify
|
Quote:| The best way known to search in a sorted ordered list is binary search. |
|
What about Fibonacci search?
|
| « Last Edit: Nov 17th, 2004, 7:37am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Guess the day
« Reply #4 on: Nov 17th, 2004, 7:36am » |
Quote Modify
|
on Nov 17th, 2004, 4:07am, 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).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Bool
Newbie
Gender:
Posts: 7
|
|
Re: Guess the day
« Reply #5 on: Nov 17th, 2004, 9:26pm » |
Quote Modify
|
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? "
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Guess the day
« Reply #6 on: Nov 19th, 2004, 1:46am » |
Quote Modify
|
Hmm, I am not sure if I would dare to play against such a clever opponent as Jock... 
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… 
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Guess the day
« Reply #7 on: Nov 20th, 2004, 1:15pm » |
Quote Modify
|
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?
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Guess the day
« Reply #8 on: Nov 20th, 2004, 5:11pm » |
Quote Modify
|
come on, make it $0.11111...
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Guess the day
« Reply #9 on: Nov 21st, 2004, 6:25am » |
Quote Modify
|
OK Grimbal, well done.
hint for reaching Grimbal's result :: weekend days count twice... ::
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Guess the day
« Reply #10 on: Nov 21st, 2004, 11:54am » |
Quote Modify
|
Hm... I don't know if there is a trick to get to that result, but here is what I did.
::
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...
::
|
| « Last Edit: Nov 21st, 2004, 11:56am by Grimbal » |
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Guess the day
« Reply #11 on: Nov 21st, 2004, 3:43pm » |
Quote Modify
|
on Nov 21st, 2004, 11:54am, 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...
|
| « Last Edit: Nov 21st, 2004, 3:57pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print