Maths Olympiad Prep

Library / /75 of 94

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:

In how many ways can the numbers 1,2,,20021,2, \ldots, 2002 be placed at the vertices of a regular 20022002-gon so that no two adjacent numbers differ by more than 22? (Rotations and reflections are considered distinct.)

Solution

Solution:

40044004. There are 20022002 possible positions for the 11. The two numbers adjacent to the 11 must be 22 and 33; there are two possible ways of placing these. The positions of these numbers uniquely determine the rest: for example, if 33 lies clockwise from 11, then the number lying counterclockwise from 22 must be 44; the number lying clockwise from 33 must be 55; the number lying counterclockwise from 44 must now be 66; and so forth. Eventually, 20022002 is placed adjacent to 20002000 and 20012001, so we do get a valid configuration. Thus there are 200222002 \cdot 2 possible arrangements.

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.