Bug jumping problem

Question

In the real axis, there is a bug standing at coordinate $x=1$. At each step, from the position $x=a$, the bug can jump to either $x=a+2$ or $x=\frac{a}{2}$. How many positions in total are there (including the initial position) that the bug can jump to by at most $n$ steps?

Isn't the answer trivially $2^n+1$? Am I missing something here?

EDIT: For examples, I tested the following:

$n=1$: Trivially, the answer is $2+1=3$.

$n=2$: The possible sequences are $1,3,5$ and $1,3,3/2$ and $1,1/2,7/2$ and $1,1/2,1/4$, which gives us a total of $7$ positions, but this is not equal to $2^2+1$. So, my hypothesis is incorrect.

Does anyone have any other idea in mind to solve this problem? We want to avoid collisions, where two possibilities land on the same position at some point, and we end up double-counting it.

Answer 1

$\newcommand{\BUG}{\operatorname{BUG}}$ This is not a solution to the problem, but I think it answers your question about the "trivial answer".

Let $\BUG(n)$ be the number of positions that the bug can jump to in at most $n$ steps. For example, in zero steps, the bug can only be at the starting position $1$, so $\BUG(0)=1$. In at most one step, the bug can get to $1/2$ or $3$, or it can be at its starting position (zero steps). So, $\BUG(1)=3$.

In general, since there are two options at each step, taking exactly $n$ steps will get the bug to at most $2^n$ different positions. Therefore, the number of possible positions after at most $n$ steps is at most $\sum_{k=0}^n 2^k$. So: $$ \BUG(n) \leq \sum_{k=0}^n 2^k = 2^{n+1}-1. $$ Note that for $n=0$ and $n=1$, this formula actually produces the exact number. I think this is the trivial solution you were looking for. So, we can ask: do we actually have $\BUG(n) = 2^{n+1}-1$?

The answer to this is no, as pointed out in the comments, since we can reach (for example) $5/2$ in two different ways: $1 \rightarrow 1/2 \rightarrow 5/2$ or $1 \rightarrow 3 \rightarrow 5 \rightarrow 5/2$. You can check by hand that: $$ \BUG(3) = 14 < 15 = 2^{3+1}-1. $$ So, the guess $\BUG(n) = 2^{n+1}-1$ is wrong. I don't what the real solution is; this seems like it could be a really tricky problem.

Answer 2

No proof yet, but I am now convinced that, as I commented under the question, the OEIS entry A001924 is the answer. I have verified by computer that if $N(m)$ stands for the number of places the bug can reach in at most $m$ jumps, the sequence $(N(m))_{m\ge0}$ begins with $$1,3,7,14,26,46,79,133,221,364,\ldots$$

There are several descriptions of this sequence in the OEIS. I haven't gone through the list and checked, if it would be easy to connect this to any of them. Hopefully during the weekend...

Anyway, I'm sure you all recognize the sequence $(N(m)+m+4)_{m\ge0}$: $$5,8,13,21,34,55,89,144,233,377,\ldots$$

Answer 3

From any starting location, the operation "forward, forward, backward" (FFB) is equivalent to "backward, forward" (BF), because $(x+2+2)/2=x/2+2$. This means that when counting the locations reachable in at most $n$ jumps, we can ignore any sequence that contains FFB, since it's equivalent to a shorter sequence.

An FFB-free sequence is one in which every B is immediately preceded by at most one F. Such a sequence is determined by the following data:

• how many Bs it has;
• for each B, whether there's an F immediately before it;
• the number of Fs that come after all the Bs.

Each such sequence takes the bug to a different final location. To see this, notice that the bug's position is always of the form $\frac m{2^k}$, where $m$ is odd and $k$ is the number of backwards jumps. A forward jump increases $m$ by $2^{k+1}$, and there's never any cancellation between the numerator and denominator since the numerator is odd, so sequences that give the same result must have the same number of Bs. Now consider the effect of the Fs on the binary representation of $m$: an F immediately before the $i$th B increments the bit at position $i$ (counting from 0 on the right), and Fs at the end of the sequence only affect higher-order bits. This means that given a final location $\frac m{2^k}$, there is a unique FFB-free sequence that brings the bug there (which we can essentially "read off" from $k$ and the binary representation of $m$).

Therefore, the count we want is just the number of FFB-free sequences of length at most $n$. Picking such a sequence is equivalent to picking:

• the number of Bs ($0\le b\le n$);
• the number of Fs not at the end ($0\le f\le b$ and $b+f\le n$);
• the positions of those Fs (a set of size $f$ from among $b$ choices);
• the number of Fs at the end (from $0$ to $n-b-f$).

The number of ways to do this is:

$$C(n)=\sum_{b=0}^n\sum_{f=0}^{\min(b,n-b)}\binom bf(n-b-f+1).$$

Answer 4

To finally prove Lahtonen's observation that the number of reachable locations after at most $n$ steps is given by A001924, we use the equivalence to $001$-avoiding binary strings from Karl's answer.

Let $a_n$ be the number of length-$n$ $001$-avoiding binary strings not ending in $0$; it is easy to show that $a_n=F_{n+1}$. Now let $b_n$ be the same but without the ending restriction. Since right $0$-padding is a bijection between $a_k$-strings for $k\le n$ and $b_n$-strings $$b_n=\sum_{k=0}^nF_{k+1}=F_{n+3}-1$$ Finally let $c_n$ count the OP's desired result – $001$-avoiding binary strings of length at most $n$: $$c_n=\sum_{k=0}^n(F_{k+3}-1)=F_{n+5}-(n+4)$$ which is essentially A001924.