wu :: forums - Print Page


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

        riddles >> hard >> HARD: GUESS NUMBER FOR MONEY I
        
(Message started by: srowen on Jul 26^th, 2002, 9:31am)

Title: HARD: GUESS NUMBER FOR MONEY I
Post by srowen on Jul 26^th, 2002, 9:31am

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.

Title: Re: HARD: GUESS NUMBER FOR MONEY I
Post by Guest on Jul 26^th, 2002, 1:26pm

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.

Title: Re: HARD: GUESS NUMBER FOR MONEY I
Post by srowen on Jul 26^th, 2002, 2:06pm

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.

Title: Re: HARD: GUESS NUMBER FOR MONEY I
Post by Nicodemus on Jul 27^th, 2002, 1:54pm

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. :)

Title: Re: HARD: GUESS NUMBER FOR MONEY I
Post by Frost on Jul 28^th, 2002, 3:33am

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?

Title: Re: HARD: GUESS NUMBER FOR MONEY I
Post by TheBean on Jul 28^th, 2002, 11:19pm

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.

Title: Re: HARD: GUESS NUMBER FOR MONEY I
Post by Frost on Jul 29^th, 2002, 3:43am

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

Title: Re: HARD: GUESS NUMBER FOR MONEY I
Post by Frost on Jul 29^th, 2002, 3:50am

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

Title: Re: HARD: GUESS NUMBER FOR MONEY I
Post by tim on Jul 29^th, 2002, 5:04am

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 ;)

Title: Re: HARD: GUESS NUMBER FOR MONEY I
Post by Frost on Jul 29^th, 2002, 6:18am

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.

Title: Re: HARD: GUESS NUMBER FOR MONEY I
Post by tim on Jul 29^th, 2002, 5:14pm

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.

Title: Re: HARD: GUESS NUMBER FOR MONEY I
Post by Frost on Jul 30^th, 2002, 1:15am

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.

Title: Re: HARD: GUESS NUMBER FOR MONEY I
Post by continuum on Sep 30^th, 2002, 8:57pm

Frost, assuming that the problem is in fact as you claim, I think it would be smarter to stop guessing and leave. ;D

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.