Library / All-Soviet-Union Mathematical Olympiad /91 of 185

All-Soviet-Union Mathematical Olympiad

Combinatorics Difficulty 5.1 AIME, harder Prove it Soviet Union

Problem:

a. Can you arrange the numbers $0, 1, \ldots, 9$ on the circumference of a circle, so that the difference between every pair of adjacent numbers is $3$ , $4$ or $5$ ? For example, we can arrange the numbers $0, 1, \ldots, 6$ thus: $0, 3, 6, 2, 5, 1, 4$ .

b. What about the numbers $0, 1, \ldots, 13$ ?

Solution

Solution:

a. No. Each of the numbers $0, 1, 8, 9$ can only be adjacent to $3, 4, 5$ or $6$ . But they can only accommodate $3$ numbers, not $4$ .

b. $0, 3, 7, 10, 13, 9, 12, 8, 11, 6, 2, 5, 1, 4$ is a solution for $13$ .

In passing, there are obviously no solutions for $4$ or $5$ . There is just the one solution for $6$ (given in the question). For $7$ there are $5$ solutions: $0, 3, 6, 1, 5, 2, 7, 4$ ; $0, 3, 6, 1, 4, 7, 2, 5$ ; $0, 3, 6, 2, 7, 4, 1, 5$ ; $0, 3, 7, 4, 1, 6, 2, 5$ ; $0, 4, 1, 6, 3, 7, 1, 5$ . For $8$ there is the solution $0, 3, 7, 2, 6, 1, 5, 8, 4$ , and maybe others.

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

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