Problem: (2000 Putnam – B1) Let be integers for . Assume for each , at least one of is odd. Show that exist integers such that is odd for at least values of , .
Solution: A pretty notation-heavy, strange, contrived problem. Let’s get started. Where do we get in the denominator? How about from the number of binary triples that contain at least one ? In fact we may simplify the problem so that are all in the set because we only care about even and odd. Cool.
Now let’s see… for which binary triples and is odd? Try it out. We will list the binary triples and give them variable names to simplify our lives.
Now we will write as where and . 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 and column signifies that is odd. Notice that each choice of makes four odd and each choice of has four possible to make it odd. Let denote the number of times is odd for . We want to show that there exists a such that . We know
is the number of times we have an odd sum if we apply every possible . But if we apply every we know from our table that each of the binary triples produces an odd for four of the seven . So in fact
But since the average of the ‘s is then , there must exist at least one such that , 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 . 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.
Leave a Reply
You must be logged in to post a comment.