We are given N triples of integers (a1, b1, c1), (a2, b2, c2), ... (aN, bN, cN). 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 ai + B bi + C ci are odd.
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 Aai + Bbi + Cci 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.
61st Putnam 2000
© John Scholes
1 Jan 2001