Guessing a Number

Divide-and-conquer strategy

If we want to solve a problem using a divide-and-conquer strategy, we have to think about the following three steps:

1. Breaking a problem into smaller subproblems.
2. Solving each subproblem recursively.
3. Combining a solution to the original problem out of solutions to subproblems.

The first two steps are the “divide” part, whereas the last step is the “conquer” part. We illustrate this approach with a number of problems of progressing difficulty and then proceed to the programming challenges.

Guess a number

In the “Guess a Number” game, our opponent has an integer $1 ≤ x ≤ n$ in mind. We ask questions of the form “Is $x = y$?”. Our opponent replies either “yes”, or “$x < y$” (that is, “my number is smaller than your guess”), or “$x > y$” (that is, “my number is larger than your guess”). Our goal is to get the “yes” answer by asking the minimum number of questions. Let $n = 3$. Our goal is to guess $1 ≤ x ≤ 3$ by asking at most two questions. Can we do this? Let’s try it here (Level 1).