24th CanMO 1992 Problem 5 There are 2n+1 cards. There are two cards with each integer from 1 to n and a joker. The cards are arranged in a line with the joker in the center position (with n cards each side of it). For which n < 11 can we arrange the cards so that the two cards with the number k have just k-1 cards between them (for k = 1, 2, ... , n)?
Consider the number of pairs (i, j) where i lies between the two j's or j lies between the two i's (if both i's or both j's do then we count both). The number must be 0 or 2, because we have either i ... i ... j ... j or i ... j ... i ... j or j ... i ... i ... j or i ... j ... j ... i or j ... i ... j ... i or j ... j ... i ... i. So the sum over all such pairs is even. But the sum is also 1 + 2 + ... + (n-1) = (n-1)n/2 less the number of pairs which straddle the joker. If n is even, then an even number of pairs must straddle the joker and if n is odd an odd number of pairs. So if n = 4m+1, then the sum is even less odd = odd, and so 4m+1 is impossible. Similarly, if n = 4m+2, then the sum is odd less even = odd, so 4m+2 is impossible. Thus we must have n = 0 or 3 mod 4. In particular, n = 1, 2, 5, 6, 9, 10 are impossible. We show below that n = 3, 4, 7, 8 are possible. 1 1 3 J 2 3 2 1 1 3 4 J 3 2 4 2 1 1 2 5 2 6 7 J 5 3 4 6 3 7 4 1 1 2 6 2 5 7 8 J 6 5 3 4 7 3 8 4 Comment. See also Chinese 86/B2. This is a variant on Langford's problem (which is the same except that there is no joker and we require k numbers between the two k's (not k-1). 24th CanMO 1992 © John Scholes jscholes@kalva.demon.co.uk 3 Aug 2002