Competition problem — Number theory

Library / /19 of 28

Number theory Difficulty 6.1 National Olympiad Prove it JBMO

Problem:

We can change a natural number $n$ in three ways:

a) If the number $n$ has at least two digits, we erase the last digit and we subtract that digit from the remaining number (for example, from $123$ we get $12-3=9$ );

b) If the last digit is different from $0$ , we can change the order of the digits in the opposite one (for example, from $123$ we get $321$ );

c) We can multiply the number $n$ by a number from the set $\{1,2,3, \ldots, 2010\}$ .

Can we get the number $21062011$ from the number $1012011$ ?

Solution

Solution:

The answer is NO. We will prove that if the first number is divisible by $11$ , then all the numbers which we can get from $n$ are divisible by $11$ .

When we use a), from the number $10a + b$ , we will get the number $m = a - b = 11a - n$ , so $11 \mid m$ since $11 \mid n$ .

It's well-known that a number is divisible by $11$ if and only if the difference between the sum of digits on even places and the sum of digits on odd places is divisible by $11$ . Hence, when we use b), from a number which is divisible by $11$ , we will get a number which is also divisible by $11$ .

When we use c), the obtained number remains divisible by $11$ .

So, the answer is NO since $1012011$ is divisible by $11$ and $21062011$ is not.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.