wu :: forums - Print Page


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

        riddles >> hard >> guess number for money 1
        
(Message started by: klbarrus on Jul 28^th, 2002, 1:25am)

Title: guess number for money 1
Post by klbarrus on Jul 28^th, 2002, 1:25am

1) should you play?

it depends, see #2

2) expected return?

using a binary search method, you'll always guess the number in 7 or fewer guesses since 2^7 > 100. You can expect to win $5 1 time, $4 2 times, 3$ 4 times, $2 8 times, $1 16 times, 0$ 32 times, and lose $1 the other 37 times. That works out to $20 for all possible games, or an expected return of 20 cents a game.

So it should like you should play... except I would say not!
My reasoning is your expected return is positive only if you trust the person to truly pick the numbers randomly. I think in reality, nobody is going to pick 50 and let you get $5 on the first guess, or pick 25 or 75 and let you get $4, etc. So a real person will not let you get $5, $4 or $3 by avoiding those numbers and that changes your expected return to losing $5 over the games selected or a loss of 5 cents a game.

So I think the answer to part 1 is a) yes if you beleive the person will pick numbers randomly, and b) no if you think they won't.

Title: Re: guess number for money 1
Post by rugga on Jul 28^th, 2002, 3:46am

This was exactly my thinking. But I think the game could
be quite interesting if you assume the first person does
not pick randomly. Then what is the best number to pick?
1 or 100 will usually result in 7 guesses, but if the 2nd person
is clever they might start by guessing 100 on the chance they'll
pick up $5 that way. Also note that the 2nd person has some
freedom in how they do their binary search since 100 < 127.
For example, the first guess doesn't have to be 50. It could be
anywhere from 36 to 64 without changing the guarantee of
getting it in 7 guesses (i.e. you can still do a binary search of
the remaining numbers in at most 6 guesses as long as there
no more than 63 numbers remaining).
I saw this problem a couple years ago and tried to figure
out the optimal mixed strategy for both sides, but it got
somewhat complicated so I put it aside. But I'd be interested
to know if anyone has worked on it.

Title: Re: guess number for money 1
Post by Frost on Jul 28^th, 2002, 5:02am

I'd choose to play it this way:

me:"50" he:"lower"
me:"25" he:"lower"
me:"12" he:"lower"
me:"6": he:"lower"
me:"3" he:"lower"
me:"Nice game. You win."

Title: Re: guess number for money 1
Post by Some random dude on Dec 14^th, 2002, 3:51am

I don't want to be a monstrous dunderhead, but since the accordian scale of payouts reverses itself, can't you just guess wrong until you are back to +5 for you?

Does the payout work like this: 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5?

If so, once I determined the number, I would just guess wrong until I can get the fiver on the 21st guess.

That's how I read the question, anyway.

Title: Re: guess number for money 1
Post by TimK on Oct 18^th, 2004, 12:15pm

Yeah, I don't see why that doesn't work. Can't you guess 50 the first 20 times, and then guess 25 or 75 the next 20, and so on? Then you always win $5.

Title: Re: guess number for money 1
Post by rmsgrey on Oct 19^th, 2004, 8:41am

Guessing the same number 20 times in a row seems a little silly - if your first guess is 50, and the response is "lower", then you can cheerfully guess "51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 25"

It's only after your 5th real guess that you start having to repeat numbers to avoid accidentally winning less than $5...

Title: Re: guess number for money 1
Post by JocK on Nov 6^th, 2004, 5:09am

on 12/14/02 at 03:51:47, Some random dude wrote:

Does the payout work like this: 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5?

I think the intention of the poster was a payout behaving like: 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, ...

Title: Re: guess number for money 1
Post by rmsgrey on Nov 6^th, 2004, 6:07am

Since it's an interview question originally (click on the problem statement to link to the problem statement on the main site) it probably did mean that the payout came back positive again after a while.

Title: Re: guess number for money 1
Post by JocK on Nov 6^th, 2004, 6:33am

The payout mentioned in the problem statement (no negatives!) makes it absolutely trivial. Even with cycling positive and negative payouts, the problem is boring. So let's focus on the payout scenario: 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7, ... that creates an interesting game-theoretical problem.

To get a feel for this problem, I played a bit with the more managable problem in which you have to select from only three numbers: 1, 2 and 3. The payout is $1 if you guess right the first time, $0 if you guess right the second time, and -$1 ($1 penalty) if your guess right at the third guess.

The person initially selecting the number has to apply a random strategy for making the selection. The best he/she can do is to select the numbers 1 and 3 both with probability 0.4, and the number 2 with probability 0.2.

In this case, the person guessing the number has an expected payout of $0.20.

I have to think a bit longer about the case in which one can select from many more (up to 100) numbers.

Title: Re: guess number for money 1
Post by JocK on Nov 9^th, 2004, 2:07pm

on 11/06/04 at 06:33:44, JocK wrote:

... you have to select from only three numbers: 1, 2 and 3. The payout is $1 if you guess right the first time, $0 if you guess right the second time, and -$1 ($1 penalty) if your guess right at the third guess.

The person initially selecting the number has to apply a random strategy for making the selection. The best he/she can do is to select the numbers 1 and 3 both with probability 0.4, and the number 2 with probability 0.2.

In this case, the person guessing the number has an expected payout of $0.20.

Actually, for this three number game, one can demonstrate that:

A) the person initially selecting the number can not on average lose more than $0.20 per game when he selects the middle number 20% of the time, and the two other numbers each with frequency 40% irrespective of what (probabilistic) guessing strategy the other player uses, and:

B) the person guessing the number can not on average gain less than $0.20 per game when she starts by guessing the middle number with frequency 60%, and the two other numbers each with frequency 20%; and in case this latter guess is wrong, always selects the other most extreme number as a second guess. This holds irrespective of the (probabilistic) number selection strategy the other player uses.

Hence, assuming rational play of the opponent, both players can not improve their expected result by changing their strategy, and therefore the above set of strategies represents the Nash equilibrium for this game.

I have no clue how to extend this to the case of 100 numbers...