Each of the n triples (ri, si, ti) 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 ∑ ri, ∑ si, ∑ ti 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 an be the probability that the sums are 2n, 2n, 2n (type 1); bn that they are 2n - 1, 2n, 2n + 1 in some order (type 2); cn 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 an < bn/4 or an+1 < bn+1/4. It is easy to verify that:
an+1 = bn/6;
bn+1 >= an + bn/3 + cn/3;
cn+1 >= bn/3
Suppose that an > bn/4. Then bn+1 ≥ bn/4 + bn/3 + bn-1/9 = 7bn/12 + 2an/3 > 7bn/12 + bn/6 = 9bn/12 = 9an+1/2 > 4 an+1.
Thus we have the required an < bn/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 an+1 = bn/6, and bn+1 ≥ an + bn/3. But that is not enough, because an > bn/4 only implies an+1 < bn+1/(3 1/2). So we need at least one more type.]
© John Scholes
jscholes@kalva.demon.co.uk
12 Dec 1998