Author |
Topic: HARD: GUESS NUMBER FOR MONEY I (Read 4565 times) |
|
S. Owen
Full Member
Gender: 
Posts: 221
|
 |
HARD: GUESS NUMBER FOR MONEY I
« on: Jul 26th, 2002, 9:31am » |
 Quote  Modify
|
What do you guys think of this answer:
It seems that one has to try to guess the number using binary search (i.e. guess 50, then 25 or 75 depending on whether that's high or low, etc.).
So if the number is 50, you get $5. If it's 25 or 75, you'll get $4. Similarly there are four possibilitites for which you will get $3, 8 - $2, 16 - $1, 32 - $0, and the remaining 37 - $-1.
So adding it up, your expected result is +$0.20 per game. You should play.
However this assumes that the gamer is picking numbers at random. Knowing you are binary searching, he could always pick a value that you'll only reach in 7 guesses (like 1). So maybe we can't assume that.
You can add some unpredictability to your binary search by breaking ties in different ways (25 is too high? do you pick 12 or 13 next? the gamer can't know) and still have a binary search.
Sounds like some complicated implications that I haven't worked out... any ideas.
|
|
 IP Logged |
|
|
|
Guest
Guest
|
|
Re: HARD: GUESS NUMBER FOR MONEY I
« Reply #1 on: Jul 26th, 2002, 1:26pm » |
Quote Modify
 Remove
|
If the problem statement is really meant to say "5 4 3 2 1 0 1 2 3 4 5 4 3 2 1 0 1 2 ...", then I can win with an expected gain of $5.
Perform a modified binary search. Each time the payoff is +5, search as usual. When the payoff is anything else (9 times out of 10), make sure that you guess wrong. You'll easily have enough known wrong numbers to complete the search.
If this is the correct sequence, but you are required to guess a number not known to be incorrect, it's a tough problem... seems there should be some way to improve expected gain.
Otherwise, I'm confident that srowen's answer is correct.
Cheers.
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: HARD: GUESS NUMBER FOR MONEY I
« Reply #2 on: Jul 26th, 2002, 2:06pm » |
Quote Modify
|
Yeah, I thought that was a typo at first, but maybe not!
If not then you have the right answer - guess "50" on the first round. If you're right, hey, $5. If not, guess "50" (which is definitely wrong) until the payoff is $5 for you again. Then try your next binary search value, like 25. If it's 25, hey, $5. Etcetera... eventually you get $5.
|
|
IP Logged |
|
|
|
Nicodemus
Guest
|
|
Re: HARD: GUESS NUMBER FOR MONEY I
« Reply #3 on: Jul 27th, 2002, 1:54pm » |
Quote Modify
Remove
|
I would argue that the problem is vague because of the inclusion of that strange parenthetical number sequence. The text of the problem makes no mention of returning to profitability after a certain number of guesses, describing only a descending sequence. The list of numbers contains no minus signs, either.
The solution I came up with was the same as srowen's, though I admit I didn't work through all the math to check that it's +0.2. 
|
|
IP Logged |
|
|
|
Frost
Newbie
Posts: 14
|
|
Re: HARD: GUESS NUMBER FOR MONEY I
« Reply #4 on: Jul 28th, 2002, 3:33am » |
Quote Modify
|
I agree this question is a bit ambiguous.
Without the sequence going up again, I'd never make more than 5 guesses. Making more guesses would not result in profit. And what if I guess it right first time, then guess it right again on my second turn? Do I get $9?
|
| « Last Edit: Jul 28th, 2002, 4:01am by Frost » |
IP Logged |
|
|
|
TheBean
Guest
|
|
Re: HARD: GUESS NUMBER FOR MONEY I
« Reply #5 on: Jul 28th, 2002, 11:19pm » |
Quote Modify
Remove
|
I'm guessing the payoff sequence was a typo... maybe, maybe not. If it is and you use a binary search, then the payoff for a RANDOM number appears to me to be $87 per 100 trials, or a little less than a buck...
One complication...
If the person thinking of the number deliberately chooses numbers in the 'cracks' of a binary search, and the search strategy is unchanged, then the payoff rapidly recedes to negative numbers.
For example, the number is 12, and your guesses are
50 (high), 25(high), 13(high), 7(low), 10(low), 11 (low), 12(match for a payout of -1). Your sequence may vary, depending on what you consider a binary search sequence, but there are numbers to choose that will always yield a negative result.
Modifying your search strategy prevents you from losing consistently, but still proabably yields a negative result, or at least increases the chance that you will choose incorrectly.
|
|
IP Logged |
|
|
|
Frost
Newbie
Posts: 14
|
|
Re: HARD: GUESS NUMBER FOR MONEY I
« Reply #6 on: Jul 29th, 2002, 3:43am » |
Quote Modify
|
The game will never end, if you don't get it right before your 7th guess.
An example, the number-to-guess being 12 again:
50 (high), 25(high), 13(high), 7(low), 10(low), 11 (low), 11(low), 11(low), 11(low), ... 11 ad infinitum.
If you'd ever 'guess' 12, you'd loose money. So you don't.
You average gain:
( 1*5 + 2*4 + 4*3 + 8*2 + 16*1 + 32*0 + 37*0 ) / 100 = $0.57
|
|
IP Logged |
|
|
|
Frost
Newbie
Posts: 14
|
|
Re: HARD: GUESS NUMBER FOR MONEY I
« Reply #7 on: Jul 29th, 2002, 3:50am » |
Quote Modify
|
Additional note:
The riddle does not state the game ends if you guess right, so your average profit may also be:
( 1*(5+4+3+2+1) + 2*(4+3+2+1) + 4*(3+2+1) + 8*(2+1) + 16*1 + 32*0 + 37*0 ) / 100 = $0.99
|
|
IP Logged |
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: HARD: GUESS NUMBER FOR MONEY I
« Reply #8 on: Jul 29th, 2002, 5:04am » |
Quote Modify
|
I'm working on the assumption that the parenthesized sequence is wrong since it does not match the definitive text. An internally-inconsistent problem is a boring problem.
I'm not assuming you have to pick a different number every time. If you extend the game indefinitely, your liability increases indefinitely. It is thus not in your interest to deliberately extend the game.
To begin with I assume a uniform distribution of selected numbers, so as to get a "best case". At best, the game has a value of $0.20 as srowen calculated.
Yes, an adversary can pick some other distribution to increase the number of guesses you need. This can only be a shift toward the edges though, since your initial guess can be anywhere from 37 to 64 and remain perfectly binary. That's enough to eliminate fine detail from the interior of the adversary's distribution.
There is no single ideal distribution from which you can calculate a long-term game value. It is in both sides' interest to use mixed strategies for picking and guessing. I've got a computer program crunching probabilities to find a good set of strategies right now. So far, it looks like the game is still in the guessers favour, with a net value of about $0.10 to $0.13.
That shouldn't be taken as gospel though -- it is subject to the whims of the heuristic search gods, and they can be mightily fickle at times. I personally doubt that anyone will ever determine the exact value of the game.
By the way, I noted that this problem doesn't have a ">=P" mark on it. Does that mean William actually knows the exact solution!? I find that hard to believe. I would like to be proven wrong, preferably by seeing the exact solution myself 
|
|
IP Logged |
|
|
|
Frost
Newbie
Posts: 14
|
|
Re: HARD: GUESS NUMBER FOR MONEY I
« Reply #9 on: Jul 29th, 2002, 6:18am » |
Quote Modify
|
Consider this snippet from the question:
Quote:
... If you get it right on the ... seventh guess you owe me $1 ... |
|
Your dept only rises if you guess right (after turn six).
You can keep your liability at a constant $0 indefinitely.
|
|
IP Logged |
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: HARD: GUESS NUMBER FOR MONEY I
« Reply #10 on: Jul 29th, 2002, 5:14pm » |
Quote Modify
|
The timing of the payoff matters not at all for calculating the value of a multi-stage strategy. The game as presented is mathematically equivalent to a game in which you are initially given $6, and have to pay $1 per guess. This equivalence transformation does not change the value of the game, it merely makes it more obvious that postponement is a losing strategy.
Another equivalent way to look at it is to find the limit for a game limited to n turns, as n increases. This defines the value of the infinite game, and again the postponement strategy has unbounded negative value.
If you can show me a self-consistent theory in which the value of an infinite postponement strategy is non-negative, I'd like to see it.
|
|
IP Logged |
|
|
|
Frost
Newbie
Posts: 14
|
|
Re: HARD: GUESS NUMBER FOR MONEY I
« Reply #11 on: Jul 30th, 2002, 1:15am » |
Quote Modify
|
In the riddle you pay/get $(5-numturns) for a right guess.
This is not the same as initially getting $6 and paying $1 for any guess.
The condition 'when you make any guess' always occurs.
The condition 'when you make the right guess' may not exists at all.
Deliberately guessing wrong all the time = the game is a draw, like playing chess with just the kings.
|
|
IP Logged |
|
|
|
continuum
Newbie
 
Gender:
Posts: 14
|
|
Re: HARD: GUESS NUMBER FOR MONEY I
« Reply #12 on: Sep 30th, 2002, 8:57pm » |
Quote Modify
|
Frost, assuming that the problem is in fact as you claim, I think it would be smarter to stop guessing and leave. 
It remembers me of the proposal of paying for break eggs on the head of another person:
"I break two eggs on your head and pay you $100 after... What do you say?"
Then you break one (and only one) egg on the head of the naive guy and go away. One day, if you feel like it, you could break the second egg and pay $100.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print