MathDB

3

Part of 2015 Turkey EGMO TST

Problems(1)

Permutations of (1,2,...,2015)

Source: Turkey EGMO TST 2015 P3

8/7/2016
Given a 20152015-tuple (a1,a2,…,a2015)(a_1,a_2,\ldots,a_{2015}) in each step we choose two indices 1≤k,l≤20151\le k,l\le 2015 with aka_k even and transform the 20152015-tuple into (a1,…,ak2,…,al+ak2,…,a2015)(a_1,\ldots,\dfrac{a_k}{2},\ldots,a_l+\dfrac{a_k}{2},\ldots,a_{2015}). Prove that starting from (1,2,…,2015)(1,2,\ldots,2015) in finite number of steps one can reach any permutation of (1,2,…,2015)(1,2,\ldots,2015).
combinatorics