We are given N triples of integers (a_{1}, b_{1}, c_{1}), (a_{2}, b_{2}, c_{2}), ... (a_{N}, b_{N}, c_{N}). At least one member of each triple is odd. Show that we can find integers A, B, C such that at least 4N/7 of the N values A a_{i} + B b_{i} + C c_{i} are odd.

**Solution**

Evidently we are only interested in the residues of the integers mod 2. So there are 7 possibilities for the each triple: (1, 1, 1), (1, 1, 0), (1, 0, 1), (0, 1, 1), (1, 0, 0), (0, 1, 0), (0, 0, 1). These are also the possibilities for (A, B, C).

It is easy to verify that if we take any fixed triple (a, b, c), then just 4 of the 7 possibilities for Aa + Bb + Cc are odd. So given any set of N triples, just 4N of the 7N sums Aa_{i} + Bb_{i} + Cc_{i} are odd. These are divided into 7 sets (corresponding to the 7 possibilities for (A, B, C) ), so at least one of the these sets must contain at least 4N/7 odds.

© John Scholes

jscholes@kalva.demon.co.uk

1 Jan 2001