Putnam 1996, Problem B-6

Let \( (a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n) \) be the vertices of a convex polygon which contains the origin in its interior. Prove that there exist positive real numbers \( x \) and \( y \) such that  
\[
(a_1, b_1)x^{a_1}y^{b_1} + (a_2, b_2)x^{a_2}y^{b_2} + \cdots + (a_n, b_n)x^{a_n}y^{b_n} = (0,0).
\]


Solution:
We will prove the claim assuming only that the convex hull of the points \((a_i, b_i)\) contains the origin in its interior. (Thanks to Marshall Buck for pointing out that the last three words are necessary in the previous sentence!) Let \(u = \log x, v = \log y\) so that the left-hand side of the given equation is  
\[
(a_1, b_1)\exp(a_1 u + b_1 v) + (a_2, b_2)\exp(a_2 u + b_2 v) + \cdots + (a_n, b_n)\exp(a_n u + b_n v). \tag{1}
\]  

Now note that (1) is the gradient of the function  
\[
f(u, v) = \exp(a_1 u + b_1 v) + \exp(a_2 u + b_2 v) + \cdots + \exp(a_n u + b_n v),
\]  
and so it suffices to show \(f\) has a critical point. We will in fact show \(f\) has a global minimum.  

Clearly we have  
\[
f(u, v) \geq \exp\left( \max_i (a_i u + b_i v) \right).
\]  

Note that this maximum is positive for \((u, v) \neq (0, 0)\): if we had \(a_i u + b_i v < 0\) for all \(i\), then the subset \(ur + vs < 0\) of the \(rs\)-plane would be a half-plane containing all of the points \((a_i, b_i)\), whose convex hull would then not contain the origin, a contradiction.  

The function \(\max_i (a_i u + b_i v)\) is clearly continuous on the unit circle \(u^2 + v^2 = 1\), which is compact. Hence it has a global minimum \(M > 0\), and so for all \(u, v\),  
\[
\max_i (a_i u + b_i v) \geq M \sqrt{u^2 + v^2}.
\]  

In particular, \(f \geq n + 1\) on the disk of radius \(\sqrt{(n + 1)/M}\). Since \(f(0, 0) = n\), the infimum of \(f\) is the same over the entire \(uv\)-plane as over this disk, which again is compact. Hence \(f\) attains its infimal value at some point in the disk, which is the desired global minimum.  

Noam Elkies has suggested an alternate solution as follows: for \(r > 0\), draw the loop traced by (1) as \((u, v)\) travels counterclockwise around the circle \(u^2 + v^2 = r^2\). For \(r = 0\), this of course has winding number 0 about any point, but for \(r\) large, one can show this loop has winding number 1 about the origin, so somewhere in between the loop must pass through the origin. (Proving this latter fact is a little tricky.)