# 1 in 100, with a twist

PBE6
Posers and Puzzles 26 Feb '08 20:50
1. PBE6
Bananarama
26 Feb '08 20:50
Suppose you are playing a game that involves yourself, your opponent, and a referee. The rules of the game are as follows:

1. Each person picks a number between 1 and 100, and keeps it secret.
2. Once all 3 numbers have been picked, they are revealed.
3. The person who comes closest to the referee's secret number without going over wins. If both players go over, or if both players tie, the game is repeated until there is a winner.

By symmetry, each player has an equal chance of winning this game. However, assuming your opponent doesn't have time to work out a strategy of his/her own and picks at random, is there a number you can pick to maximize your chances of winning?
2. 26 Feb '08 21:18
If you take means, the referee will pick 50.5 and your opponent will pick 50.5
In order to win, you need to consistently pick 50.5.
So your tactic should be alternating between picking 50 and 51, really. After that, it's completely luck.
3. uzless
The So Fist
27 Feb '08 18:023 edits
Originally posted by doodinthemood
If you take means, the referee will pick 50.5 and your opponent will pick 50.5
In order to win, you need to consistently pick 50.5.
So your tactic should be alternating between picking 50 and 51, really. After that, it's completely luck.
I assume here that the referee is not some kind of mechanical random number generator which means it is highly unlikely he will be pick the number 1 since this would defeat the purpose of the game for the most part.

It seems the key here is to figure out the most likely number the referee would choose since the referee knows the rules of the game.

You have to combine straightforward statistical analysis with an educated guess as to how the referee would think.

I suggest that is unlikely the ref would choose a number below say 10 because it's likely that both players will choose a number higher than that.

If the game were played only once, and I was the referee, I would choose a number higher than 50 (in the hopes that at least one player guessed less than 50 and a winner will result), so if i were a player, my guess would be less than 50 but more than 10.

35-45 would seem to be a best guess.
4. 27 Feb '08 19:25
And if I was referee I'd like being annoying and pick something like 14 to make both guessers feel insecure with their over-guessing.
In that case it would be best to guess 10.

I can also imagine a referee who would want a winner, but just scrape off the overambitious guesses. A referee who would pick a number in the 80s, wherupon the best guess would be something like 75.

You cannot guess the referee, so it's best to assume complete randomness in their selection.
5. 27 Feb '08 21:321 edit
Originally posted by doodinthemood
You cannot guess the referee, so it's best to assume complete randomness in their selection.
That's the approach I was taking. I'm not convinced the argument is quite as simple as you suggest - to prove it you have to worry about the average difference between random numbers.

[EDIT]

Scratch that. I misread the question. Back to the drawing board...
6. uzless
The So Fist
27 Feb '08 21:42
Originally posted by mtthw
That's the approach I was taking. I'm not convinced the argument is quite as simple as you suggest - to prove it you have to worry about the average difference between random numbers.

But, on the other hand, a simulation I just ran suggests 50/51 is still the right answer.
then you are assuming the referee will just pick numbers at random and not use any kind of game theory?
7. 27 Feb '08 21:57
Originally posted by uzless
then you are assuming the referee will just pick numbers at random and not use any kind of game theory?
Why would the referee use game theory? The referee isn't playing the game.
8. 27 Feb '08 23:152 edits
Originally posted by mtthw
Scratch that. I misread the question. Back to the drawing board...
OK. Assuming the referee also chooses randomly (with a flat distribution), the simulation indicated an optimal value of around 40.

I've also got an analytic solution (that I don't trust - think I've found a flaw) that suggests 42, but it's a little complicated to write up right now.

Further edit...

I trust it a bit more now. If you can allow any number in [0, 100] (so don't bother restricting to integers - because it makes the maths easier), then I think the best guess is:

100(2 - sqrt(2.5)), or approx. 41.9

Any good?
9. 28 Feb '08 07:36
oooh, explain where this has come from?

I'll do a quick test of 42 vs 51:
Out of 100 trials...
42 won 28 times
50 won 22 times

you might be on to something.

Out of 200 trials...
42 won 46 times
50 won 43 times

Is it a big enough difference for it to mean anything? Could be. What's your mathematical justification for 42 though?
10. Mexico
Quis custodiet
28 Feb '08 07:39
Originally posted by mtthw
OK. Assuming the referee also chooses randomly (with a flat distribution), the simulation indicated an optimal value of around 40.

I've also got an analytic solution (that I don't trust - think I've found a flaw) that suggests 42, but it's a little complicated to write up right now.

Further edit...

I trust it a bit more now. If you can allow any num ...[text shortened]... asier), then I think the best guess is:

100(2 - sqrt(2.5)), or approx. 41.9

Any good?
42 is also the answer to the ultimate question..... Coincidence??

I THINK NOT.....
11. 28 Feb '08 11:24
Originally posted by doodinthemood
Is it a big enough difference for it to mean anything? Could be. What's your mathematical justification for 42 though?
Right, here's my approach. Bear with me! Let's say I pick x, my opponent picks y, and the referee picks r. I'm assuming y and r have evenly spread random distributions.

I'm also going to consider the case where the numbers are real numbers between 0 and 1, rather than integers between 1 and 100. Exactly the same approach will work in the latter case, but it's more fiddly. The answer will be pretty close.

I win if: x < r < y (case A), or y < x < r (case B)
I lose if: y < r < x (case C), or x < y < r (case D)
Otherwise we try again.

For a particular r, the probabilities of the four cases are:
P(A): (1 - x)(1 - r)
P(B): (1 - x)x
P(C): xr
P(D): (1 - x)(r - x)
(Think about picking a valid value of r, and then a valid value of y)

P(win) = P(A) + P(B) = 1 - r + xr - x^2
P(loss) = P(C) + P(D) = x^2 - x + r

But that's for a particular value of r. For the expected probabilities, we average over all possible values of r (i.e. integrate from 0 to 1 - in the discrete case we have to sum from 1 to 100)

P(win) = 0.5 + 0.5x - x^2
P(loss) = x^2 - x + 0.5

We can maximise our chances of winning first time by picking 0.25. But we need to maximise our chances of winning eventually. This is given by

P(overall win) = P(win)/[P(win) + P(loss)] (an exercise for the reader ðŸ™‚)

= (0.5 + 0.5x - x^2)/(1 - 0.5x)

This has a maximum (differentiate, equate to zero) at 2 - sqrt(2.5), or approx 0.42. Your chance of winning is about 0.675
12. 28 Feb '08 11:25
Of course, the next question is what your strategy is if your opponent has had time to think about it! That's where the game theory really comes in...
13. 28 Feb '08 18:07
The big flaw in this analisys is that the reeree might pick randomly, but the oponent does not.

you are trying to beat a human opponent who is trying to beat you; if you pick 42 three times, the fourth time he picks 43 and wins.
14. 28 Feb '08 18:25
Originally posted by preachingforjesus
The big flaw in this analisys is that the reeree might pick randomly, but the oponent does not.

you are trying to beat a human opponent who is trying to beat you; if you pick 42 three times, the fourth time he picks 43 and wins.
this is what mtthw just said... the original question involved your opponent not coming up with any sort of strategy and just picking numbers at random. you're right though - especially for the "tie" cases it seems unlikely that if you tied 6 times in a row the opponent wouldn't catch on and guess 43
15. 29 Feb '08 09:252 edits
Originally posted by Aetherael
this is what mtthw just said... the original question involved your opponent not coming up with any sort of strategy and just picking numbers at random. you're right though - especially for the "tie" cases it seems unlikely that if you tied 6 times in a row the opponent wouldn't catch on and guess 43
When you take this into account, an optimal solution will take the form of a probability distribution - you need to pick randomly, but with a bias towards the more effective numbers (so with a maximum probability somewhere around 42, probably). You then assume your opponent has an identical strategy.

So now all those 'simple' probabilities take the form of integrals. E.g., instead of:

A: (1 - x)(1 - r)

you'll have

A: Integral[r to 1] (1-x)p(y)dy, where p(y) is your distribution.

Carry on like this, and you'll probably have some nasty integral equation that I have no intention of trying to solve. ðŸ™‚