In how many ways can the numbers 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
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 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.