| You would want to be a un-optimal as possible for your opponent, so I
guess that means to leave as large a range as possible left for your
opponent to guess from.
Your first guess should be 1 or 100. From then on, whatever your
opponent guesses will divide the remaining numbers into one or more
contiguous ranges. You pick the range with the largest size, and
re-apply the same strategy to that: pick the highest or lowest number
of that range.
I assumed it's more important to make it difficult for your opponent
than to optimize your own chances of winning.
I have no idea how to prove this though.
|
| .1> I assumed it's more important to make it difficult for your opponent
> than to optimize your own chances of winning.
>
> I have no idea how to prove this though.
I think this strategy is correct, with a few minor changes, and I can sketch
out a proof. Three of them, in fact.
The changes are:
> Your first guess should be 1 or 100. From then on, whatever your
Always guess the high end of the range: I'd rather have a 1% chance of winning
$100 than a 1% chance of winning $1.
> contiguous ranges. You pick the range with the largest size, and
Since the MC is announcing high or low, you always know the range that contains
the answer. So always pick the number at the high end of this range.
sketch proof 1:
As described, this is a zero sum game. So giving information to your opponent
can't help you. Minimizing the information transfer is the correct strategy.
sketch proof 2:
An obvious strategy is binary search: always guess the middle of the current
range. If A and B both use this strategy, then probabilities of win on each
guess are given by this table:
round A B
1 1/100 99/100 * 1/50
2 99/100 * 49/50 * 1/25 ... * 1/12 or 1/13
...
Since the probability on each round are in approximate ratio 1:2, the sum must
be in the same ratio, so the final probability of winning is about
A = 1/3 B = 2/3
The opposite strategy is guessing the highest number in the valid range. If
both A and B follow this strategy, then probabilities of win are
round A B
1 1/100 99/100 * 1/99 = 1/100
2 98/100 * 1/98 97/100 * 1/97
...
These ratios are 1:1, so the sum is 1:1
I just stopped to fool around with the endgame, but it still looks like picking
the high end of the range is optimal.
sketch proof 3:
For any given guess, picking the high end maximizes expected return on this
guess. It also maximizes the range left to the opponent, so it maximizes the
probability that there will be another round. So this strategy is optimal
on any given round. Therefore it is optimal for the game.
As usual, I am ignoring the possibilities of collusion, signals and payoff
splitting by the contestants. As stated, the rules provide no advantage for
collusion anyway.
|
| Not a proof, but an intuitive guess:
Imagine a row of bins - one for each possible guess. Bin #1 is 1 slot wide.
Bin #2 is 2 slots wide, and so forth up to Bin #100 which is 100 slots wide.
The total range is the sum of all numbers from 1 to 100 (= 5050).
I think that a binary search within this space would be the optimal
dollar-weighted search strategy. If you were playing by yourself and were
being rewarded on how quickly you get the right answer, your first guess
should be in middle of the weighted range (2525). I think that this
corresponds to a bin number of about 70.
However, because this is a two-player game, the best way to win is to minimize
the odds that your opponent wins. That leads to the following strategy:
"Pick the highest number that has not already been eliminated."
This means that you should first guess $100. Your opponent still has a
large range to choose from (low odds that they will win). Their best
strategy, of course, would be pick 99. If they don't, then you have
an even better chance on your next guess.
Since it is *not* a goal of the game to finish quickly, the use of a binary
search probably does not apply and, in fact, gives away the *most* information
to your opponent!
-steve-
|