2. A midpoint tracer is an instrument that draws the exact midpoint of two previously marked points. Starting from two points at a distance of 1 and using only the midpoint tracer, you must obtain two points at a distance strictly between $\frac{1}{2017}$ and $\frac{1}{2016}$, drawing the minimum number of points possible. What is the minimum number of times you need to use the midpoint tracer, and what strategy would you follow to achieve your goal?
Solution. Without loss of generality, we can work with the real line and consider that one of the initial points is 0 and the other is 1. It is easy to verify that after $k$ applications of the tracer, all the points found are of the form $\frac{n}{2^{k}}$ with $0 \leq n \leq 2^{k}$, and the fraction is not necessarily irreducible. We will prove this by induction. Indeed, for $k=1$ we have the points

$$
0=\frac{0}{2^{1}}, \quad \frac{1}{2}=\frac{1}{2^{1}}, \quad 1=\frac{2}{2^{1}}
$$

Suppose that in step $k$ the points are

$$
0=\frac{0}{2^{k}}, \frac{1}{2^{k}}, \cdots, \frac{r}{2^{k}}, \cdots, \frac{s}{2^{k}}, \cdots, 1=\frac{2^{k}}{2^{k}}
$$

Then, applying the tracer again, in step $k+1$ the points obtained are

$$
0=\frac{0}{2^{k+1}}, \frac{1}{2^{k+1}}, \cdots, \frac{1}{2}\left(\frac{r}{2^{k}}+\frac{s}{2^{k}}\right)=\frac{r+s}{2^{k+1}}, \cdots, 1=\frac{2^{k+1}}{2^{k+1}}
$$

Now we focus on the distances between points. Using the tracer once, the distance between any two of the points obtained

$$
0=\frac{0}{2^{1}}, \quad \frac{1}{2}=\frac{1}{2^{1}}, \quad 1=\frac{2}{2^{1}}
$$

is a multiple of $\frac{1}{2^{1}}$, and applying the tracer $k$ times results in the distance between any two points being a multiple of $\frac{1}{2^{k}}$. It is immediate to verify that between $\frac{64}{2^{17}}$ and $\frac{66}{2^{17}}$ the inequalities

$$
\frac{64}{2^{17}}<\frac{1}{2017}<\frac{65}{2^{17}}<\frac{1}{2016}<\frac{66}{2^{17}}
$$

are satisfied. Therefore, any distance strictly included between $\frac{1}{2017}$ and $\frac{1}{2016}$ must necessarily have a denominator with an exponent $k \geq 17$.

Now we will see that the minimum number of times the tracer needs to be used is $k=17$ and we will describe a strategy to achieve this. Indeed, using the tracer once yields the point $\frac{1}{2}=\frac{1}{2^{1}}$, then we use it again between this point and 1 to obtain the point $\frac{3}{4}=\frac{3}{2^{2}}$, and from here we calculate the midpoint between the last point found so far and the point $\frac{1}{2}$, obtaining successively the points

$$
\frac{5}{8}=\frac{5}{2^{3}}, \quad \frac{9}{16}=\frac{9}{2^{4}}, \quad \frac{17}{32}=\frac{17}{2^{5}}, \quad \frac{33}{64}=\frac{33}{2^{6}}
$$

and after a total of 7 applications of the tracer, we obtain the point $\frac{65}{128}=\frac{65}{2^{7}}$. Now we apply the tracer 10 more times, to obtain the midpoint between the last point found so far and the point 0, successively obtaining the points

$$
\frac{65}{2^{8}}, \frac{65}{2^{9}}, \frac{65}{2^{10}}, \cdots, \frac{65}{2^{17}}
$$

This last point is $\frac{65}{2^{17}}$ away from both 0 and the previous point found $\frac{65}{2^{16}}$. Thus, in 17 steps we have achieved our goal, and we are done.