Given are the real line and the two unique marked points $0$ and $1$. We can perform as many times as we want the following operation: we take two already marked points $a$ and $b$ and mark the reflection of $a$ over $b$. Let $f(n)$ be the minimum number of operations needed to mark on the real line the number $n$ (which is the number at a distance $\left| n\right|$ from $0$ and it is on the right of $0$ if $n>0$ and on the left of $0$ if $n<0$). For example, $f(0)=f(1)=0$ and $f(-1)=f(2)=1$. Find $f(n)$.
Problem
Source: Brazil National Olympiad 2019 #2
Tags: combinatorics
Pathological
15.11.2019 04:41
By symmetry, it suffices to solve the problem for positive $n.$ The answer is $f(n) = \left \lceil \log_2{n} \right \rceil$ if $n$ is positive. Call this function $g(n)$. The proof proceeds in two steps. First we show that $f(n) \ge g(n).$ We claim that the range fo the marked points is at most $2^t$ at $t$ operations. This is proven by induction on $t$. The base case $t = 0$ is obvious. If it holds for $t = k$, when $t = k+1$ simply apply the inductive hypothesis after reverting the last operation. It's easy to complete the induction. From here, it becomes apparent that $f(n) \ge g(n)$, because $n > 2^{g(n) - 1}.$ Let's now show that $f(n) \le g(n).$ We need to show that it requires at most $n$ operations to mark $n$, for all $n \in \mathbb{N}.$ The proof is by induction on $g(n).$ If $g(n) = 1$, then we have $n = 2$, which clearly requires only one operation to mark. Assume it holds for all $n$ with $g(n) = k.$ When $g(n) = k+1$, consider two cases on the parity of $n$. If $n$ is even, then $g(\frac{n}{2}) = k$ and so $\frac{n}{2}$ requires only $k$ operations to mark. After these $k$ operations, we can just reflect $0$ over $\frac{n}{2}$ to get $n$, completing the induction. If $n$ is odd, then $g(\frac{n+1}{2}) = k$ and so $\frac{n+1}{2}$ requires only $k$ operations to mark. After these $k$ operations, we can just reflect $1$ over $\frac{n+1}{2}$ to get $n$, completing the induction. Hence, the induction is complete. After acquiring the two above bounds, we have shown that $f(n) = g(n).$ $\square$
ryt1452
16.11.2019 09:46
check f(5). 5 can be marked by reflecting -2 over 1. in this case f(5)=2, not 3, as your function suggests.
Pathological
17.11.2019 01:12
@above Sorry, I don't see how we can obtain $5$ with only two reflections. We can't mark $-2$ on the first move (only $-1$ and $2$), so the first marked point can't be $-2$.
ryt1452
17.11.2019 03:57
sorry lol typed it wrong. reflecting -1 over 2, my bad
Pathological
17.11.2019 04:31
Doesn't it take one operation each to mark $-1$ and $2$? Then reflecting $-1$ over $2$ would require another operation, for a total of $3$ operations, right?
ryt1452
17.11.2019 06:10
uhhh now i get it. thanks for your patience
Letteer
17.11.2019 17:41
With regards to the final sentence, 1) Reflecting $-2$ over $1$ gives $4$, not $5$. 2) Note that $-2 $ cannot be reached in $1$ step. 3) I calculate that $f(5)=3 $
With each step, we can at most double the maximum distance between any 2 marked points. Hence, the numbers in the sets $S^n = \{ 2^{n-1} + 1, 2^{n-1} + 2 + \ldots + 2^n\}$ and the negative counterparts $ T^n = \{- 2^{n-1}, -2^{n-1} + 1, \ldots, -2^{n} - 1 \}$ will need at least $n$ steps.
It remains to show that $n$ steps is enough. This can be done via 2 different approaches below.
The case for $T^n$ can be done similarly (by flipping the number line around) so we will just focus on $S^n$.
For a given $s\in S^{n}$, let $s_1, \ldots, s_{n} = s$ be the sequence of marks that we take to reach $s$. If needed, $s_0 = 1$ which we're given for free.
Constructive approach.
Let $f(s) = \begin{cases} \frac{ s+1}{2} & s \text{ odd} \\ \frac{s}{2} & s \text{ even} \end{cases} $.
Construct the sequence $ s, f(s), f^2(s), \ldots f^n(s) = 2$.
(Note: Why is $f^n(s) = 2$?)
Follow the rule: To get mark $s_i$,
If $f^{n+1-i} (s)$ is odd, flip 1 about $s_{i-1}$.
If $f^{n+1-1} (s)$ is even, flip 0 about $s_{i-1}$.
The reason why this works is:
- Flipping 1 about $s_{i-1}$ gives $s_{i} = 2s_{i-1}-1$
- Flipping 0 about $s_{i-}$ gives $s_{i} = 2s_{i-1}$
This is the inverse map of the function $f$, hence we obtain the marks $s_i$ as the reverse of the constructed sequence, and in particular $s_n = s$ as desired.
To see this in action, consider say $s=22$, we get the sequence $ 22 \rightarrow 11 \rightarrow 6 \rightarrow 3 \rightarrow 2$.
$s_1:$ Since 2 is even, flip 0 about 1 to get 2.
$s_2:$ Since 3 is odd, flip 1 about 2 to get 3.
$s_3:$ Since 6 is even, flip 0 about 3 to get 6.
$s_4:$ Since 11 is odd, flip 1 about 6 to get 11.
$s_5:$ Since 22 is even, flip 0 about 11 to get 22.
Existence approach. (I came up with this first, because the induction was very natural to consider. However, the previous approach is better, hence it's listed above.)
The resulting sequence of marks is different from the above, in part for odd $n$ $s_1=-1$ instead of $2$.
For $s \in S^{n+1}$ odd:
We will take $s_1 = -1$, obtained by flipping $1$ to $-1$.
Then, consider the map of the real line $ \rho: x \rightarrow \frac{x+1}{2}$. $\rho (1) = 1, \rho (-1 ) = 0, \rho (s) = \frac{ s + 1 } { 2 } \in S^n$.
Hence, there is some series of marks $s^* _1, s^*_2, \ldots s^*_n = \frac{ s + 1 } { 2 } $.
Hence, we can take $s_{i+1} = \rho^{-1} (s^*_i)$, to reach $s_{n+1} = \rho^{-1} (s^*_n) = s$.
Similarly, for $s \in S^{n+1} $ even:
We will take $s_1 = 2$ obtained by flipping $0$ to $2$.
Then, consider the map of the real line $ \rho: x \rightarrow \frac{x}{2}$. $\rho (2) = 1, \rho (0 ) = 1, \rho (s) = \frac{ s} { 2 } \in S^n$.
Hence, there is some series of marks $s^* _1, s^*_2, \ldots s^*_n = \frac{ s } { 2 } $.
Hence, we can take $s_{i+1} = \rho^{-1} (s^*_i)$, to reach $s_{n+1} = \rho^{-1} (s^*_n) = s$.
cyshine
10.12.2019 06:57
Hi, I'm the author of this problem, and I just want to add that the inspiration to this problem was... Geogebra. I was measuring 7 units for a simple geometry problem by using the symmetry about a point tool (or circle by center and one point, I don't remember exactly), and I was wondering what was the most efficient way to reach $n$ after marking $0$ and $1$. It became this little nice problem.
pad
23.05.2020 05:08
We claim $f(n) = \lceil \log_2(n) \rceil$, for $n\ge 1$. Obviously $f(n)=f(1-n)$ by symmetry, so it suffices to answer for $n\ge 1$. We first show $f(n) \ge \lceil \log_2(n) \rceil$. In order to do this, we will show that given $k$ operations, the largest "width" of the range of numbers that we mark if at most $2^k$. This is obvious by induction, as at each step, we can at most double the entire width of our range. This proves $f(n) \ge \lceil \log_2(n) \rceil$. To finish, we need to show that we can always get to $n$ from $0,1$ in exactly $\lceil \log_2(n) \rceil$ moves. We induct on $n$, the base case of $n=1$ given. Suppose $2^k < n\le 2^{k+1}$. We need to show that we can get to $n$ in $k+1$ moves. If $n$ is even: we can get to $\tfrac{n}{2}$ in $k$ moves by induction. Then reflect this over 0 to get to $n$. If $n$ is odd: we can get to $\tfrac{n+1}{2}$ in $k$ moves. Then reflect 1 over this to get to $n$. This completes the induction, and the proof.
Coming up with the answer is not hard by doing some examples. The idea of considering the total width of the range is key; we cannot actually get bounds on the maximum number or anything like that. For the construction, originally, I was trying to introduce more structure to reflect over, but actually just using 0 and 1, which we are given, works.