17
$\begingroup$

A grasshopper is hopping around on the integers and starts its journey on the number $81$. In a jump starting from the integer $m$, the grasshopper

  • may jump to any integer $m^k$ with integer $k\ge1$
  • may jump to the number that results from $m$ by first cutting the decimal representation into a left piece and a right piece of two digits, and then adding three times the right piece to the left piece (for example, from $m=123456789$ the grasshopper may jump to $1234567+3\cdot89$). The left piece may be empty (for example, the jumps from $m=12$ to $0+3\cdot12$ and from $m=8$ to $0+3\cdot08$ are permitted).

No other jumps are allowed. Is there a sequence of jumps that brings the grasshopper to number $82$?

$\endgroup$
8
  • 2
    $\begingroup$ Can the left piece be empty? Is a jump from $081$ to $243$ permitted under the second bullet? How about from $004$ to $12$? How about from $105$ to $16$? $\endgroup$ Commented Sep 14, 2015 at 15:40
  • $\begingroup$ Yes, the left piece can be empty. Yes, the jumps from 081 to 243, from 004 to 12, and from 105 to 16 are all permitted. $\endgroup$
    – Gamow
    Commented Sep 14, 2015 at 16:00
  • $\begingroup$ It seems an impossible task. I tried this in Excel: Fill A1 to A100 with nos. 1 to 100. For every cell (m,n), enter formula: =ROUNDDOWN((m-1,n)/100,0)+(3*MOD((m-1,n),100)). Autofill helps. I couldn't find 82 anywhere. (If your cell is, say, C5, your function will operate on B5) $\endgroup$ Commented Sep 14, 2015 at 16:25
  • $\begingroup$ @ghosts_in_the_code I don't think that's correct. By my count, it takes 33 iterations to get from 81 back to 81 using jump #2: 81, 243, 131, 94, 282, 248, 146, 139, 118, 55, 165, 196, 289, 269, 209, 29, 87, 261, 185, 256, 170, 211, 35, 105, 16, 48, 144, 133, 100, 1, 3, 9, 27, 81 $\endgroup$ Commented Sep 14, 2015 at 16:59
  • $\begingroup$ No matter what I do my $m$ is always divisible by 3... 82 is not divisible by 3... Therefore I conclude it's impossible. $\endgroup$
    – warspyking
    Commented Sep 14, 2015 at 22:06

1 Answer 1

20
$\begingroup$

It is

not possible.

Consider the remainder of the number when divided by $13$. Initially we start with remainder $3$ ($81\equiv 3 \mod 13$), we have to get remainder $4$ ($82\equiv 4 \mod 13$).

Applying step 1, assuming that $m\equiv 3\mod 13$, we get:

$$ \begin{align} m &\to m^k \\ 3 &\to 3^1, 3^2, 3^3, \ldots \mod 13 \\ 3 &\to 3, 9, 1, 3, \ldots \mod 13 \end{align} $$

Now we know that we can at least get to $1$, $3$, and $9 \mod 13$. Applying the same argument for the two new values, we get:

$$ \begin{align} 1 &\to 1^1, 1^2, 1^3, \ldots \mod 13 \\ 1 &\to 1, 1, 1, \ldots \mod 13 \\ 9 &\to 9^1, 9^2, 9^3, \ldots \mod 13 \\ 9 &\to 9, 3, 1, 9, \ldots \mod 13 \\ \end{align} $$

(Here we have explicitly shown the argument for $9$, but we could have used the fact that $9=3^2$, so the powers of $9$ must be a subset of the powers of $3$ computed earlier.)

Therefore using step 1 we can get only numbers which are congruent to 1, 3 or 9 modulo 13. Now we verify that this is still true even if we apply step 2.

If we start with the number m and apply step 2, we will get:

$$ \begin{align} m=100a+b &\to a + 3b \end{align} $$

and then:

$$ \begin{align} 100a+b &\to a+3b \mod 13 \\ 100a+b &\to 300a + 3b \mod 13 \\ m &\to 3m \mod 13 \end{align} $$

Thus it is sufficient to consider the action of $m\to 3m$ on the values from earlier ($1$, $3$, and $9$):

$$ \begin{align} 3\times 1 &\to 3 \mod 13 \\ 3\times 3 &\to 9 \mod 13 \\ 3\times 9 &\to 1 \mod 13 \\ \end{align} $$

(Again, we could have used the fact that all the values are powers of three instead of calculating all the transformations explicitly.)

Thus the numbers that we get through any number of jumps is always of the form $13k+1$, $13k+3$, or $13k+9$ ($m\equiv1,3,9\mod 13$).

Since $82$ gives remainder $4$ when divided by $13$, it is not reachable.

$\endgroup$
15
  • 1
    $\begingroup$ He's saying that all results end in one of those three digits when divided by 13. $\endgroup$ Commented Sep 14, 2015 at 17:03
  • 1
    $\begingroup$ Why is 13 the magic number? $\endgroup$ Commented Sep 14, 2015 at 17:07
  • 2
    $\begingroup$ @Raystafarian, I wanted to see if the problem can be solved using congruences. For this reason observed that the second step transforms 100x+y to x+3y. Wanted x+3y to be congruent to k.(100x+y) modulo some special number in order to make the idea work. Chose k=3, such that the 3y will cancel on both sides. Ended up looking for a number which divides 300-1=299. The options were 13 and 23. Tried 13 and it worked. $\endgroup$ Commented Sep 14, 2015 at 17:11
  • 2
    $\begingroup$ @Anachor, the right piece should be a 2-digit number. I also missed that part initially and was trying to prove reachability for half an hour at least. P.S.Thanks for the edit. $\endgroup$ Commented Sep 14, 2015 at 17:47
  • 1
    $\begingroup$ @ArturKirkoryan - Well done on the solution! However, part of the explanation is a bit hard to follow. Consider reversing the order of the three lines starting at $m \to 3m \mod 13$. Then $a\equiv 300a \mod 13$, etc., flows nicely. +1 $\endgroup$
    – Marconius
    Commented Sep 15, 2015 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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