Today’s first game needs no computer. It needs a partner, a marker and a whiteboard.
In class, we worked through this sequence of cards in pairs at the whiteboards.
If you were away
Find a partner, or play both roles with a random number, and work through the questions below in order. Each one builds on the one before it. Once you have an answer, expand the answer box to check it.
Play
One of you is the thinker. The other is the guesser.
Question 1
The thinker writes a whole number from 1 to 100 where the guesser cannot see it. The guesser says a number. The thinker says higher, lower or right. Keep a tally of the guesses on the board, and stop when the guesser is right.
Swap roles and play again. Play three or four rounds in all. If there are three of you, the third person keeps the tally, and you rotate each round.
Question 2
Play one more round. This time the guesser must guess 1, then 2, then 3, and so on, in order.
What is the most guesses this could ever take for a number from 1 to 100?
Answer
100 guesses, if the number is 100.
Think
Now stop playing, and answer these together on the board.
Question 3
Back to playing however you like. What is the best first guess? Why that number?
Answer
50, or 51. It is in the middle, so whatever the answer, you get rid of about half the numbers.
Question 4
Describe your strategy in one sentence that another group could follow without asking you anything.
Answer
Guess the middle of the numbers that are still possible. Throw away the half the answer rules out. Repeat.
Question 5
Using your strategy, what is the most guesses you could ever need for a number from 1 to 10? Be sure. Don’t give the number you got today; give the worst it could ever be.
Answer
4 guesses.
Question 6
Now for a number from 1 to 100. Write down how many numbers are still possible after each guess, starting from 100. What is the most guesses you could ever need?
Answer
100, 50, 25, 12, 6, 3, 1. The seventh guess always finds it, so 7 guesses.
Question 7
Now for a number from 1 to 1000. What is the most guesses you could ever need? Start a table:
| Numbers from | Most guesses you could ever need |
|---|---|
| 1 to 10 | |
| 1 to 100 | |
| 1 to 1000 |
Answer
1 to 10: 4. 1 to 100: 7. 1 to 1000: 10.
Question 8
Look at your table. Each row has ten times as many numbers as the row above. About how many more guesses does each row cost?
Answer
About 3 more guesses each time: 4, 7, 10.
Question 9
Without playing it, predict the most guesses you could ever need for a number from 1 to 1,000,000. Explain how you got your prediction.
Answer
20. There are three more rows of “times ten” past 1 to 1000, so about 10 + 3 × 3 = 19, and a little more.
Question 10
Try doubling instead. What is the most guesses you could ever need for 1 to 20? For 1 to 200? Compare with 1 to 10 and 1 to 100. What does doubling the numbers cost?
Answer
1 to 20: 5. 1 to 200: 8. Doubling the numbers costs exactly one more guess, which is why ten times as many numbers costs only about three.
Question 11
New rule. The thinker only ever says right or wrong, and never higher or lower. What happens to your strategy? What is the most guesses you could ever need now for 1 to 100?
Answer
The strategy stops working. “Wrong” only rules out one number at a time, so you might need all 100 guesses, just like question 2. Halving only works because the answer tells you which way to go, and that only makes sense because the numbers are in order.
Bonus
A guesser playing 1 to 100 says they have a strategy, but they need about 10 guesses every single round. What might they be doing wrong? Suggest one change that gets them to 7 or fewer.
Answer
They are not guessing the middle, so each guess throws away less than half of the numbers. Guess the middle of what is left.
Keep your table. You will see the number 7 again soon.
Curriculum connection
AAP-2.P
For binary search algorithms: a. Determine the number of iterations required to find a value in a data set. b. Explain the requirements necessary to complete a binary search.
AAP-2.P.1 The binary search algorithm starts at the middle of a sorted data set of numbers and eliminates half of the data; this process repeats until the desired value is found or all elements have been eliminated.
AAP-2.P.2 Data must be in sorted order to use the binary search algorithm.
AAP-2.P.3 Binary search is often more efficient than sequential/linear search when applied to sorted data.
Link to original