Local Mathematical Competitions

Question

Prove that given any two permutations , S_n, there exists some function f : 1, , n -1, 1 such that we simultaneously have, for any indices 1 i j n, | _k=i^j f((k)) | 2 and | _k=i^j f((k)) | 2. Dan Schwarz

Accepted Answer

We will first prove it for the even case,

n = 2 m

. Consider the graph whose set of vertices is

{1, \dots, 2 m}

, and with red edges between

σ (2 k - 1)

and

σ (2 k)

, and blue edges between

τ (2 k - 1)

and

τ (2 k)

, where

1 \leq k \leq m

(notice that multiple edges may occur).

Clearly, each vertex is incident with one red edge and one blue edge, hence all vertex degrees are equal to 2. Therefore the graph is the union of disjoint cycles. Moreover, each such cycle is of even length, since its edges must be of alternating colours (the graph is thus bipartite).

Define

f

alternately taking values

- 1

and

1

along each of the cycles. Then the largest value any of the moduli can take is 2, when

i

is even and

j

is odd, since on consecutive pairs of odd/even indices the sum of the values of

f

is zero, along either

σ

or

τ

.

When

n

is odd, prolong

σ (n + 1) = τ (n + 1) = n + 1

to achieve the case treated in the above.