In the real axis, there is bug standing at coordinate $x=1$. Each step, from the position $x=a$, the bug can jump to either $x=a+2$ or $x=\frac{a}{2}$. Show that there are precisely $F_{n+4}-(n+4)$ positions (including the initial position) that the bug can jump to by at most $n$ steps. Recall that $F_n$ is the $n^{th}$ element of the Fibonacci sequence, defined by $F_0=F_1=1$, $F_{n+1}=F_n+F_{n-1}$ for all $n\geq 1$.
Problem
Source: Vietnam TST 2019 Day 2 P6
Tags: combinatorics
Pathological
08.04.2019 02:13
First of all, let's apply magic to turn the bug into a frog, since bugs are bad.
Next, it's obvious that the frog is always at a position of the form $\frac{n}{2^m}$, where $n \in 2 \mathbb{N} + 1$ and $m \ge 0$. Furthermore, it's easily seen that any position of this form is indeed reachable by the frog. Hence, it makes sense to define $f: \mathbb{Z}_{\ge 0} \times \mathbb{Z}_{\ge 0} \rightarrow \mathbb{Z}_{\ge 0}$ by letting $f(n, m)$ be the minimal number of hops the frog needs to make to get from $1$ to $\frac{2n+1}{2^m}$, for all $n, m \in \mathbb{Z}_{\ge 0}.$ For convenience, we will refer to $\mathbb{Z}_{\ge 0}$ as $\mathbb{X}$ from now on. We can easily obtain that $f(n, 0) = n$ and $f(n, m) = f(n-2^m, m) + 1$ when $n \ge 2^m$ and $f(n, m) = f(n, m-1) + 1$ otherwise.
Call an ordered pair $(n, m) \in \mathbb{X}^2$ $\mathbf{vengeful}$ if $n \le 2^{m+1} - 1$. We $\mathbf{claim}$ that for all $x \in \mathbb{X}$, the number of vengeful $(n, m) \in \mathbb{X}^2$ for which $f(n, m) = x$ is $F_{x+1}$. To see this, notice that for a fixed $m$, the number of $0 \le n \le 2^{m+1} - 1$ for which $f(n, m) = x$ is $\binom{m+1}{x-m}$ if $x \ge m$ and $0$ else. The proof of the above claim is by induction on $m.$ From here, a well-known combinatorial identity shows the claim.
Using the claim, we will now show a lemma.
$\mathbf{Lemma.}$ For any $x \in \mathbb{X}$, the number of $(n, m) \in \mathbb{X}^2$ for which $f(n, m) = x$ is $F_{x+2} - 1$.
$\mathbf{Proof.}$ We will prove it by induction on $x$. When $x = 0$, it is obvious since $f(0,0) = 0$ and for no other $(n, m) \in \mathbb{X}^2$ is $f(n, m) = 0$. Assume that it holds when $x = k$. When $x = k+1,$ let $S_{x}, S_{x+1}$ be the set of $(n, m) \in \mathbb{X}^2$ for which $f(n, m) = x, x+1$, respectively. We will construct a function $g$ from $S_{x+1}$ to $S_x$ as follows. For $(n, m) \in S_{x+1}$, if $f(n, m-1) = x$, then let $g(n, m) = (n, m-1).$ Otherwise, let $g(n, m) = (n-2^m, m).$ It's easy to verify that this is indeed a function from $S_{x+1}$ to $S_x$, it is surjective, and that $(n, m) \in S_x$ is mapped to either once or twice. Furthermore, it's easy to see that $(n, m) \in S_x$ is mapped to twice if and only if it is vengeful. Therefore, we know that $|S_{x+1}| = |S_x| + v(x),$ where $v(x)$ denotes the number of vengeful $(n, m)$ with $f(n, m) = x$. By induction and the claim, we hence know that $|S_{x+1}| = F_{x+2} - 1 + F_{x+1} = F_{x+3} - 1,$ hence completing the induction.
$\blacksquare$
By the Lemma, it's clear that for every $x \in \mathbb{X}$, the number of $(n, m) \in \mathbb{X}^2$ with $f(n, m) \le x$ is $F_2 - 1 + F_3 - 1 + F_4 - 1 + \cdots + F_{x+2} - 1 = F_{x+4} - (x+4),$ as desired.
$\square$
Muriatic
13.04.2019 23:43
Dear Pathological, what would the motivation be for considering Step 1? It is very insightful indeed.
CANBANKAN
08.03.2022 21:37
Rename $F_0=0,F_1=1$.
Clearly, all reachable numbers are of the form $\frac{2m+1}{2^k}$
Let $f(m,k)$ be the minimum number of steps needed to get $\frac{2m+1}{2^k}$.
I claim if $m=q2^k+r$ where $0\le r<2^k$ then $f(m,k)=s_2(r)+q+k$. To prove this, consider $2^k$ times the number. Suppose I add 2 $n_1$ times, divide by 2, add 2 $n_2$ times, divide by 2, ...
Then $n_1$'s contribution is $2n_1$, $n_2$'s contribution is $4n_1$ .. (when multiplied by $2^k$)
Therefore, this is the minimum value of $n_0+n_1+n_2+\cdots+n_k$ where $1+\sum\limits_{j=0}^k 2^{j+1} n_j = 2m+1$. It's clear $n_1,\cdots,n_{k-1}\le 1$ and we do have $n_0+\cdots+n_{k-1}=s_2(R(m,2^k))$ and $n_k=\lfloor \frac{m}{2^k} \rfloor$. Therefore, $f(q2^k+r, k)=k+q+s_2(r)$. For each value of $s_2(r)$, there are $\binom{k}{s_2(r)}$ values of $r$ that satisfy the property.
Therefore, the number of points reachable in exactly $n$ points is $\sum\limits_{q\ge 0} \sum\limits_{k\ge 0} \binom{k}{n-q-k} = \sum\limits_{q\ge 0} F_{q+1}$. We can induct to show this is $F_{n+3}-1$. We again induct to show there are exactly $F_{n+5}-(n+4)$ positions reachable within $n$ moves, as needed.