15th Irish 2002 Problem B1 For which n can we find a cyclic shift a 1 , a 2 , ... , a n of 1, 2, 3, ... , n (ie i, i+1, i+2, ... , n, 1, 2, ... , i-1 for some i) and a permutation b 1 , b 2 , ... , b n of 1, 2, 3, ... , n such that 1 + a 1 + b 1 = 2 + a 2 + b 2 = ... = n + a n + b n ?
n odd Solution We have 1 + 2 + ... + n = ½ n(n+1). So (1 + a 1 + b 1 ) + ... + (n + a n + b n ) = 3n(n+1)/2. Hence we require each sum i + a i + b i = 3(n+1)/2. But each such sum is integral, so n must be odd. If n = 2m+1, take a 1 = m+1, a 2 = m+2, ... , a n = m, and b 1 = 2m+1, b 2 = 2m-1, b 3 = 2m-3, ... , b m+1 = 1, b m+2 = 2m, b m+3 = 2m-2, ... , b 2m+1 = 2. It is easy to check that each i + a i + b i = 3m+3. 15th Irish 2002 © John Scholes jscholes@kalva.demon.co.uk 15 June 2003 Last updated/corrected 15 Jun 03