HMMT 二月 2002 · ADV 赛 · 第 6 题

HMMT February 2002 — ADV Round — Problem 6

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

解析

In how many ways can the numbers 1 , 2 , . . . , 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: 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 · 2 possible arrangements.