Maths Olympiad Prep

Library / /100 of 196

Combinatorics Difficulty 5.1 AIME, harder Prove it Soviet Union

Problem:

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

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

Solution

Solution:

a. No. Each of the numbers 0,1,8,90, 1, 8, 9 can only be adjacent to 3,4,53, 4, 5 or 66. But they can only accommodate 33 numbers, not 44.

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

In passing, there are obviously no solutions for 44 or 55. There is just the one solution for 66 (given in the question). For 77 there are 55 solutions: 0,3,6,1,5,2,7,40, 3, 6, 1, 5, 2, 7, 4; 0,3,6,1,4,7,2,50, 3, 6, 1, 4, 7, 2, 5; 0,3,6,2,7,4,1,50, 3, 6, 2, 7, 4, 1, 5; 0,3,7,4,1,6,2,50, 3, 7, 4, 1, 6, 2, 5; 0,4,1,6,3,7,1,50, 4, 1, 6, 3, 7, 1, 5. For 88 there is the solution 0,3,7,2,6,1,5,8,40, 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,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.