Track / Stage 7 / 114 of 300 #1514 of 1964

Problem 1514

National olympiad second round; IMO P1/P4

Combinatorics Difficulty 7.2 Prove it Final Round, September 2019 · Netherlands · 2019

A complete number is a 9 digit number that contains each of the digits 1 to 9 exactly once. The difference number of a number $N$ is the number you get by taking the differences of consecutive digits in $N$ and then stringing these digits together. For instance, the difference number of 25143 is equal to 3431. The complete number 124356879 has the additional property that its difference number, 12121212, consists of digits alternating between 1 and 2.

Determine all $a$ with $3 \le a \le 9$ for which there exists a complete number $N$ with the additional property that the digits of its difference number alternate between 1 and $a$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

For $a = 4$ , an example of such a number is 126734895. For $a = 5$ , an example is the number 549832761. (There are other solutions as well.)

We will show that for $a = 3, 6, 7, 8, 9$ there is no complete number with a difference number equal to $1a1a1a1a$ . It then immediately follows that there is also no complete number $N$ with difference number equal to $a1a1a1a1$ (otherwise, we could write the digits of $N$ in reverse order and obtain a complete number with difference number $1a1a1a1a$ ).

For $a$ equal to 6, 7, 8, and 9, no such number $N$ exists for the following reason. For the digits 4, 5, and 6, there is no digit that differs by $a$ from that digit. Since the difference number of the complete number $N$ is equal to $1a1a1a1a$ , every digit of $N$ , except the first, must be next to a digit that differs from it by $a$ . Hence, the digits 4, 5, and 6 can only occur in the first position of $N$ , which is impossible.

For $a = 3$ the argument is different. If we consider the digits that differ by 3, we find the triples 1–4–7, 2–5–8, and 3–6–9. If the 1 is next to the 4 in $N$ , the 7 cannot be next to the 4 and so the 7 must be the first digit of $N$ . If the 1 is not next to the 4, the 1 must be the first digit of $N$ . In the same way, either the 2 or the 8 must be the first digit of $N$ as well. This is impossible.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.