Putnam 2000, Problem B-1

Let $a_j, b_j, c_j$ be integers for $1 \leq j \leq N$. Assume for each $j$, at least one of $a_j, b_j, c_j$ is odd. Show that there exist integers $r, s, t$ such that $r a_j + s b_j + t c_j$ is odd for at least $4N/7$ values of $j$, $1 \leq j \leq N$.

Solution:
Consider the seven triples \((a,b,c)\) with \(a,b,c \in \{0,1\}\) not all zero. Notice that if \(r_j,s_j,t_j\) are not all even, then four of the sums \(ar_j + bs_j + ct_j\) with \(a,b,c \in \{0,1\}\) are even and four are odd. Of course the sum with \(a = b = c = 0\) is even, so at least four of the seven triples with \(a,b,c\) not all zero yield an odd sum. In other words, at least \(4N\) of the tuples \((a,b,c,j)\) yield odd sums. By the pigeonhole principle, there is a triple \((a,b,c)\) for which at least \(4N/7\) of the sums are odd.