% Last modified 7 Dec 1997 % Process using LaTeX2e \documentclass[12pt]{article} \usepackage{latexsym} \setlength{\textheight}{8.75in} \setlength{\textwidth}{6.5in} \setlength{\topmargin}{0.0in} \setlength{\headheight}{0.0in} \setlength{\headsep}{0.0in} \setlength{\leftmargin}{0.0in} \setlength{\oddsidemargin}{0.0in} \setlength{\parindent}{1pc} \def\binom#1#2{{#1 \choose #2}} \def\mymod#1{\,\,({\rm mod}\, #1)} \begin{document} \begin{center} {\bf Solutions to the Fifty-Ninth William Lowell Putnam Mathematical Competition} \\ \vskip 0.25cm Saturday, December 5, 1998\\ \vskip 0.25cm Prepared by Mark Hovey \end{center} \vskip .2cm \begin{itemize} \item[A--1] Let $s$ denote the side length of the cube. At height $s$ above the base of the cone, the radius of the cone is $(1/3)(3-s)=1-(1/3)s$, by simmilar triangles. The top of the cube, a square of side $s$, must be inscribed in this circle. Therefore, $\sqrt{2}(1-(1/3)s)=s$, because the side length of a square inscribed in a circle is $\sqrt{2}$ times the radius. Solving for $s$ gives \[ s = \frac{3\sqrt{2}}{3+\sqrt{2}}. \] \item[A--2] Suppose $s$ is the arc from $\theta =\theta _{1}$ to $\theta =\theta _{2}$. Then \[ A= \int_{x=\cos \theta _{2}}^{\cos \theta _{1}} \sqrt{1-x^{2}} \, dx. \] The change of variables $x=\cos \alpha $ leads to \[ A = \int_{\alpha =\theta _{2}}^{\theta _{1}} -\sin ^{2}\alpha \, d\alpha = \int_{\theta _{1}}^{\theta _{2}} \sin ^{2} \alpha \, d\alpha . \] Similarly, \[ B = \int_{y=\sin \theta _{1}}^{\theta _{2}} \sqrt{1-y^{2}}\, dy = \int_{\alpha =\theta _{1}}^{\theta _{2}} \cos ^{2}\alpha \, d\alpha . \] Adding gives \[ A+B= \int_{\theta _{1}}^{\theta _{2}} d\alpha = \theta _{2}-\theta _{1} \] which is the arclength of $s$. \item[A--3] We first prove a little lemma. \textbf{Lemma:} Suppose $f$ is a function on the real line with $f''$ continuous. Suppose that $f(x)>0$ for all $x$ and $f'(x)<0$ for all $x$. Then there must be an $a$ such that $f''(a)\geq 0$. To prove this lemma, compare the function $f$ to its tangent line $g(x)=f(0)+f'(0)x$ at the origin. Then $f(0)=g(0)$, and, if $f''(x)<0$ for all $x$, then $g'(x)>f'(x)$ for all positive $x$. This implies, by the standard calculus tricks like Rolle's theorem, that $g(x)\geq f(x)$ for all positive $x$. But obviously there is an $a>0$ such that $g(a)=0$, so there is an $a>0$ such that $f(a)\leq 0$. This is a contradiction. \textbf{Corollary:} Suppose $f$ is a function on the real line with $f''$ continuous, $f(x)>0$ for all $x$, and $f'(x)>0$ for all $x$. Then there is an $a$ such that $f''(a)\geq 0$. To prove the corollary, replace $f(x)$ by $g(x)=f(-x)$ to reduce to the lemma. Now suppose we have a function $f$ as in the statement of the problem. If any of $f$, $f'$, $f''$, or $f'''$ is ever $0$, then we are done. If not, then each of $f$, $f'$, $f''$, and $f'''$ must be either always positive or always negative, by the intermediate value theorem. By replacing $f$ by $-f$, we can assume $f>0$. By replacing $f(x)$ by $f(-x)$, we can assume $f'>0$. Then we are in the situation of the corollary, so we conclude that $f''(a)\geq 0$ for some $a$, so $f''(x)>0$ for all $x$. Then we are in the situation of the corollary again for $f'$, so we conclude that $f'''(x)>0$ for all $x$. Thus the product $f(a)f'(a)f''(a)f'''(a)>0$ for all $a$, as required. (Note that this stronger conclusion only holds when none of them are ever $0$). \item[A--4] Note that the number of decimal digits in $A_{n}$ is the $n$th Fibonacci number $F(n)$. Indeed, it is obvious that the number of digits obeys the Fibonacci recurrence, and the first few terms are as required. Therefore we have \[ A_{n} = 10^{F(n-2)}A_{n-1} + A_{n-2} \equiv (-1)^{F(n-2)} A_{n-1} + A_{n-2} \pmod{11}. \] It is well-known, and easy to check, that $F(n)$ is even if and only if $n$ is divisible by $3$. This enables us to construct a table of the first few values of $A_{n} \pmod{11}$, which goes like this: \[ A_{1}\equiv 0, A_{2}\equiv 1, A_{3}\equiv -1, A_{4}\equiv 2, A_{5}\equiv 1, A_{6}\equiv 1, A_{7}\equiv 0, A_{8}\equiv 1. \] Since $7 \equiv 1 \pmod{3}$ and $8 \equiv 2 \pmod{3}$, this pattern will repeat endlessly, and so $A_{n}$ is divisible by $11$ if and only if $n\equiv 1 \pmod{6}$. \item[A--5] We proceed by induction on $n$. The main point is the following lemma. \textbf{Lemma:} Suppose we have two disks $D_{1}$ and $D_{2}$ with radii $r_{1}$ and $r_{2}$, respectively. If $r_{1}\geq r_{2}$ and $D_{1}\cap D_{2}$ is nonempty, then $3D_{1}\supseteq D_{1}\cup D_{2}$. The proof of this lemma uses the triangle inequality. Suppose the center of $D_{1}$ is $p$ and the radius is $r$, the center of $D_{2}$ is $q$, and $x$ is a point in both $D_{1}$ and $D_{2}$. Then if $y$ is any point in $D_{2}$, we have \[ d(p,y) \leq d(p,x) + d(x,q) + d(q,y) < 3r. \] Here $d$ is the usual distance function. This lemma handles the case $n=2$ without difficulty. Now suppose we know the theorem for $n-1$. Given $n$ disks $D_{1},D_{2},\dots ,D_{n}$, with radii $r_{1},\dots ,r_{n}$, rearrange them so that $r_{1}\geq r_{j}$ for all $j$. Rearrange them further so that $D_{1}\cap D_{i}\neq \emptyset $ for all $i< j$, and $D_{1}\cap D_{i}=\emptyset $ for all $i\geq j$. Here $j$ can be anything from $1$ to $n+1$. By induction, there is a disjoint subcollection $D_{i_{1}},\dots ,D_{i_{k}}$ of $D_{j},\dots ,D_{n}$ so that \[ \bigcup_{m=1}^{k} 3D_{m} = \bigcup _{m=j}^{n} D_{m}. \] By repeated application of the lemma, \[ 3D_{1}\supseteq \bigcup _{m=1}^{j-1} D_{m}, \] so the subcollection $D_{1}, D_{i_{1}},\dots ,D_{i_{k}}$ give us the desired disjoint subfamily. This proves the induction step, and so the theorem is true for all $n$. Notice that this argument will work in any metric space. \item[A--6] (From Kirin Kedlaya at MIT) We are given that $|AB|^{2}+|BC|^{2}+2|AB||BC| < 8[ABC] + 1$. We also know that $|AB||BC|\geq 2[ABC]$, and $|AB|^{2}+|BC|^{2}\geq 2|AB||BC| \geq 4[ABC]$. Therefore we have \[ 8[ABC] \leq |AB|^{2} + |BC|^{2} + 4[ABC] \leq |AB|^{2} + |BC|^{2} + 2|AB| |BC| < 8[ABC] + 1. \] It is easy to see, using for example the cross product or Pick's theorem, that $2[ABC]$ is an integer. It follows that $8[ABC] = |AB|^{2}+|BC|^{2} + 4[ABC]$, and so \[ |AB|^{2}+|BC|^{2} = 2 |AB| |BC| = 4[ABC]. \] This means that $B$ is a right angle and $|AB|=|BC|$, as required. \item[B--1] The function in question is just $3(x+1/x)$, as some calculation will show, The minimum is therefore $6$ at $x=1$. \item[B--2] (Solution by Richard McKenzie) Let $P$ denote the point $(a,b)$, $Q$ the point on the line $y=x$, and $R$ the point on the $x$-axis. By reflecting in the line $y=x$, we find that the side $PQ$ has the same length as the line segment from $Q$ to $(b,a)$. By reflecting in the $x$-axis, we find that the side $PR$ has the same length as the line segment from $R$ to $(a,-b)$. So the perimeter of the triangle is the length of the path from $(b,a)$ to $(a,-b)$ that passes through $Q$ and $R$. Obviously this path will be shortest when it is a straight line, in which case the minimum perimeter is just the distance from $(b,a)$ to $(a,-b)$. This distance is $\sqrt{2a^{2}+2b^{2}}$. Solution 2: More prosaically, we can apply multivariable calculus. Let $(c,c)$ be the point on the line $y=x$, and $(d,0)$ the point on the $x$-axis. Then the perimeter is given by \[ P(c,d) = \sqrt{(a-c)^{2}+(b-c)^{2}} + \sqrt{(a-d)^{2}+b^{2}} + \sqrt{(c-d)^{2}+c^{2}}. \] At the minimum triangle, the gradient of $P$ must be trivial. The relationship $\partial P/\partial d=0$ gives, after some simplification, \[ (a-d)^{2}c^{2} = (c-d)^{2}b^{2}. \] This gives either \[ (a-d)c = (c-d)b \mbox{ or } (a-d)c = (d-c)b. \] In the first case, geometric arguments show that $a=c=d$ at the mimimum, where the perimeter is $2a$. Indeed, if $a\geq d$ and $c\geq d$, then we might as well slide $d$ directly beneath $c$, in which case $c-d=0$, so $a-d=0$. A similar argument shows that if $a\leq d$ and $c\leq d$, then $a=c=d$. We are then left with the second case. In this case, a whole lot of complicated algebra using $\partial P/\partial c = 0$ shows that \[ c=\frac{a^{2}+b^{2}}{2a} \mbox{ and } d=\frac{a^{2}+b^{2}}{a+b}. \] In this case, more complicated algebra shows that \[ P= \sqrt{2a^{2}+2b^{2}}. \] This is less than $2a$ and so is the minimum perimeter. \item[B--3] (From Kirin Kedlaya at MIT) The surface area is obviously $2\pi -5A$, where $A$ is the surface area outside one face of the pentagon. We can arrange the pentagon so that one face goes from $\theta =-\pi /5$ to $\theta =\pi /5$. Then if we imagine the point $(1,0,0)$ is actually the north pole of the unit sphere, $A$ is half of the area of the spherical cap where $z\geq \cos \pi /5$. This surface area is easily calculated using the standard surface area techniques--if we parametrize the sphere by $f(r,\theta )= (r \cos \theta ,r\sin \theta , \sqrt{1-r^{2}})$, then $|(\partial f/\partial r)\times (\partial f/\partial \theta )|=r/\sqrt{1-r^{2}}$. We must integrate this over the disk with $r\leq \sin \pi /5$. The answer comes out to be $(2\pi )(1-\cos \pi /5)$. Since $A$ is half this, the surface area we want is \[ 2\pi - 5\pi (1-\cos \pi /5) = 5\pi \cos \pi /5 - 3\pi . \] \item[B--4] Let $f(m,n)$ denote the sum in question. \textbf{Lemma:} $f(2m,2n)=2(1+(-1)^{m+n})f(m,n)$. To prove this lemma, note that $\lfloor 2i/2m \rfloor = \lfloor (2i+1)/2m \rfloor = \lfloor i/m \rfloor$, and similarly for $n$. It follows that \[ f(2m,2n) = 2 (f(m,n) + \sum _{i=mn}^{2mn-1} (-1)^{\lfloor i/m \rfloor + \lfloor i/n \rfloor}) . \] Since $\lfloor (i+mn)/m \rfloor = \lfloor i/m + n$, and similarly for $n$, this second sum is $(-1)^{m+n}f(m,n)$. The lemma follows. Now suppose $m=2^{r}m'$ and $n=2^{s}n'$ where $m'$ and $n'$ are odd. Without loss of generality we can assume that $r\geq s$. Repeated application of the lemma shows that \[ f(m,n) = 2^{2(s-1)}f(2^{r-s+1}m',2n') = 2^{2s-1}(1+(-1)^{2^{r-s}m'+n'})f(m',n'). \] Therefore, if $r>s$, $f(m,n)=0$, but if $r=s$, $f(m,n)=2^{2s}f(m',n')$. Since $m'$ and $n'$ are both odd, there are an odd number of terms in the sum defining $f(m',n')$. Since each term is $\pm 1$, the sum can't be $0$. The final answer is then $f(m,n)=0$ if and only if the power of $2$ occuring in the prime factorization of $m$ is different than the power of $2$ appearing in the prime factorization of $n$. \item[B--5] (This argument is due to Jim Lipton). The number $N$ is the sum of a geometric series, so it is $(10^{1998}-1)/9$. So its square root is $\sqrt{10^{1998}-1}/3$. We approximate this square root using the first few terms of the Taylor series. We find \[ \sqrt{10^{1998}-1} = 10^{999} - 1/2(10^{999}) - 1/8(10^{2997}) + \varepsilon \] where $\varepsilon $ is on the order of the third derivative of $\sqrt{x}$ applied to $10^{1998}$, which is much smaller than $10^{-1000}$. To find the thousandth digit after the decimal place, we multiply by $10^{1000}$, take the integer part, and take the remainder mod 10. We get \[ 10^{1000}\sqrt{N} = 10^{1999}/3 -5/3 - 1/24(10^{1997}) + \varepsilon ' \] where $\varepsilon '$ is still too small to matter. The decimal expansion of the first term is infinitely many 3's, starting way past where we care about. Subtracting $5/3$ will give us a $1$ in the units place, so the desired decimal digit is $1$. \item[B--6] Suppose $\sqrt{n^{3}+an^{2}+bn+c}$ is always an integer. Let us first suppose $c$ is even. Then $c \equiv 0 \pmod{4}$, as one can say by taking $n \equiv 0 \pmod{4}$. By taking $n\equiv 2 \pmod{4}$, we find that $2b$ is a perfect square mod 4, so $b$ is even. Then by taking $n \equiv 1 \pmod{4}$ and $n \equiv 3 \pmod{4}$, we see that both $1+a+b$ and $-1+a-b$ are perfect squares. If either $b\equiv 0 \pmod{4}$ or $b \equiv 2 \pmod{4}$, this means both $a+1$ and $a-1$ are perfect squares mod 4. This is impossible. Therefore $c$ must be odd. This implies that $c \equiv 1 \pmod{8}$. By taking $n \equiv 4 \pmod{8}$, we find that $4b+1$ is a perfect square mod $8$, so $b$ must be even. By taking $n \equiv 2 \pmod{8}$, we find that $4a+2b+1$ is a perfect square mod 8. For the moment, let us assume that $a$ is odd. Then $b \equiv 2 \pmod{4}$. By taking $n\equiv 1 \pmod{4}$ and $n \equiv -1 \pmod{4}$, we find that both $a$ and $a+2$ are perfect squares mod 4. This is a contradiction, and so $a$ must be even. So now we know that $c\equiv 1 \pmod{8}$, and that $a$ and $b$ are both even. Taking $n \equiv 2 \pmod{8}$, we find that $2b+1$ is a square mod 8, so $b\equiv 0 \pmod{4}$. By taking $n\equiv 1 \pmod{4}$ and $n \equiv -1 \pmod{4}$, we find that both $a$ and $a+2$ are perfect squares mod $4$. This is again a contradiction, and we conclude that there must be some $n$ (between $1$ and $8$, in fact) such that $n^{3}+an^{2}+bn+c$ is not a perfect square. \end{itemize} \end{document}