\documentclass[amssymb,twocolumn]{revtex4} \usepackage{times,amsmath,latexsym,epsfig} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\ZZ}{\mathbb{Z}} \begin{document} \title{Solutions to the 62nd William Lowell Putnam Mathematical Competition \\ Saturday, December 1, 2001} \author{Manjul Bhargava, Kiran Kedlaya, and Lenny Ng} \maketitle \begin{itemize} \item[A--1] The hypothesis implies $((b*a)*b)*(b*a)=b$ for all $a,b\in S$ (by replacing $a$ by $b*a$), and hence $a*(b*a)=b$ for all $a,b\in S$ (using $(b*a)*b = a$). \item[A--2] Let $P_n$ denote the desired probability. Then $P_1=1/3$, and, for $n>1$, \begin{align*} P_n &= \left(\frac{2n}{2n+1}\right) P_{n-1} +\left(\frac{1}{2n+1}\right) (1-P_{n-1}) \\ &= \left(\frac{2n-1}{2n+1}\right)P_{n-1} + \frac{1}{2n+1}. \end{align*} The recurrence yields $P_2=2/5$, $P_3=3/7$, and by a simple induction, one then checks that for general $n$ one has $P_n=n/(2n+1)$. Note: Richard Stanley points out the following noninductive argument. Put $f(x) = \prod_{k=1}^n (x+2k)/(2k+1)$; then the coefficient of $x^i$ in $f(x)$ is the probability of getting exactly $i$ heads. Thus the desired number is $(f(1) - f(-1))/2$, and both values of $f$ can be computed directly: $f(1) = 1$, and \[ f(-1) = \frac{1}{3} \times \frac{3}{5} \times \cdots \times \frac{2n-1}{2n+1} = \frac{1}{2n+1}. \] \item[A--3] By the quadratic formula, if $P_m(x)=0$, then $x^2=m\pm 2\sqrt{2m}+2$, and hence the four roots of $P_m$ are given by $S = \{\pm\sqrt{m}\pm\sqrt{2}\}$. If $P_m$ factors into two nonconstant polynomials over the integers, then some subset of $S$ consisting of one or two elements form the roots of a polynomial with integer coefficients. First suppose this subset has a single element, say $\sqrt{m} \pm \sqrt{2}$; this element must be a rational number. Then $(\sqrt{m} \pm \sqrt{2})^2 = 2 + m \pm 2 \sqrt{2m}$ is an integer, so $m$ is twice a perfect square, say $m = 2n^2$. But then $\sqrt{m} \pm \sqrt{2} = (n\pm 1)\sqrt{2}$ is only rational if $n=\pm 1$, i.e., if $m = 2$. Next, suppose that the subset contains two elements; then we can take it to be one of $\{\sqrt{m} \pm \sqrt{2}\}$, $\{\sqrt{2} \pm \sqrt{m}\}$ or $\{\pm (\sqrt{m} + \sqrt{2})\}$. In all cases, the sum and the product of the elements of the subset must be a rational number. In the first case, this means $2\sqrt{m} \in \QQ$, so $m$ is a perfect square. In the second case, we have $2 \sqrt{2} \in \QQ$, contradiction. In the third case, we have $(\sqrt{m} + \sqrt{2})^2 \in \QQ$, or $m + 2 + 2\sqrt{2m} \in \QQ$, which means that $m$ is twice a perfect square. We conclude that $P_m(x)$ factors into two nonconstant polynomials over the integers if and only if $m$ is either a square or twice a square. Note: a more sophisticated interpretation of this argument can be given using Galois theory. Namely, if $m$ is neither a square nor twice a square, then the number fields $\QQ(\sqrt{m})$ and $\QQ(\sqrt{2})$ are distinct quadratic fields, so their compositum is a number field of degree 4, whose Galois group acts transitively on $\{\pm \sqrt{m} \pm \sqrt{2}\}$. Thus $P_m$ is irreducible. \item[A--4] Choose $r,s,t$ so that $EC = rBC, FA = sCA, GB = tCB$, and let $[XYZ]$ denote the area of triangle $XYZ$. Then $[ABE] = [AFE]$ since the triangles have the same altitude and base. Also $[ABE] = (BE/BC) [ABC] = 1-r$, and $[ECF] = (EC/BC)(CF/CA)[ABC] = r(1-s)$ (e.g., by the law of sines). Adding this all up yields \begin{align*} 1 &= [ABE] + [ABF] + [ECF] \\ &= 2(1-r) + r(1-s) = 2-r-rs \end{align*} or $r(1+s) = 1$. Similarly $s(1+t) = t(1+r) = 1$. Let $f: [0, \infty) \to [0, \infty)$ be the function given by $f(x) = 1/(1+x)$; then $f(f(f(r))) = r$. However, $f(x)$ is strictly decreasing in $x$, so $f(f(x))$ is increasing and $f(f(f(x)))$ is decreasing. Thus there is at most one $x$ such that $f(f(f(x))) = x$; in fact, since the equation $f(z) = z$ has a positive root $z = (-1 + \sqrt{5})/2$, we must have $r=s=t=z$. We now compute $[ABF] = (AF/AC) [ABC] = z$, $[ABR] = (BR/BF) [ABF] = z/2$, analogously $[BCS] = [CAT] = z/2$, and $[RST] = |[ABC] - [ABR] - [BCS] - [CAT]| = |1 - 3z/2| = \frac{7 - 3 \sqrt{5}}{4}$. Note: the key relation $r(1+s) = 1$ can also be derived by computing using homogeneous coordinates or vectors. \item[A--5] Suppose $a^{n+1} - (a+1)^n = 2001$. Notice that $a^{n+1} + [(a+1)^n - 1]$ is a multiple of $a$; thus $a$ divides $2002 = 2 \times 7 \times 11 \times 13$. Since $2001$ is divisible by 3, we must have $a \equiv 1 \pmod{3}$, otherwise one of $a^{n+1}$ and $(a+1)^n$ is a multiple of 3 and the other is not, so their difference cannot be divisible by 3. Now $a^{n+1} \equiv 1 \pmod{3}$, so we must have $(a+1)^n \equiv 1 \pmod{3}$, which forces $n$ to be even, and in particular at least 2. If $a$ is even, then $a^{n+1} - (a+1)^n \equiv -(a+1)^n \pmod{4}$. Since $n$ is even, $-(a+1)^n \equiv -1 \pmod{4}$. Since $2001 \equiv 1 \pmod{4}$, this is impossible. Thus $a$ is odd, and so must divide $1001 = 7 \times 11 \times 13$. Moreover, $a^{n+1} - (a+1)^n \equiv a \pmod{4}$, so $a \equiv 1 \pmod{4}$. Of the divisors of $7 \times 11 \times 13$, those congruent to 1 mod 3 are precisely those not divisible by 11 (since 7 and 13 are both congruent to 1 mod 3). Thus $a$ divides $7 \times 13$. Now $a \equiv 1 \pmod{4}$ is only possible if $a$ divides $13$. We cannot have $a=1$, since $1 - 2^n \neq 2001$ for any $n$. Thus the only possibility is $a = 13$. One easily checks that $a=13, n=2$ is a solution; all that remains is to check that no other $n$ works. In fact, if $n > 2$, then $13^{n+1} \equiv 2001 \equiv 1 \pmod{8}$. But $13^{n+1} \equiv 13 \pmod{8}$ since $n$ is even, contradiction. Thus $a=13, n=2$ is the unique solution. Note: once one has that $n$ is even, one can use that $2002 =a^{n+1} + 1 - (a+1)^n$ is divisible by $a+1$ to rule out cases. \item[A--6] The answer is yes. Consider the arc of the parabola $y=Ax^2$ inside the circle $x^2+(y-1)^2 = 1$, where we initially assume that $A > 1/2$. This intersects the circle in three points, $(0,0)$ and $(\pm \sqrt{2A-1}/A, (2A-1)/A)$. We claim that for $A$ sufficiently large, the length $L$ of the parabolic arc between $(0,0)$ and $(\sqrt{2A-1}/A, (2A-1)/A)$ is greater than $2$, which implies the desired result by symmetry. We express $L$ using the usual formula for arclength: \begin{eqnarray*} L &=& \int_0^{\sqrt{2A-1}/A} \sqrt{1+(2Ax)^2} \, dx \\ &=& \frac{1}{2A} \int_0^{2\sqrt{2A-1}} \sqrt{1+x^2} \, dx \\ &=& 2 + \frac{1}{2A} \left( \int_0^{2\sqrt{2A-1}} (\sqrt{1+x^2}-x)\,dx -2\right), \end{eqnarray*} where we have artificially introduced $-x$ into the integrand in the last step. Now, for $x \geq 0$, \[ \sqrt{1+x^2}-x = \frac{1}{\sqrt{1+x^2}+x} > \frac{1}{2\sqrt{1+x^2}} \geq \frac{1}{2(x+1)}; \] since $\int_0^\infty dx/(2(x+1))$ diverges, so does $\int_0^\infty (\sqrt{1+x^2}-x)\,dx$. Hence, for sufficiently large $A$, we have $\int_0^{2\sqrt{2A-1}} (\sqrt{1+x^2}-x)\,dx > 2$, and hence $L > 2$. Note: a numerical computation shows that one must take $A > 34.7$ to obtain $L > 2$, and that the maximum value of $L$ is about $4.0027$, achieved for $A \approx 94.1$. \item[B--1] Let $R$ (resp.\ $B$) denote the set of red (resp.\ black) squares in such a coloring, and for $s\in R\cup B$, let $f(s)n+g(s)+1$ denote the number written in square $s$, where $0\leq f(s),g(s)\leq n-1$. Then it is clear that the value of $f(s)$ depends only on the row of $s$, while the value of $g(s)$ depends only on the column of $s$. Since every row contains exactly $n/2$ elements of $R$ and $n/2$ elements of $B$, \[ \sum_{s\in R} f(s) = \sum_{s\in B} f(s) .\] Similarly, because every column contains exactly $n/2$ elements of $R$ and $n/2$ elements of $B$, \[ \sum_{s\in R} g(s) = \sum_{s\in B} g(s) .\] It follows that \[\sum_{s\in R} f(s)n+g(s)+1 = \sum_{s\in B} f(s)n+g(s)+1,\] as desired. Note: Richard Stanley points out a theorem of Ryser (see Ryser, \textit{Combinatorial Mathematics}, Theorem~3.1) that can also be applied. Namely, if $A$ and $B$ are $0-1$ matrices with the same row and column sums, then there is a sequence of operations on $2 \times 2$ matrices of the form \[ \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \to \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \] or vice versa, which transforms $A$ into $B$. If we identify 0 and 1 with red and black, then the given coloring and the checkerboard coloring both satisfy the sum condition. Since the desired result is clearly true for the checkerboard coloring, and performing the matrix operations does not affect this, the desired result follows in general. \item[B--2] By adding and subtracting the two given equations, we obtain the equivalent pair of equations \begin{align*} 2/x &= x^4 + 10x^2y^2 + 5y^4 \\ 1/y &= 5x^4 + 10x^2y^2 + y^4. \end{align*} Multiplying the former by $x$ and the latter by $y$, then adding and subtracting the two resulting equations, we obtain another pair of equations equivalent to the given ones, \[ 3 = (x+y)^5, \qquad 1 = (x-y)^5. \] It follows that $x = (3^{1/5}+1)/2$ and $y = (3^{1/5}-1)/2$ is the unique solution satisfying the given equations. \item[B--3] Since $(k-1/2)^2 = k^2-k+1/4$ and $(k+1/2)^2 = k^2+k+1/4$, we have that $\langle n \rangle = k$ if and only if $k^2-k+1 \leq n \leq k^2+k$. Hence \begin{eqnarray*} \sum_{n=1}^\infty \frac{2^{\langle n \rangle} + 2^{-\langle n \rangle}}{2^n} &=& \sum_{k=1}^\infty \sum_{n, \langle n \rangle = k} \frac{2^{\langle n \rangle} + 2^{-\langle n \rangle}}{2^n} \\ &=& \sum_{k=1}^\infty \sum_{n=k^2-k+1}^{k^2+k} \frac{2^k+2^{-k}}{2^n} \\ &=& \sum_{k=1}^\infty (2^k+2^{-k})(2^{-k^2+k}-2^{-k^2-k}) \\ &=& \sum_{k=1}^\infty (2^{-k(k-2)} - 2^{-k(k+2)}) \\ &=& \sum_{k=1}^\infty 2^{-k(k-2)} - \sum_{k=3}^\infty 2^{-k(k-2)} \\ &=& 3. \end{eqnarray*} Alternate solution: rewrite the sum as $\sum_{n=1}^\infty 2^{-(n+\langle n \rangle)} + \sum_{n=1}^\infty 2^{-(n - \langle n \rangle)}$. Note that $\langle n \rangle \neq \langle n+1 \rangle$ if and only if $n = m^2+m$ for some $m$. Thus $n + \langle n \rangle$ and $n - \langle n \rangle$ each increase by 1 except at $n=m^2+m$, where the former skips from $m^2+2m$ to $m^2+2m+2$ and the latter repeats the value $m^2$. Thus the sums are \[ \sum_{n=1}^\infty 2^{-n} - \sum_{m=1}^\infty 2^{-m^2} + \sum_{n=0}^\infty 2^{-n} + \sum_{m=1}^\infty 2^{-m^2} = 2+1=3. \] \item[B--4] For a rational number $p/q$ expressed in lowest terms, define its {\it height} $H(p/q)$ to be $|p|+|q|$. Then for any $p/q\in S$ expressed in lowest terms, we have $H(f(p/q))=|q^2-p^2|+|pq|$; since by assumption $p$ and $q$ are nonzero integers with $|p|\neq |q|$, we have \begin{align*} H(f(p/q)) - H(p/q) &= |q^2-p^2|+|pq| -|p| -|q| \\ &\geq 3+ |pq| -|p| - |q| \\ &= (|p|-1)(|q|-1) + 2 \geq 2 . \end{align*} It follows that $f^{(n)}(S)$ consists solely of numbers of height strictly larger than $2n+2$, and hence \[\cap_{n=1}^\infty f^{(n)}(S) = \emptyset.\] Note: many choices for the height function are possible: one can take $H(p/q) = \max{|p|, |q|}$, or $H(p/q)$ equal to the total number of prime factors of $p$ and $q$, and so on. The key properties of the height function are that on one hand, there are only finitely many rationals with height below any finite bound, and on the other hand, the height function is a sufficiently ``algebraic'' function of its argument that one can relate the heights of $p/q$ and $f(p/q)$. \item[B--5] Note that $g(x) = g(y)$ implies that $g(g(x)) = g(g(y))$ and hence $x = y$ from the given equation. That is, $g$ is injective. Since $g$ is also continuous, $g$ is either strictly increasing or strictly decreasing. Moreover, $g$ cannot tend to a finite limit $L$ as $x \to +\infty$, or else we'd have $g(g(x)) - ag(x) = bx$, with the left side bounded and the right side unbounded. Similarly, $g$ cannot tend to a finite limit as $x \to -\infty$. Together with monotonicity, this yields that $g$ is also surjective. Pick $x_0$ arbitrary, and define $x_n$ for all $n \in \ZZ$ recursively by $x_{n+1} = g(x_n)$ for $n > 0$, and $x_{n-1} = g^{-1}(x_n)$ for $n<0$. Let $r_1 = (a + \sqrt{a^2+4b})/2$ and $r_2 = (a - \sqrt{a^2+4b})/2$ and $r_2$ be the roots of $x^2 - ax-b = 0$, so that $r_1 > 0 > r_2$ and $1 > |r_1| > |r_2|$. Then there exist $c_1, c_2 \in \RR$ such that $x_n = c_1 r_1^n + c_2 r_2^n$ for all $n \in \ZZ$. Suppose $g$ is strictly increasing. If $c_2 \neq 0$ for some choice of $x_0$, then $x_n$ is dominated by $r_2^n$ for $n$ sufficiently negative. But taking $x_n$ and $x_{n+2}$ for $n$ sufficiently negative of the right parity, we get $0 < x_n < x_{n+2}$ but $g(x_n) > g(x_{n+2})$, contradiction. Thus $c_2 = 0$; since $x_0 = c_1$ and $x_1 = c_1 r_1$, we have $g(x) = r_1 x$ for all $x$. Analogously, if $g$ is strictly decreasing, then $c_2 = 0$ or else $x_n$ is dominated by $r_1^n$ for $n$ sufficiently positive. But taking $x_n$ and $x_{n+2}$ for $n$ sufficiently positive of the right parity, we get $0 < x_{n+2} 0$ such that \begin{equation} \label{eq1} a_k < a_n + m(k-n) \qquad \forall k \geq 1. \end{equation} We first show that $n=1$ satisfies (\ref{eq1}). The condition $a_k/k \to 0$ as $k \to \infty$ implies that $(a_k - a_1)/(k-1) \to 0$ as well. Thus the set $\{(a_k-a_1)/(k-1)\}$ has an upper bound $m$, and now $a_k \leq a_1 + m(k-1)$, as desired. Next, we show that given one $n$ satisfying (\ref{eq1}), there exists a larger one also satisfying (\ref{eq1}). Again, the condition $a_k/k \to 0$ as $k \to \infty$ implies that $(a_k-a_n)/(k-n) \to 0$ as $k \to \infty$. Thus the sequence $\{(a_k-a_n)/(k-n)\}_{k>n}$ has a maximum element; suppose $k = r$ is the largest value that achieves this maximum, and put $m = (a_r -a_n)/(r-n)$. Then the line through $(r, a_r)$ of slope $m$ lies strictly above $(k, a_k)$ for $k > r$ and passes through or lies above $(k, a_k)$ for $k< r$. Thus (\ref{eq1}) holds for $n=r$ with $m$ replaced by $m-\epsilon$ for suitably small $\epsilon > 0$. By induction, we have that (\ref{eq1}) holds for infinitely many $n$. For any such $n$ there exists $m>0$ such that for $i=1, \dots, n-1$, the points $(n-i, a_{n-i})$ and $(n+i, a_{n+i})$ lie below the line through $(n, a_n)$ of slope $m$. That means $a_{n+i} < a_n + mi$ and $a_{n-i} < a_n - mi$; adding these together gives $a_{n-i} + a_{n+i} < 2a_n$, as desired. \end{itemize} \end{document}