Putnam 2013-A1

2013-A1. Recall that a regular icosahedron is a convex polyhedron having 12 vertices and 20 faces; the faces are congruent equilateral triangles. On each face of a regular icosahedron is written a nonnegative integer such that the sum of all 20 integers is 39. Show that there are two faces that share a vertex and have the same integer written on them.

 Obvious first step: what the hell does an icosahedron look like? Well, it looks like this:

Icosahedron

Also known as a d20. Nerd.

For any of you nerds that have played DnD before, this is a d20. Hope that helps.We’re looking for things that share a vertex, so we should probably look for things which share a vertex. We can see from the picture that about each vertex, there are five equilateral triangles, so we want to show that two of these have the same number. 

How can we do that? It seems hard to pin down one specific number that would have to occur twice. For instance, we can make 19 faces 2 and 1 face 1, or we could make 13 faces 3. In the first case, some 2’s will be touching, but in the second case, some 3’s will be touching. This is probably not going to work.

If we can’t prove what we want directly, we’ll have to try and prove it indirectly. That is, we’ll assume that the statement is false and find a contradiction. When is the statement false? Well, each of the 5 faces about each vertex must be different. Again, this statement by itself doesn’t help us a whole lot, because there a lot of nonnegative integers to choose from. So we look back at the problem statement for guidance. The fact that the sum of the faces must be 39 narrows our choices down a lot.

39 is not a particularly large number, not when we have 20 faces to consider AND the smallest number we can put on a face is 0. The average number on a face must be less than 2. This doesn’t give us a lot of wiggle room, so let’s see if we can find our contradiction here. We want to make our numbers as small as possible. If all the numbers about each vertex are different, that means that the smallest they can be is the integers 0, 1, 2, 3, and 4. Those add up to 10, so at best we can have a sum of 10 about each vertex. Great! If we can decompose the icosahedron into 4 set of these bad boys, we’ll be done, because then our sum is 40 which is too big.

…unfortunately, a quick glance at the picture above and a little experimentation will quickly show that this can’t be done. But we shouldn’t scrap this idea yet, because it seems like it’s going somewhere. The problem is that we can’t look at a bunch of these other things without having them overlap, in which case we’re overcounting some faces and not counting others at all. Instead of trying to pick some subset of these 5 faces around 1 vertex, let’s consider all of them instead. By the symmetry of the icosahedron, we’ll be overcounting each face the same amount of times.

We get one set of 5 faces around a vertex for each vertex, so there are 12 of them. If each has 0, 1, …,4 around it, that means the sum around each of these is 10, so the sum of all of them is 120. Note that all we’re doing is adding the value of a face each time it occurs in one of these sets of 5. That happens every time a vertex of the face is the center of a set of 5, which will happen once for each of its vertices. Since each face has three vertices, that means we’re adding each face to the total 3 times, so in total we end up with 3 times the sum of all the faces. Thus 3 * (sum of the faces) = 120, so the sum of the faces is 40. Last I checked, that’s greater than 39.

What does this all mean? Remember, what we just did was create the absolute smallest sum of all the faces when no two faces with a shared vertex have the same number on them. This lower bound ends up being greater than the sum which we know that the faces have, so it can’t be done! This means that our assumption must have been invalid, i.e. it’s not possible that there are 5 different numbers for each set of 5 faces around a vertex. So there exists some set of 5 about a vertex with the same number. These share a vertex, so we’re done.

I like this problem because a) it’s cool, and b) it shows that you shouldn’t always give up on an approach that seems promising at the first sign of trouble. Sometimes you just need make a few tiny adjustments to find yourself at the answer.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s