Parity Check. Topic: Logic/NT. Level: AIME/Olympiad.

Problem: (2000 Putnam - B1) Let $ a_j, b_j, c_j $ be integers for $ 1 \le j \le N $. Assume for each $ j $, at least one of $ a, b, c $ is odd. Show that exist integers $ r, s, t $ such that $ ra_j+sb_j+tc_j $ is odd for at least $ \frac{4N}{7} $ values of $ j $, $ 1 \le j \le N $.

Solution: A pretty notation-heavy, strange, contrived problem. Let's get started. Where do we get $ 7 $ in the denominator? How about from the number of binary triples that contain at least one $ 1 $? In fact we may simplify the problem so that $ a_j, b_j, c_j, r, s, t $ are all in the set $ \{0, 1\} $ because we only care about even and odd. Cool.

Now let's see... for which binary triples $ (a_j, b_j, c_j) $ and $ (r, s, t) $ is $ ra_j+sb_j+tc_j $ odd? Try it out. We will list the binary triples and give them variable names to simplify our lives.

$ A = (0, 0, 1) $
$ B = (0, 1, 0) $
$ C = (0, 1, 1) $
$ D = (1, 0, 0) $
$ E = (1, 0, 1) $
$ F = (1, 1, 0) $
$ G = (1, 1, 1) $.

Now we will write $ ra_j+sb_j+tc_j $ as $ U \cdot V $ where $ U = (r, s, t) $ and $ V = (a_j, b_j, c_j) $. We make the following table:


. A B C D E F G
A X . X . X . X
B . X X . . X X
C X X . . X X .
D . . . X X X X
E X . X X . X .
F . X X X X . .
G X X . X . . X


where an X in the entry in row $ U $ and column $ V $ signifies that $ U \cdot V $ is odd. Notice that each choice of $ (r, s, t) $ makes four odd and each choice of $ (a_j, b_j, c_j) $ has four possible $ (r, s, t) $ to make it odd. Let $ k_U $ denote the number of times $ U \cdot (a_j, b_j, c_j) $ is odd for $ 1 \le j \le N $. We want to show that there exists a $ U $ such that $ k_U \ge \frac{4N}{7} $. We know

$ \displaystyle \sum_{U=A}^G k_U $

is the number of times we have an odd sum if we apply every possible $ (r, s, t) $. But if we apply every $ (r, s, t) $ we know from our table that each of the $ N $ binary triples $ (a_j, b_j, c_j) $ produces an odd for four of the seven $ (r, s, t) $. So in fact

$ \displaystyle \sum_{U=A}^G k_U = 4N $.

But since the average of the $ k_U $'s is then $ \frac{4N}{7} $, there must exist at least one $ k_U $ such that $ k_U \ge \frac{4N}{7} $, as desired. QED.

--------------------

Comment: IMO, a very cool problem. Something that at first glance you sort of stare blankly at how they got such a ridiculous problem but then you realize it is a Putnam B1 so it couldn't possibly that bad, which is soon followed by your realization of the simplification to binary and finally the recognition of the seven as the number of binary triples with at least one $ 1 $. Yay!

--------------------

Practice Problem: I have seven light bulbs which are off and seven switches labeled with the binary triples above. A switch turns on a light bulb if the dot product (as above) of the number of the switch and the number of the light bulb is odd. Show that if I flip each switch once the light bulbs will still all be off.