Each of the n triples (r_{i}, s_{i}, t_{i}) is a randomly chosen permutation of (1, 2, 3) and each triple is chosen independently. Let p be the probability that each of the three sums ∑ r_{i}, ∑ s_{i}, ∑ t_{i} equals 2n, and let q be the probability that they are 2n - 1, 2n, 2n + 1 in some order. Show that for some n ≥ 1995, 4p ≤ q.

**Solution**

*Fairly hard. Note the typically misleading suggestion that we need n large.*

Let a_{n} be the probability that the sums are 2n, 2n, 2n (type 1); b_{n} that they are 2n - 1, 2n, 2n + 1 in some order (type 2); c_{n} that they are 2n - 2, 2n + 1, 2n + 1 or 2n - 1, 2n - 1, 2n + 2 in some order (type 3). We show that for any n, either a_{n} < b_{n}/4 or a_{n+1} < b_{n+1}/4. It is easy to verify that:

a_{n+1} = b_{n}/6;

b_{n+1} >= a_{n} + b_{n}/3 + c_{n}/3;

c_{n+1} >= b_{n}/3

Suppose that a_{n} > b_{n}/4. Then b_{n+1} ≥ b_{n}/4 + b_{n}/3 + b_{n-1}/9 = 7b_{n}/12 + 2a_{n}/3 > 7b_{n}/12 + b_{n}/6 = 9b_{n}/12 = 9a_{n+1}/2 > 4 a_{n+1}.

Thus we have the required a_{n} < b_{n}/4 for either n = 1995 or n = 1996.

[This looks deceptively easy. But how did we know that the inequality is alternately true and false? How do we know how many types of patterns to look at? The second question is easier. We might start with just type 1 and type 2. Then we get a_{n+1} = b_{n}/6, and b_{n+1} ≥ a_{n} + b_{n}/3. But that is not enough, because a_{n} > b_{n}/4 only implies a_{n+1} < b_{n+1}/(3 1/2). So we need at least one more type.]

© John Scholes

jscholes@kalva.demon.co.uk

12 Dec 1998