Putnam 2000/B1 solution

61st Putnam 2000

Problem B1

We are given N triples of integers (a₁, b₁, c₁), (a₂, b₂, c₂), ... (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.

61st Putnam 2000