BEAM Los Angeles has started a math team! The goal is for students to have fun doing challenging math problems, but also to be prepared to participate in math competitions once pandemic closures lift. Some weeks students work on a specific math competition, and other weeks they focus on particular kinds of problems that often appear in math competitions, like the one below, which involves a guessing game. See how you do! (And if you like this sort of challenge, you should also check out this problem from last summer's newsletter.)
You may have played this game before: I am thinking of a number between 1 and 1000; try to guess my number in as few guesses as possible. Each time you guess, I will tell you whether my number is greater than or less than your guess. What is the best strategy so that you are guaranteed to find the correct number with as few guesses as possible?
In this case, the answer is fairly straight forward and not too difficult.
But what if we add a twist: You are allowed to say three numbers in each guess, and I will tell you whether my number is greater than or less than each. Now what is the optimal strategy to find the correct answer in as few guesses as possible? What if instead, I let you ask three yes/no questions each time? Would you use the same strategy?
Let's start with our initial question. If you want to guess a number from 1-1000 in as few guesses as possible and you can make one guess at a time, what's the best way to do it?
One way to think about this is that when you guess a number, call it x, you turn your original problem (searching for a number 1-1000) into a smaller problem: either searching 1-(x-1) or (x+1)-1000. If one of these ranges is too big, and we get unlucky and our number is in that larger range, then we will have more guesses to do! Hence, a good strategy is to always divide the range in half (or as close in half as we can). That way, no matter which half we end up in, the worst case is under control.
Hence, the first time you'd guess 500. If you're over, then you need to check 1-499; if you're under, you need to check 501-1000. (You could also have guessed 501, in which case you'd get ranges that are the same size.) Keep splitting in half. In total, it will take you no more than ten guesses.
In fact, it turns out that 10 guesses is enough to go higher than 1000. One way to look at this is by building up from smaller values. To guess a number 1-3 requires two guesses (your first guess would be 2, and then you might need to guess either 1 or 3 depending on if you were over or under). To guess a number 1-7 thus requires three guesses: start by guessing 4, and then you're left with two ranges of size three (1-3 or 5-7), which you know you can do in two guesses no matter which range it turns out to be. Guessing a number 1-15 requires four guesses (guess 8, and now you've reduced to a range of size 7 which you can do in three more guesses); 1-31 requires five; and so forth.
Notice the nice pattern: with n guesses, you can do a range of size 2n-1. That makes sense, because each guess basically lets you double the range you can check. So with 10 guesses, you could do 210-1 = 1023 numbers. This search strategy is called binary search and comes up all the time in computer science.
Sidebar: Extra credit: This also exposes a neat pattern: if you double one less than a power of two and then add 1, you get one less than the next power of two. Written with an equation, that's 2(2n-1)+1 = 2n+1-1.
So what happens when we get to name three numbers at a time? When we only guessed one number, it would split our range into two subranges (less than or greater than the number we guessed). Now, knowing if the target is greater or smaller than each of three numbers splits our original range into four subranges. We might be smaller than all three numbers, between the lowest and the next two, between the lowest two and the highest, or above the highest.
Effectively, this allows us to take two steps at once: instead of guessing just the number in the middle, we can guess the number in the middle and the number in the middle of both of the possible resulting ranges. Thus, instead of needing 10 guesses, we only need 5 guesses.
This might be surprising. After all, you're guessing three times as many numbers; maybe you would have expected to only need a third as many rounds of guessing. However, because you have to pick all three at first (without knowing the answer to your first guess), you can't do quite as well.
Sidebar: Extra credit: We can also build things recursively like before. We can do 1-3 in one round by just guessing 1, 2, and 3; we can do 1-15 in two rounds by guessing 4, 8, 12 — the resulting range is going to be of size 3, so we can finish it off next round. And so on. The next step would be 15x4 (the four ranges) plus 3 (the three numbers you guess) which would be 63. You'd guess 16, 32, and 48, and whatever range the target number was left in would be size 15, which you can now do in two guesses. The relationship here is that 4(4n - 1) + 3 = 4n+1-1.
So, you'd expect the same with asking three yes/no questions, right?
Well, this is the neat part, and why we decided to highlight this problem. With yes/no questions, you have more flexibility than just "is the number too high or too low." Now you can ask questions whose answers are actually independent of each other, and truly cut your search space in half with each guess. (As an example of two independent questions, you could ask: "Is the number bigger than 500?" and "Is the number even?" Both answers cut your search space in half no matter what order you ask them in.)
So how can we come up with three questions that are all independent of each other? That's actually not too hard if you know binary numbers. For example, written in binary, the number 953 is 1110111001, because 953 = 29 + 28 + 27 + 25 + 24 + 23 + 20 — a power of 2 for each place there's a 1. To turn these into questions, just ask:
Is the units digit in binary a 1?
Is the 2's digit in binary a 1?
Is the 4's digit in binary a 1?
Is the 8's digit in binary a 1?
...
Is the 512's digit in binary a 1?
In total, that's 10 questions you need to ask, one for each binary digit, and then you know the number. That means we have to do four rounds in total. Three questions in each of the first three rounds, and then one more question to finally know the number. But now that we have arbitrary yes/no questions, it really does mean we only need a third as many rounds (rounding up).