0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Taha Akbari Nov 4 '17 at 14:41
  • $\begingroup$ 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. $\endgroup$ – fleablood Nov 4 '17 at 16:07
  • $\begingroup$ 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. $\endgroup$ – fleablood Nov 4 '17 at 17:05
  • $\begingroup$ But we can get $2^9-2^8$ in $18$ moves not $2^9+2^8$ $\endgroup$ – Taha Akbari Nov 4 '17 at 17:18
  • $\begingroup$ 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$. $\endgroup$ – fleablood Nov 4 '17 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.