26 Feb 08
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?
27 Feb 08
3 edits
Originally posted by doodinthemoodI 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.
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.
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.
27 Feb 08
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.
27 Feb 08
1 edit
Originally posted by doodinthemoodThat'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.
You cannot guess the referee, so it's best to assume complete randomness in their selection.
[EDIT]
Scratch that. I misread the question. Back to the drawing board...
27 Feb 08
Originally posted by mtthwthen you are assuming the referee will just pick numbers at random and not use any kind of game theory?
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.
27 Feb 08
2 edits
Originally posted by mtthwOK. Assuming the referee also chooses randomly (with a flat distribution), the simulation indicated an optimal value of around 40.
Scratch that. I misread the question. Back to the drawing board...
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?
28 Feb 08
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?
28 Feb 08
Originally posted by mtthw42 is also the answer to the ultimate question..... Coincidence??
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?
I THINK NOT.....
28 Feb 08
Originally posted by doodinthemoodRight, 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.
Is it a big enough difference for it to mean anything? Could be. What's your mathematical justification for 42 though?
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
28 Feb 08
Originally posted by preachingforjesusthis 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
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.
29 Feb 08
2 edits
Originally posted by AetheraelWhen 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.
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
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. 🙂