Author 
Topic: HARD: GUESS NUMBER FOR MONEY I (Read 4087 times) 

S. Owen
Full Member
Gender:
Posts: 221


HARD: GUESS NUMBER FOR MONEY I
« on: Jul 26^{th}, 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 26^{th}, 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 26^{th}, 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 27^{th}, 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 28^{th}, 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 28^{th}, 2002, 4:01am by Frost » 
IP Logged 



TheBean
Guest


Re: HARD: GUESS NUMBER FOR MONEY I
« Reply #5 on: Jul 28^{th}, 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 29^{th}, 2002, 3:43am » 
Quote Modify

The game will never end, if you don't get it right before your 7th guess. An example, the numbertoguess 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 29^{th}, 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 29^{th}, 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 internallyinconsistent 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 longterm 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 29^{th}, 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 29^{th}, 2002, 5:14pm » 
Quote Modify

The timing of the payoff matters not at all for calculating the value of a multistage 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 selfconsistent theory in which the value of an infinite postponement strategy is nonnegative, I'd like to see it.


IP Logged 



Frost
Newbie
Posts: 14


Re: HARD: GUESS NUMBER FOR MONEY I
« Reply #11 on: Jul 30^{th}, 2002, 1:15am » 
Quote Modify

In the riddle you pay/get $(5numturns) 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 30^{th}, 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 



