16
$\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$
  • 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$ – Ross Millikan Sep 14 '15 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 Sep 14 '15 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$ – ghosts_in_the_code Sep 14 '15 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$ – GentlePurpleRain Sep 14 '15 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 Sep 14 '15 at 22:06
19
$\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$
  • $\begingroup$ I don't actually understand what you're saying here, but it sounds like you're saying that the final digit will always be 1, 3, or 9. That's definitely incorrect. See my comment on the question for the sequence of numbers derived from 81 using step 2. There are certainly numbers that don't end in one of those 3 digits. $\endgroup$ – GentlePurpleRain Sep 14 '15 at 17:02
  • 1
    $\begingroup$ He's saying that all results end in one of those three digits when divided by 13. $\endgroup$ – Ian MacDonald Sep 14 '15 at 17:03
  • 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$ – Puzzle Prime Sep 14 '15 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$ – Puzzle Prime Sep 14 '15 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 Sep 15 '15 at 2:24

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.