a1, a2, ... , an is an arbitrary sequence of positive integers. A member of the sequence is picked at random. Its value is a. Another member is picked at random, independently of the first. Its value is b. Then a third, value c. Show that the probability that a + b + c is divisible by 3 is at least 1/4.
Solution
Let the prob of a value = 0, 1, 2 mod 3 be p, q, r respectively. So p + q + r = 1 and p, q, r are non-negative. If a = b mod 3, then to get a + b + c = 0 mod 3, we require c = a mod 3. So the prob of such events is p3 + q3 + r3. If the first two values are different mod 3, then the third must be different again, so the prob. is 6pqr. Thus we have to show that p3 + q3 + r3 + 6pqr >= 1/4.
1 = (p + q + r)3 = p3 + q3 + r3 + 6pqr + 3(p2q + pq2 + p2r + pr2 + q2r + qr2). So we have to show that (p2q + pq2 + p2r + pr2 + q2r + qr2) <= 1/4. Or p2(q + r) + p(q2 + r2) + qr(q + r) <= 1/4, or p2(1 - p) + p(q + r)2 + qr(q + r - 2p) ≤ 1/4, or p2(1 - p) + p(1 - p)2 + qr(1 - 3p) = p(1 - p) + qr(1 - 3p) ≤ 1/4.
If p ≥ 1/3, then we maximise p(1 - p) + qr(1 - 3p) by taking qr = 0 and p = 1/2 to maximise p(1 - p). Thus the maximum is 1/4, achieved at p = 1/2, q = 1/2, r = 0 and p = 1/2, q = 0, r = 1/2. But because of the symmetry, there is no loss of generality in assuming that p ≥ q ≥ r, so p must be ≥ 1/3. So the maximum value is 1/4.
© John Scholes
jscholes@kalva.demon.co.uk
20 Aug 2002