How to Consistently Win the High-low Game

“We’re going to play a game. I’m going to pick a number between 1 and 100, you get to guess the number. If you don’t get it, I’ll tell you if you’re too high or too low. If you guess it, I’ll pay you $6 less the number of guesses that you take - so if you get the number on the first guess, you get $6, but if you take 7 guesses, you pay ME $1. Now do you want to play the game or not?”

Whether you want to play will depend on your desires. Instead of answering that question, let’s consider who is more likely to win or, in other words, who will make money if you play over and over.

Unless you’re very lucky, you will occasionally lose. Flipwise, if Balmer gets lucky, he’ll always win. On average though, even if Balmer knows your strategy you can consistently win. How much? Over time, a cent or two per game.

To win the game, we should know the rules. The discription isn’t too detailed, so let’s make explicit what was implicit. First, let’s consider the winnings calculation. “i’ll pay you $6 less the number of guesses that you take .. but if you take 7 guesses, you pay ME $1” means that:

• We receive $6 if the first guess is correct.
• We receive a doller less for each subsequent guess.
• If we guess correctly after six tries, we get $1.
• If we guess correctly on the seventh try, we give Balmer a dollar. That’s the exception.
• If you use a binary search, you’re sure to stop there. But we won’t so let’s continue passed the execptional case. If there were no exception, then the seventh try would be the break even point. So after eight guesses, we owe Balmer $1.
• After nine guesses we owe $2, etc.

Now let’s start look at strategy. “to pick a number between 1 and 100” means that:

• 1 is a valid choice.
• 100 is a valid choice.
• Balmer can use any strategy including strategies where he knows ours.

As a consequence, if a strategy has a positive expected outcome for every choice of number, then regardless of what secret number he picks he’ll lose more often than he wins.

Beating Balmer

Our strategy is pretty simple. We start with a fair binary search. Sometimes there are two numbers equally distant from the midpoint of the known high and low. When this happens, we’ll chose one randomly. For example, on the first try, the midpoint between 1 and 100 is 50.5; so half of the time we’ll guess 50 and half of the time we’ll guess 51.

Unfortunately, binary search is not a winning strategy. Balmer can beat it. Four numbers: 1, 24, 77, and 100 are wins for Balmer. Their approximate expected values, in cents, are -15, -3, -3, and -15 cents respectively. We approximate the expected values by running a simulation in Ruby. For each possible secret number, we play the game 100,000 times. Since random choice is involved, our expected values are slightly off from the true values.

To achieve a winning strategy we need to guess 1, 24, 77, and 100 a little more often. We have to do this without, guessing any other number too infrequently. One way to do this is by not always choosing the midpoint for our next guess in the binary search. In particular, as soon as we have five or fewer numbers between our highest and lowest guesses, we pick the remaining midpoints randomly. This gives 1, 24, 77, and 100 positive expected values. Under the worst cicumstances, it will take us nine guesses to find Balmer’s number. But by occationally giving Balmer a double win of $2, we are able to ensure that he loses in the long run.

With the winning strategy, Balmer’s best bets are on 2, 27, 74, and 99. Both 27 and 74 yield a hefty 8 cents on average, but 2 and 99 only yield a little less than two cents. And that, friends, is my two cents. Here is a chart showing the expected values of each number for the simply binary search strategy as well as the adjusted winning strategy.