IMO 1971 SL 6

Origin: HUN

Problem

Let n \geq2 be a natural number. Find a way to assign nat- ural numbers to the vertices of a regular 2n-gon such that the following conditions are satisfied: (1) only digits 1 and 2 are used; (2) each number consists of exactly n digits; (3) different numbers are assigned to different vertices; (4) the numbers assigned to two neighboring vertices differ at exactly one digit.

Solution

The proof goes by induction on n. For n = 2, the following numeration satisfies the conditions (a)–(d): C1 = 11, C2 = 12, C3 = 22, C4 = 21. Suppose that n > 2, and that the numeration C1, C2, . . . , C2n−1 of a reg- ular 2n−1-gon, in cyclical order, satisfies (i)–(iv). Then one can assign to the vertices of a 2n-gon cyclically the following numbers: 1C1, 1C2, . . . , 1C2n−1, 2C2n−1, . . . , 2C2, 2C1. The conditions (i), (ii) obviously hold, while (iii) and (iv) follow from the inductive assumption.