Prove that every number of form $3k$, $3k+1$ can be reached

An ant starts at point $0$ of the number line. In the first step it moves to $1$. After that the ant can move in steps of length $2x$ or $\frac{x}{2}$ if it has moved the amount $x$ in the previous step. The ant can't move backwards and can only move in steps equal to a natural number.

1. Which numbers can it reach?

Answer: We can start a way from $1$ or $3$ so if we can reach $w$ we can also reach $w+3$ and because we can reach $0,1$ we can reach any point of form $3k,3k+1$ and because in every two consecutive moves we move as a multiply of $3$ we can't reach numbers of form $3k+2$.

1. If we write the numbers that can be reached in at most $100$ moves from small to big find $2012$th number.

The book just found the $2012$th number that is like $3k$ or $3k+1$ and haven't checked if they could reached in less than $101$ moves. It is very likely the answer to be true since powers of $2$ can be large enough but I can't prove it.

Okay, suppose we want to get $3k$ where $0 \le k \le 1023$

$k$ will be a $10$ digit binary number = $a_9a_8a_7a_6a_5a_4a_3a_2a_1a_0$.

Case $1$. $a_9a_8 = 11$.

Then if we spend the first $22 = 2(10+1)$ steps doing $1+2+4 +.... + 2^9 + 2^8 + 2^9 + 2^8 + 2^7 + .... + 4 + 2 + 1 + 2 = 2^{10} - 1 + 2^8 + 2^{10} - 1 + 2 = 2^{12}+ 2^{8} = 2^{10} + 2^9+2^9 + 2^8 = 3(2^9 + 2^8)=3(a_9a_800000000)$.

So this is $22$ steps plus whatever it takes to do $3k': k = a_7a_6a_5a_4a_3a_2a_1a_0$.

(Note: We ended that stretch at $2$, so the next step can be $1$ and we can start a new number.

Case 2: $a_9a_8 = 10$.

If we spend the first $20 = 2*10$ steps doing $1+2 + 4 + ... +2^9 + 2^8 + 2^7 + ... + 2 + 1 + 2= (2^{10} -1)+(2^9 - 1) + 2 = 2^{10} + 2^9 = 3*2^9 = 3(a_900000000)$.

So this is $20$ steps plus what ever it takes to do the sake $k'$ above.

Case 3: $a_9a_8 = 01$.

Well we can do similar to case 2 to get in $18$ steps $1+2 + ... 2^8 + 2^7 + ... + 1 + 2=3*2^8 = 3*(a_9a_800000000)$ to reduce it to $18$ plus whatever it takes to get the $3*k'$ above.

And Case 4: $a_9a_8 = 00$ then it will take only whatever it takes to get teh $3*k'$ above.

So at the very most is will take $22$ steps plus whatever it takes to get the $3k'$ above.

By similar argument the absolute must it will take to get $3k'$ will be $2(8+1)=18$ plus whatever it takes to get $3k'': k'' = a_6a_5a_4a_3a_2a_1a_0$.

Reiteration five times it will take at most $22 + 18 + 14 + 10 + 6 = 70$ steps to get $3k$ for any $0 \le k \le 1023$.

And after achieving a distance of $3k$ we can finish with $3k + 1$ to get $3k+1$ in $71$ steps.

I'm not sure what the text had in mind to solve this but $100$ steps is plenty to get: $m_1 = 1; m_2 = 3; m_3= 4; m_{2k} = 3k; m_{2k + 1} = 3k + 1;$ are for $k < 1024$ within $100$ steps.

The only issue is to prove that only numbers of the form $3k$ and $3k + 1$ are possible.

There are several ways to do this and what you gave in the $OP$ is fine.

I suppose the easiest would be induction. If a sequence $S= +,......$ where $+$ doubles then ants step and $-$ halves it, results in a distance of $k$ then the sequence $+, -, S$ will results in $k+3$ and a sequence of $+, S$ will result is $1 + 2k$. As all sequences begin with $+$ and for every sequence can be achieve by either adding a $+$ or a $+, -$ to the beginning, this recursively describes all possible results.

A sequence of $1$ step can end in $1$ and a sequence of $2$ steps can end in $3$ both are of the forms $3k$ or $3k+1$.

If we assume all sequence of at most $m$ steps result in a distance of the form $k$ or $k + 1$. then a sequence of $m+1$ steps will result in distance of the form $3+ 3k = 3(k+1)$, $3+3k + 1 = 3(k+1) + 1$, $1 + 2*3k = 3(2k) + 1$, or $1 + 2*(3k + 1) = 6k + 3 = 3(2k + 1)$.

• I can't get the part "So we can get 3k within $(4∗9−2∗8−2)+(4∗7−2∗6−2)+(4∗5−2∗4−2)+(4∗3−2∗2−2)+(4∗1−2)=18+14+10+6+2=50$ moves (at most)" could you explain more please? – Taha Akbari Nov 4 '17 at 14:41
• let me redo the whole thing. this is kind o f sketchy although i think it is true it is pretty sketchy and it might not be. Give me a few hours. – fleablood Nov 4 '17 at 16:07
• We can get $3*(1100000000)$ in $(4*9 - 2*8 -2)=18$ moves. So we can get we get $3*(11000000)$ in $(4*7 - 2*6 -2)= 14$ moves. and $3*(110000)$ in $4*5-2*4-2 = 10$ moves and so on to get $3*11111111111$ in $50$ moves. That is the maximum number of moves required to get any number. – fleablood Nov 4 '17 at 17:05
• But we can get $2^9-2^8$ in $18$ moves not $2^9+2^8$ – Taha Akbari Nov 4 '17 at 17:18
• Oh, you're right. But that's okay. A ten digit number will have isolated $1$ representing $2^j$ or strings of $111$s between zeros representing $2^m(2^j - 1)$. There are at most 5 of these significant values. We have an upper limit on how long it will take to get these. Either $4*j-2m-2$ or $2j$. – fleablood Nov 4 '17 at 17:53