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

I’m a dirty liar

I hate to admit it, but it’s true. Why? Because I misleadingly stated that this blog contained math and shit, but so far it’s only shit. I am truly sorry.

Starting today, however, I’m going to try and make an honest man of myself. Every day (hopefully, but not likely), I’ll try to solve at least three interesting problems, and post my solutions on here. Most of these problems will have solutions that you can just look up, so in order to make myself marginally useful, I will include not only my solutions but also how I came by these solutions. I personally find this much more informative and helpful than reading a beautiful, elegant solution which appears to be conjured out of nowhere and which I never would have known how to come by on my own. Posting will also hopefully give me a better way to keep track of my progress, and maybe motivate me to actually keep working. Anyway, we’ll start off simple. I’m going to go through these “easy problems” first.

2014-A1. Prove that every nonzero coefficient of the Taylor series of (1-x+x^2)e^x about x = 0 is a rational number whose numerator (in lowest terms) is either 1 or a prime number.

It’s going to be hard to make any progress on this without knowing the Taylor series in question, so we should get that sorted out first. I’m not sure how much rigor the Putnam requires, but regardless I’m not going to prove that the Taylor series of the product is the product of the individual Taylor series. It’s not very hard and it’s more trouble to write out than it’s worth. Anyway, we compute the product:

(1-x+x^2)e^x = (1-x+x^2)\sum_{n=0}^\infty \frac{x^n}{n!} = \sum_{n=0}^\infty \frac{x^n-x^{n+1}+x^{n+2}}{n!}

We want to simplify things a little bit, so we group like terms. The x^n term is going to involve (n-2)! so we will have to separate the constant and linear terms. We get

= 1 + \sum_{n=2}^\infty \left(\frac{1}{n!}-\frac{1}{(n-1)!}+\frac{1}{(n-2)!}\right)x^n

Putting these three fractions over a common denominator, we see that the nth coefficient is

\frac{1-2n+n^2}{n!} = \frac{(n-1)^2}{n!} = \frac{n-1}{n(n-2)!}

for n > 2. (The coefficients of the constant and linear terms both meet the conditions so we don’t need to worry about them.)

At this point, I got a little caught up. We’re trying to prove something for all positive integers, and we have a formula to work with, so my first thought was to try induction. I monkeyed around for the bit:

Induction disaster

Yikes.

Maybe someone else can drag something useful out of this, but I can’t. So I abandoned this approach and started looking for another angle.

We want our numerator to be a prime or 1, so we should try to take advantage of the fact that the factorial in the denominator should cancel most of the factors in the numerator. We’ll proceed by casework.

1. n-1 is prime. There’s nothing to cancel it in the denominator, but we’re done anyway.

2. n-1 is composite. This actually breaks down into two sub-cases:

  • If n-1=pq, where p and q are distinct integers both greater than 1, then they will both be found in the product (n-2)!, and so the numerator will be 1 when reduced to lowest terms.
  • n-1=p^2 for some prime p. This is the only case where a composite number can’t be written as above. We’re okay in this case too, though, because one of the p factors will be canceled by (n-2)! and our numerator is prime.

This concludes the proof. Not a very hard problem, but for me it was a good exercise in knowing when to give up on an approach and try something new.