On 2012 Putnam problem B2

This post continues my effort to write up solutions (aimed at students) to the problems on this year’s Putnam exam. Here is problem B2:

Let P be a given (non-degenerate) polyhedron. Prove that there is a constant c(P) > 0 with the following property: If a collection of n balls whose volumes sum to V contains the entire surface of P, then n > c(P)/V^2.

Spoiler alert: the solution is below Nyan Cat.

poptart1red1

Initial comments

Sometimes Putnam problems involve situations that seem complicated but allow for various simplifications that make the problems tractable. For this problem, I can think of a couple of complicating factors:

  • It involves an arbitrary polyhedron, whose specific characteristics could be weird.
  • It involves covering the surface of the polyhedron by (spherical) balls, which would necessarily require some “inefficient” overlapping.

It would be too difficult to address issues like these in the 30 minutes that you (in principle) should allocate to this problem, so you have to hope that you can safely ignore these issues. In the end, you should write down a (more or less) ironclad proof, but sometimes the road to a proof includes leaps of faith.

As a completely separate issue, I found it helpful to rewrite the desired inequality in the form nV^2 > c(P). Writing it like this allows you to interpret the problem as asking you to show that nV^2 can’t “go to zero”, since it will always be bigger than the positive constant c(P). So maybe you can cover the surface with balls whose total volume is almost zero, but to do so you would need a lot of them.

Understanding the problem in this way helped me to have a better feel for what I was actually trying to prove. In general, when solving Putnam problems (or any problems for that matter) it can be helpful to restate them in (relatively) ordinary language.

Solution

In an effort to avoid the first issue mentioned above, I’m going to “forget” that we have a polyhedron and only consider a polygon. It might seem like I’m just arbitrarily changing the problem, but I’m not. The surface of the polyhedron is made up of polygonal faces, so if you can prove that nV^2 can’t “go to zero” for a polygon, then you can deduce that it can’t “go to zero” for a polyhedron.

So, suppose that there is a collection of n balls containing a polygon with area A. The maximum area that a ball of radius r can cover is \pi r^2, so if the radii of the balls are r_1, \dots, r_n, then

\pi \sum_{i=1}^n r_i^2 \geq A.

Because of the overlapping mentioned above, you could probably do better than this (depending on n and the shape of the polygon, the sum might be substantially bigger than A). But, since I don’t want to mess around with the overlapping issue, I’m going to take a leap of faith and hope that this inequality is good enough to derive the result we want.

The total volume is

V = \frac{4\pi}{3}\sum_{i=1}^n r_i^3.

We’re worried about whether nV^2 can be very small. Since we’re treating n as fixed (but arbitrary), the only thing we’re left to worry about is how small V can be. And the smallest possible values of V will occur when all the r_i are equal to each other (This fact and others like it are useful for Putnam problems, so I’ll explain it in a broader context in the appendix below).

So, without loss of generality, we can assume that all the balls have the same radius r. In this case, the above inequality becomes

n\pi r^2 \geq A,

so we can see that the smallest possible value of r is \sqrt {\frac{A}{n\pi}}. This means the smallest possible value of V is

\frac{4n\pi}{3}\left(\sqrt{\frac{A}{n\pi}}\right)^3,

and the smallest possible value of nV^2 is

\frac{16n^3 \pi^2}{9}\left(\frac{A}{n\pi}\right)^3 = \frac{16A^3}{9\pi}.

And that does it! The key point is that all the n‘s cancelled, giving a lower bound for nV^2 that only depends on the area of the polygon, and guaranteeing that nV^2 can’t “go to zero”.

QED

Appendix

You might remember from multivariable calculus a constrained optimization problem like this: Minimize x^2 + y^2 subject to the constraint x + y = a, where a is a constant. One method of solving this is with a Lagrange multiplier \lambda, which would lead to the system of equations 2x + \lambda = 0, 2y + \lambda = 0, x+y=a. Solving this system, you’d find that the minimum value occurs when x = y = a/2.

The advantage of the Lagrange multiplier approach is that it works with almost no additional effort for many variables (e.g. minimize \sum x_i^2 subject to the constraint \sum x_i = a), and with other variations on the problem (such as the one we encountered above, which, give or take some constants, asked to minimize \sum r_i^3 subject to the constraint \sum r_i^2 = a). And in all these cases, the minimum value occurs when all the variables are equal to each other.

I don’t know what the grading scheme is for the Putnam, but I would guess that you could have used this fact without giving a detailed justification, since it’s considered to be “well-known”. I’ve seen other Putnam problems that use it (for example, see A1 on the 2000 exam), so it’s worth remembering in case it comes up again.

Advertisements
Tagged , , , ,

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

%d bloggers like this: