Maths Olympiad Prep

Library / /4 of 5

, 2019

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Netherlands

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 NN is the number you get by taking the differences of consecutive digits in NN 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 aa with 3a93 \le a \le 9 for which there exists a complete number NN with the additional property that the digits of its difference number alternate between 1 and aa.

Solution

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

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

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

For a=3a = 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 NN, the 7 cannot be next to the 4 and so the 7 must be the first digit of NN. If the 1 is not next to the 4, the 1 must be the first digit of NN. In the same way, either the 2 or the 8 must be the first digit of NN as well. This is impossible.

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 and solution reproduced as published; topic and difficulty added by this site.