Problem 1835

a. With $256$ written on the board, Maja can get $55$ by taking the square root of $256$, obtaining $16$, and then writing down $3 \cdot 16 + 13 = 61$ and $3 \cdot 61 + 13 = 196$. Now, she can write down the square root of $196$, which is $14$, and finally she can get $55$ as $3 \cdot 14 + 13 = 55$. (Note: there might be other ways of obtaining $55$, but this is the only one that requires less than $100$ steps).

b. Let us now show that Maja cannot get $256$ from $55$. Consider the remainders modulo $4$. An even number is of the form $2k$ and its square is $4k^2$. An odd number can be written as $2k + 1$, so its square is equal to $4k^2 + 4k + 1$, giving the remainder of $1$ when divided by $4$. We see that a perfect square can only give the remainders $0$ or $1$ when divided by $4$, so we can never use the rule $n \mapsto \sqrt{n}$ on numbers that give the remainder $2$ or $3$.

The remainder we get when dividing $55$ by $4$ is $3$. Using the rule $n \to 3n+13$ on a number of the form $4k+3$, we get $12k+9+13 = 4(3k+5)+2$, a number that gives the remainder of $2$. Using this rule on the number of the form $4k+2$, we get $12k+6+13 = 4(3k+4)+3$, the remainder is $3$. After one step the remainder will be $2$, then $3$, then $2$ again, and so on. Since $256$ is divisible by $4$, Maja can never reach it using the given two rules.