Let p, q, n be three positive integers with p + q < n. Let x0, x1, ... , xn be integers such that x0 = xn = 0, and for each 1 ≤ i ≤ n, xi - xi-1 = p or -q. Show that there exist indices i < j with (i, j) not (0, n) such that xi = xj.
Solution
Let xi - xi-1 = p occur r times and xi - xi-1 = -q occur s times. Then r + s = n and pr = qs. If p and q have a common factor d, the yi = xi/d form a similar set with p/d and q/d. If the result is true for the yi then it must also be true for the xi. So we can assume that p and q are relatively prime. Hence p divides s. Let s = kp. If k = 1, then p = s and q = r, so p + q = r + s = n. But we are given p + q < n. Hence k > 1. Let p + q = n/k = h.
Up to this point everything is fairly obvious and the result looks as though it should be easy, but I did not find it so. Some fiddling around with examples suggested that we seem to get xi = xj for j = i + h. We observe first that xi+h - xi must be a multiple of h. For suppose e differences are p, and hence h-e are -q. Then xi+h - xi = ep - (h - e)q = (e - q)h.
The next step is not obvious. Let di = xi+h - xi. We know that all dis are multiples of h. We wish to show that at least one is zero. Now di+1 - di = (xi+h+1 - xi+h) - (xi+1 - xi) = (p or -q) - (p or -q) = 0, h or -h. So if neither of di nor di+1 are zero, then either both are positive or both are negative (a jump from positive to negative would require a difference of at least 2h). Hence if none of the dis are zero, then all of them are positive, or all of them are negative. But d0 + dh + ... + dkh is a concertina sum with value xn - x0 = 0. So this subset of the dis cannot all be positive or all negative. Hence at least one di is zero.
© John Scholes
jscholes@kalva.demon.co.uk
22 Oct 1998
Last corrected/updated 21 Aug 03