Putnam 1996/B6 solution

Putnam 1996

Problem B6

The origin lies inside a convex polygon whose vertices have coordinates (a_i, b_i) for i = 1, 2, ... , n. Show that we can find x, y > 0 such that a₁x^a₁y^b₁ + a₂x^a₂y^b₂ + ... + a_nx^a_ny^b_n = 0 and b₁x^a₁y^b₁ + b₂x^a₂y^b₂ + ... + b_nx^a_ny^b_n = 0.

Solution

The basic idea is fairly obvious, but care is needed.

Convex may trigger thoughts of λ_i such that λ₁(a₁, b₁) + ... + λ_n(a_n, b_n) = 0, but that is a dead-end. The problem is that there are n λs, whereas we only want 2 parameters x and y. But if we look at the requirement for the first coordinate a₁x^a₁y^b₁ + a₂x^a₂y^b₂ + ... + a_nx^a_ny^b_n = 0, the a₁x^a₁ is strongly reminiscent of k x^k-1, and indeed we could make it more so by dividing through by x. In fact the requirement can be written as grad f(x,y) = 0, where f(x,y) = x^a₁y^b₁ + x^a₂y^b₂ + ... + x^a_ny^b_n. So it looks as though all we have to do is show that grad f = 0 in the first quadrant.

That is true. But care is needed. For example, suppose we take the three points as (1, -1), (-1, 1), (-1, -1), which puts the origin on the boundary of the polygon, rather than in its interior. Then f(x, y) = x/y + y/x + 1/xy. This is clearly > 2 for x, y > 0, but it decreases monotonically to 2 as we go to infinity along the line y = x, so there is no minimum (and in fact no stationary point at all) in the first quadrant. So simple-minded arguments to the effect that the a_i and b_i include both positive and negative values and hence the function tends to infinity as x, y tend to 0 or infinity are not enough. The point of the problem is precisely to establish that grad f (or grad of something) really does vanish in the first quadrant.

A more instructive case is f(x, y) = x/y + y/x + xy (which again puts the origin on the boundary of the polygon). If we take a ray y = kx, then f(x, kx) = 1/k + k + k x² which clearly does tend to infinity as we go to infinity along the ray. Also as if we fix x or y non-zero and let the other tend to zero, we clearly get f tending to infinity. So f tends to infinity as we approach the boundary of the first quadrant in any direction except towards the origin, where the function is evidently discontinuous. Unfortunately, this is enough to invalidate the argument that grad f must be zero in the first quadrant (as we easily see by setting grad f to zero and solving - there are no solutions). This strongly suggests that f is the wrong function to use, since the problems with the discontinuity of f at the origin will still be there even if we take the origin in the interior of the polygon.

A better behaved variant is f(u, v) = e^a₁u+b₁v + ... + e^a_nu+b_nv, which is defined on the plane with no problems at the origin. Now if we take any ray through the origin it passes between two vertices. The two vertices must subtend an angle less than π at the origin (since the origin is in the interior of the polygon), so the line to one of the two vertices makes an angle θ < π/2 with the ray. Take this vertex (a_k, b_k) [or in the degenerate case where the ray passes through a vertex, we simply take that vertex]. Now if (u, v) is a point on the ray, we have a_ku + b_kv = |(u, v)| h cos q, where |(u, v)| is the distance from the origin to the point (u, v) and h is the distance from the origin to the vertex. Hence a_ku + b_kv tends to infinity as we go to infinity along the ray and hence g(u, v) tends to infinity. Thus g tends to infinity in all directions. Hence grad g = 0 at some point in the plane. Putting x = e^u, y = e^v gives the result.

Putnam 1996