Mathematical Food for Thought

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.

Problem: (2001 Putnam – B1) Let be an even positive integer. Write the numbers in the squares of an grid so that the th row, from left to right, is

.

Color the squares of the grid so that half of the squares in each row and in each column are red and the other half are black (a checkerboard coloring is one possibility). Prove that for each coloring, the sum of the numbers on the red squares is equal to the sum of the numbers on the black squares.

Solution: Consider all the values of the red squares and all the values of the black squares . For each square (of any color) , let

,

where and are the row and column of the square corresponding to . We want to show that

.

But we have

and .

Since each row has half red and half black, we have

for each row and consequently the whole board. Similarly, since each column has half red and half black, we have

for each column and hence the whole board. Adding these two equalities together, we obtain

as desired. QED.

——————–

Comment: Not too hard intuitively, but slightly difficult to put down a rigorous proof; assigning variables can be a good way of going about solving word problems. It might simplify the problem down to some simple algebra, which is good.

——————–

Practice Problem: Let be a positive even integer. In how many ways can we fill an board with ’s and ’s such that the sum of each row and column is zero?

Problem: (2002 Putnam – B2) Consider a polyhedron with at least five faces such that exactly three edges emerge from each of its vertices.

Two players play the following game:

Each player, in turn, signs his or her name on a previously unsigned face. The winner is the player who first succeeds in signing three faces that share a common vertex.

Show that the player who signs first will always win by playing as well as possible.

Solution: First, we claim that the polyhedron contains a face with at least four sides. To prove this, suppose the contrary, that all faces are triangles. Take any three faces that share a vertex. Called the shared vertex and the other vertices . Since each vertex already has three edges emerging from it, we cannot add a new vertex; hence we will have at most four faces. Contradiction. So there exists a face with at least four sides.

Let be this face. We claim that if Player 1 signs on first, he or she can win on the third move. Let be the faces that share an edge with , where because there are at least four such faces. If Player 2 does not sign on any of these faces, Player 1 can sign on any and the following turn can win with or (indices taken modulo ) since Player 2 cannot block both of them. If Player 2 does sign on , then Player 1 signs on with (again, modulo ), which exists because . Then again Player 1 can sign the next turn to win, at most one of which can be blocked by Player 2. QED.

——————–

Comment: Not really too hard of a problem; the only real challenge was showing that there exists a face with at least four edges. And the proof of that was not complex either. Just simple logic and a bit of geometry to finish it.

——————–

Practice Problem: Suppose an ant is on the vertex of a cube. Each second, it can move along one edge. What is the probability that after seconds it will end up at the opposite vertex?

Problem: (2002 Putnam – A2) Given any five points on a sphere, show that some four of them must lie on a closed hemisphere.

Solution: Well, that doesn’t sound so bad. And, in fact, it really isn’t. First, let’s maximize the number of points on the boundary of a great circle; this is, in general, two. We can’t arbitrarily choose three points and always draw a great circle through all three (think about it).

So now we have a great circle through two points. Well, maybe these hemispheres work. There are three points left, so by the Pigeonhole Principle one of the closed hemispheres has at least four points. Whoa, we’re done. QED.

——————–

Comment: That was almost too simple. Especially for a Putnam problem; shows you how knowing how to think can take you a long ways even if you don’t know much math.

——————–

Practice Problem: Can you generalize this to an -dimensional sphere?

Taking a break from math, here is an interesting puzzle. It’s called Kakuro and it’s similar to Sudoku, but not really the same either. Basically, you have a lot of open squares and some dark squares with a diagonal slash through them (and some irrelevent filled dark squares). These dark squares might have a number in the lower left corner and/or a number in the upper right corner.

Lower Left – All the consecutive blank spaces below contain different numbers (1-9) and sum to the number in the lower left corner of the dark square.

Upper Right – All the consecutive blank spaces to the right contain different numbers (1-9) and sum to the number in the upper right corner of the dark square.

These puzzles all have a unique solution that can be determined through logic (no guessing is necessary), but they can be very difficult! Take a stab at it. If it’s too easy, check out some of the other puzzles on the site.