5. Maja writes natural numbers on the board. If the number $n$ is written on the board, she writes $3n + 13$ on the board as well. If a perfect square is written on the board, she also writes its square root.

(a) Can Maja obtain the number 55 using the mentioned operations if the number $256$ is already written on the board?

(b) Can Maja obtain the number 256 using the mentioned operations if the number $55$ is already written on the board?

## 52nd Mathematical Competition for High School Students in Slovenia  Optional Competition, April 2, 2008

## Problems for 3rd Year Students
II/5. If the number 256 is written on the board, Maja can obtain the number 55, and she can do so by first taking the square root of 256 to get 16. From 16, she can then get $3 \cdot 16 + 13 = 61$, and from this number, she can further get $3 \cdot 61 + 13 = 196$. The number 196 can be rooted to get 14, and then from it, $3 \cdot 14 + 13 = 55$. (Note: It is possible that there are multiple ways to get the number 55 from 256, but this method is the only one that requires fewer than 100 steps).

Let's show that Maja cannot obtain the number 256 from the number 55. Consider the remainders when dividing by 4. If a number is even, it is of the form $2k$, and the square of this number is then of the form $4k^2$. If the number is odd, it is of the form $2k+1$, so the square of this number is $4k^2 + 4k + 1$, which gives a remainder of 1 when divided by 4. Therefore, a number is a perfect square only if it gives a remainder of 0 or 1 when divided by 4, so we can only take the square root of such numbers.

The number 55 gives a remainder of 3 when divided by 4. If we apply the rule $n \mapsto 3n + 13$ to a number of the form $4k + 3$, we get $12k + 9 + 13 = 4(3k + 5) + 2$, which is a number that gives a remainder of 2. If we apply the rule to a number of the form $4k + 2$, we get $12k + 6 + 13 = 4(3k + 4) + 3$, which is a number that gives a remainder of 3 when divided by 4. This means that from the number 55, after one step, we will get a number that gives a remainder of 2 when divided by 4, then a number with a remainder of 3, then a number with a remainder of 2, and so on. Since the number 256 is divisible by 4, Maja will not be able to reach it this way.

Writing how Maja can get the number 55 from 256 2 points  
Observation of divisibility by any number when applying rules .................... 1 point  
Finding that perfect squares give a remainder of 0 or 1 when divided by 4 ....... 1 point  
Finding that from the number 55, we can only get numbers that give remainders of 2 or 3 when divided by 4. 2 points  
Conclusion that Maja cannot write the number 256 in the second case 1 point