IMO 2002 SL C6

Origin: POL | Category: Combinatorics

Problem

Let n be an even positive integer. Show that there is a permutation x1, x2, . . . , xn of 1, 2, . . . , n such that for every 1 \leqi \leqn the number xi+1 is one of 2xi, 2xi −1, 2xi −n, 2xi −n −1 (where we take xn+1 = x1).

Solution

Write n = 2m. We shall define a directed graph G with vertices 1, . . . , m and edges labelled 1, 2, . . . , 2m in such a way that the edges issuing from i are labelled 2i −1 and 2i, and those entering it are labelled i and i + m. What we need is an Euler circuit in G, namely a closed path that passes each edge exactly once. Indeed, if xi is the ith edge in such a circuit, then xi enters some vertex j and xi+1 leaves it, so xi \equivj (mod m) and xi+1 = 2j −1 or 2j. Hence 2xi \equiv2j and xi+1 \equiv2xi or 2xi −1 (mod n), as required. The graph G is connected: by induction on k there is a path from 1 to k, since 1 is connected to j with 2j = k or 2j −1 = k, and there is an edge from j to k. Also, the in-degree and out-degree of each vertex of G are equal (to 2), and thus by a known result, G contains an Euler circuit.