Library / Harvard-MIT Math Tournament /65 of 83

Harvard-MIT Math Tournament

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:

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

Solution

Solution:

$4004$ . There are $2002$ possible positions for the $1$ . The two numbers adjacent to the $1$ must be $2$ and $3$ ; there are two possible ways of placing these. The positions of these numbers uniquely determine the rest: for example, if $3$ lies clockwise from $1$ , then the number lying counterclockwise from $2$ must be $4$ ; the number lying clockwise from $3$ must be $5$ ; the number lying counterclockwise from $4$ must now be $6$ ; and so forth. Eventually, $2002$ is placed adjacent to $2000$ and $2001$ , so we do get a valid configuration. Thus there are $2002 \cdot 2$ possible arrangements.

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.