12th Chinese 1997 Problem B2 Let X be the set of residues mod 17. We regard two members of X as adjacent if they differ by 1, so 0 and 16 are adjacent. We say that a permutation of X is dispersive if it never takes two adjacent values to two adjacent values, and connective if it always takes two adjacent values to two adjacent values. What is the largest N for which we can find a permutation p on X such that p, p 2 , ... , p N-1 are all dispersive and p N is connective?
Rotations of X do not affect adjacency, so we can assume that 0 is fixed. If 1 and 16 are in the same cycle, then one must map to the other in 8 iterations or less. If 1 maps to 16, then 0 and 1 are adjacent and map to 0 and 16, which are adjacent. Similarly, if 16 maps to 1, then the adjacent 0 and 16 map to the adjacent 0 and 1. If 1 and 16 are in different cycles, then one of the cycles must have length 8 or less and hence 1 or 16 must map to itself in 8 iterations or less. If 1 maps to itself, then the adjacent 0 and 1 map to the adjacent 0 and 1. Similarly for 16. So certainly N <= 8. We can achieve N = 8 by the permutation p(n) = 3n (the rows give p, p 2 , p 3 , p 4 , p 5 , p 6 , p 7 , p 8 ): 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 3 6 9 12 15 1 4 7 10 13 16 2 5 8 11 14 0 9 1 10 2 11 3 12 4 13 5 14 6 15 7 16 8 0 10 3 13 6 16 9 2 12 5 15 8 1 11 4 14 7 0 13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4 0 5 10 15 3 8 13 1 6 11 16 4 9 14 2 7 12 0 15 15 11 9 7 5 3 1 16 14 12 10 8 6 4 2 0 11 5 16 10 4 15 9 3 14 8 2 13 7 1 12 6 0 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 12th Chinese 1997 © John Scholes jscholes@kalva.demon.co.uk 5 June 2002