MathDB

12

Part of 2011 Ukraine Team Selection Test

Problems(1)

| a_ {i +1} - a_ i |= 1given, wanted a _ 1 - a _ {2n} = n iff 1<= a _ {2k} <= n

Source: Ukraine TST 2011 p12

5/7/2020
Let n n be a natural number. Consider all permutations (a1, …, a2n) ({{a} _ {1}}, \ \ldots, \ {{a} _ {2n}}) of the first 2n 2n natural numbers such that the numbers ∣ai+1−ai∣, i=1, …, 2n−1, | {{a} _ {i +1}} - {{a} _ {i}} |, \ i = 1, \ \ldots, \ 2n-1, are pairwise different. Prove that a1−a2n=n {{a} _ {1}} - {{a} _ {2n}} = n if and only if 1≤a2k≤n 1 \le {{a} _ {2k}} \le n for all k=1, …, n k = 1, \ \ldots, \ n .
permutationscombinatorics