\documentclass[12pt]{article} \usepackage{amssymb, latexsym, amsmath, amsthm, epsf} \usepackage{epic, eepic} \pagestyle{plain} \setlength{\oddsidemargin}{-.3in} \setlength{\evensidemargin}{-.3in} \setlength{\textwidth}{6.75in} \setlength{\textheight}{8.5in} \setlength{\topmargin}{.2in} \setlength{\headheight}{0in} \setlength{\headsep}{0in} \setlength{\parskip}{20pt} \setlength{\labelsep}{10pt} \setlength{\parindent}{0pt} \setlength{\medskipamount}{1ex} \setlength{\smallskipamount}{1ex} \def\RR{{\mathbb R}} \def\ZZ{{\mathbb Z}} \newtheorem*{lemma}{Lemma} \newtheorem{fact}{Proposition} \newcommand\dg{\raisebox{.15pt}{$^{\circ}$}} \def\th{^{\mbox{\scriptsize th}}} \begin{document} \setlength{\baselineskip}{.25in} \begin{center} ${\bf 36th}$ \textbf{United States of America Mathematical Olympiad} \end{center} \begin{enumerate} \item %VAN1 Let $n$ be a positive integer. Define a sequence by setting $a_1=n$ and, for each $k >1$, letting $a_k$ be the unique integer in the range $0 \leq a_k \leq k-1$ for which $a_1+a_2+\dots+a_k$ is divisible by $k$. For instance, when $n=9$ the obtained sequence is $9,1,2,0,3,3,3,\dots$~. Prove that for any $n$ the sequence $a_1,a_2,a_3,\dots$ eventually becomes constant. \vspace{.1in} {\bf First Solution:} For $k \geq 1$, let \[ s_k=a_1+a_2+\dots+a_k . \] We have \[ \frac{s_{k+1}}{k+1} < \frac{s_{k+1}}{k} = \frac{s_k+a_{k+1}}{k} \leq \frac{s_k+k}{k} = \frac{s_k}{k}+1. \] On the other hand, for each $k$, $s_k/k$ is a positive integer. Therefore \[ \frac{s_{k+1}}{k+1} \leq \frac{s_k}{k}, \] and the sequence of quotients $s_k/k$ is eventually constant. If $s_{k+1}/(k+1) = s_k/k$, then \[ a_{k+1} = s_{k+1} - s_k = \frac{(k+1)s_k}{k} - s_k = \frac{s_k}{k}, \] showing that the sequence $a_k$ is eventually constant as well. \vspace{.1in} {\bf Second Solution:} For $k \geq 1$, let \[ s_k=a_1+a_2+\dots+a_k \qquad\text{and}\qquad \frac{s_k}{k}=q_k. \] Since $a_k \leq k-1$, for $k \geq 2$, we have \[ s_k = a_1+a_2+a_3+ \dots+a_k \leq n + 1 + 2 + \dots + (k-1) = n + \frac{k(k-1)}{2}. \] Let $m$ be a positive integer such that $n \leq \frac{m(m+1)}{2}$ (such an integer clearly exists). Then \[ q_m = \frac{s_m}{m} \leq \frac{n}{m} + \frac{m-1}{2} \leq \frac{m+1}{2} + \frac{m-1}{2} = m. \] We claim that \[ q_m = a_{m+1} = a_{m+2} = a_{m+3} = a_{m+4} = \dots~. \] This follows from the fact that the sequence $a_1,a_2,a_3,\dots$ is uniquely determined and choosing $a_{m+i} = q_m$, for $i \geq 1$, satisfies the range condition \[ 0 \leq a_{m+i} = q_m \leq m \leq m+i-1, \] and yields \[ s_{m+i} = s_m + iq_m = mq_m + iq_m = (m+i)q_m. \] \vspace{.1in} {\bf Third Solution:} For $k \geq 1$, let \[ s_k=a_1+a_2+\dots+a_k . \] We claim that for some $m$ we have $s_m = m(m-1)$. To this end, consider the sequence which computes the differences between $s_k$ and $k(k-1)$, i.e., whose $k$-th term is $s_k - k(k-1)$. Note that the first term of this sequence is positive (it is equal to $n$) and that its terms are strictly decreasing since \[ (s_k-k(k-1)) - (s_{k+1}-(k+1)k) = 2k - a_{k+1} \geq 2k-k = k \geq 1 . \] Further, a negative term cannot immediately follow a positive term. Suppose otherwise, namely that $s_k>k(k-1)$ and $s_{k+1} < (k+1)k$. Since $s_k$ and $s_{k+1}$ are divisible by $k$ and $k+1$, respectively, we can tighten the above inequalities to $s_k \geq k^2$ and $s_{k+1} \leq (k+1)(k-1) = k^2-1$. But this would imply that $s_k > s_{k+1}$, a contradiction. We conclude that the sequence of differences must eventually include a term equal to zero. Let $m$ be a positive integer such that $s_m = m(m-1)$. We claim that \[ m-1 = a_{m+1} = a_{m+2} = a_{m+3} = a_{m+4} = \dots~. \] This follows from the fact that the sequence $a_1,a_2,a_3,\dots$ is uniquely determined and choosing $a_{m+i} = m-1$, for $i \geq 1$, satisfies the range condition \[ 0 \leq a_{m+i} = m-1 \leq m+i-1, \] and yields \[ s_{m+i} = s_m + i(m-1) = m(m-1) + i(m-1) = (m+i)(m-1). \] \vspace{.1in} This problem was suggested by Sam Vandervelde. \item A square grid on the Euclidean plane consists of all points $(m,n)$, where $m$ and $n$ are integers. Is it possible to cover all grid points by an infinite family of discs with non-overlapping interiors if each disc in the family has radius at least 5? \vspace{.1in} {\bf Solution:} It is not possible. The proof is by contradiction. Suppose that such a covering family ${\cal F}$ exists. Let $D(P,\rho)$ denote the disc with center $P$ and radius $\rho$. Start with an arbitrary disc $D(O,r)$ that does not overlap any member of ${\cal F}$. Then $D(O,r)$ covers no grid point. Take the disc $D(O,r)$ to be maximal in the sense that any further enlargement would cause it to violate the non-overlap condition. Then $D(O,r)$ is tangent to at least three discs in ${\cal F}$. Observe that there must be two of the three tangent discs, say $D(A,a)$ and $D(B,b)$, such that $\angle AOB \le 120^{\circ}$. By the Law of Cosines applied to triangle $ABO$, \[ (a+b)^2 \le (a+r)^2 + (b+r)^2 + (a+r)(b+r), \] which yields \[ ab \le 3(a+b)r + 3r^2, \qquad \text{and thus} \qquad 12r^2 \ge (a-3r)(b-3r). \] Note that $r < 1/\sqrt{2}$ because $D(O,r)$ covers no grid point, and $(a-3r)(b-3r) \ge (5-3r)^2$ because each disc in ${\cal F}$ has radius at least 5. Hence $2 \sqrt{3} r \ge (5-3r)$, which gives $5 \le (3 + 2 \sqrt{3})r < (3 + 2 \sqrt{3})/\sqrt{2}$ and thus $5 \sqrt{2} < 3 + 2 \sqrt{3}$. Squaring both sides of this inequality yields $50 < 21 + 12 \sqrt{3} < 21 + 12 \cdot 2 = 45$. This contradiction completes the proof. \vspace{.1in} {\bf Remark:} The above argument shows that no covering family exists where each disc has radius greater than $(3+2\sqrt{3})/\sqrt{2} \approx 4.571$. In the other direction, there exists a covering family in which each disc has radius $\sqrt{13}/2 \approx 1.802$. Take discs with this radius centered at points of the form $(2m+4n + \frac{1}{2}, 3m + \frac{1}{2})$, where $m$ and $n$ are integers. Then any grid point is within $\sqrt{13}/2$ of one of the centers and the distance between any two centers is at least $\sqrt{13}$. The extremal radius of a covering family is unknown. \vspace{.1in} This problem was suggested by Gregory Galperin. \item %ROU1 Let $S$ be a set containing $n^2 + n - 1$ elements, for some positive integer $n$. Suppose that the $n$-element subsets of $S$ are partitioned into two classes. Prove that there are at least $n$ pairwise disjoint sets in the same class. \vspace{.1in} {\bf Solution:} In order to apply induction, we generalize the result to be proved so that it reads as follows: \vspace{.1in} \noindent {\bf Proposition.} If the $n$-element subsets of a set $S$ with $(n+1)m-1$ elements are partitioned into two classes, then there are at least $m$ pairwise disjoint sets in the same class. \begin{proof} Fix $n$ and proceed by induction on $m$. The case of $m=1$ is trivial. Assume $m>1$ and that the proposition is true for $m-1$. Let ${\mathcal P}$ be the partition of the $n$-element subsets into two classes. If all the $n$-element subsets belong to the same class, the result is obvious. Otherwise select two $n$-element subsets $A$ and $B$ from different classes so that their intersection has maximal size. It is easy to see that $\vert A\cap B\vert = n-1$. (If $\vert A\cap B\vert = k < n-1$, then build $C$ from $B$ by replacing some element not in $A\cap B$ with an element of $A$ not already in $B$. Then $\vert A\cap C\vert = k+1$ and $\vert B\cap C\vert=n-1$ and either $A$ and $C$ or $B$ and $C$ are in different classes.) Removing $A\cup B$ from $S$, there are $(n+1)(m-1)-1$ elements left. On this set the partition induced by $\mathcal P$ has, by the inductive hypothesis, $m-1$ pairwise disjoint sets in the same class. Adding either $A$ or $B$ as appropriate gives $m$ pairwise disjoint sets in the same class. \end{proof} \vspace{.1in} {\bf Remark:} The value $n^2+n-1$ is sharp. A set $S$ with $n^2+n-2$ elements can be split into a set $A$ with $n^2-1$ elements and a set $B$ of $n-1$ elements. Let one class consist of all $n$-element subsets of $A$ and the other consist of all $n$-element subsets that intersect $B$. Then neither class contains $n$ pairwise disjoint sets. \vspace{.1in} \noindent This problem was suggested by Andr\'{a}s Gy\'{a}rf\'{a}s. \item %BAR1 An {\em animal} with $n$ {\em cells} is a connected figure consisting of $n$ equal-sized square cells.\footnote {Animals are also called {\em polyominoes}. They can be defined inductively. Two cells are {\em adjacent} if they share a complete edge. A single cell is an animal, and given an animal with $n$-cells, one with $n+1$ cells is obtained by adjoining a new cell by making it adjacent to one or more existing cells.} The figure below shows an 8-cell animal. \setlength{\unitlength}{.5pt} \begin{center} \begin{picture}(400,150)(-50,-20) \path(50,0)(250,0)(250,50)(0,50)(0,100)(50,100) \path(50,0)(50,100)(200,100)(200,0) \path(100,0)(100,100) \path(150,0)(150,100) \end{picture} \end{center} A {\em dinosaur} is an animal with at least 2007 cells. It is said to be {\em primitive} if its cells cannot be partitioned into two or more dinosaurs. Find with proof the maximum number of cells in a primitive dinosaur. \vspace{.1in} {\bf Solution:} Let $s$ denote the minimum number of cells in a dinosaur; the number this year is $s = 2007$. {\bf Claim:} The maximum number of cells in a primitive dinosaur is $4(s-1)+1$. First, a primitive dinosaur can contain up to $4(s-1)+1$ cells. To see this, consider a dinosaur in the form of a cross consisting of a central cell and four arms with $s-1$ cells apiece. No connected figure with at least $s$ cells can be removed without disconnecting the dinosaur. The proof that no dinosaur with at least $4(s-1)+2$ cells is primitive relies on the following result. \begin{lemma} Let $D$ be a dinosaur having at least $4(s-1)+2$ cells, and let $R$ (red) and $B$ (black) be two complementary animals in $D$, i.e., $R \cap B = \varnothing$ and $R \cup B = D$. Suppose $|R| \le s-1$. Then $R$ can be augmented to produce animals $\tilde{R} \supset R$ and $\tilde{B} = D \setminus \tilde{R}$ such that at least one of the following holds: \begin{enumerate} \item[(i)] $|\tilde{R}| \ge s$ and $|\tilde{B}| \ge s$, \item[(ii)] $|\tilde{R}| = |R| + 1$, \item[(iii)] $|R| < |\tilde{R}| \le s-1$. \end{enumerate} \end{lemma} \begin{proof} If there is a black cell adjacent to $R$ that can be made red without disconnecting $B$, then (ii) holds. Otherwise, there is a black cell $c$ adjacent to $R$ whose removal disconnects $B$. Of the squares adjacent to $c$, at least one is red, and at least one is black, otherwise $B$ would be disconnected. Then there are at most three resulting components ${\cal C}_1, {\cal C}_2, {\cal C}_3$ of $B$ after the removal of $c$. Without loss of generality, ${\cal C}_3$ is the largest of the remaining components. (Note that ${\cal C}_1$ or ${\cal C}_2$ may be empty.) Now ${\cal C}_3$ has at least $\lceil(3s-2)/3\rceil = s$ cells. Let $\tilde{B} = {\cal C}_3$. Then $|\tilde{R}| = |R| + |{\cal C}_1| + |{\cal C}_2| + 1$. If $|\tilde{B}| \le 3s-2$, then $|\tilde{R}| \ge s$ and (i) holds. If $|\tilde{B}| \ge 3s-1$ then either (ii) or (iii) holds, depending on whether $|\tilde{R}| \ge s$ or not. \end{proof} Starting with $|R|=1$, repeatedly apply the Lemma. Because in alternatives (ii) and (iii) $|R|$ increases but remains less than $s$, alternative (i) eventually must occur. This shows that no dinosaur with at least $4(s-1)+2$ cells is primitive. \vspace{.1in} This problem was suggested by Reid Barton. \item %AND2 Prove that for every nonnegative integer $n$, the number $7^{7^n} + 1$ is the product of at least $2n+3$ (not necessarily distinct) primes. \vspace{.1in} {\bf Solution:} The proof is by induction. The base is provided by the $n=0$ case, where $7^{7^0} + 1 = 7^1 + 1 = 2^3$. To prove the inductive step, it suffices to show that if $x = 7^{2m-1}$ for some positive integer $m$ then $(x^7 + 1)/(x+1)$ is composite. As a consequence, $x^7 + 1$ has at least two more prime factors than does $x+1$. To confirm that $(x^7 + 1)/(x+1)$ is composite, observe that \begin{align*} \frac{x^7 + 1}{x+1} & = \frac{(x+1)^7 - ((x+1)^7 - (x^7 + 1))}{x+1} \\[.1in] & = (x+1)^6 - \frac{7x(x^5 + 3x^4 + 5x^3 + 5x^2 + 3x + 1)}{x+1} \\[.1in] & = (x+1)^6 - 7x(x^4 + 2x^3 + 3x^2 + 2x + 1) \\[.1in] & = (x+1)^6 - 7^{2m}(x^2 + x + 1)^2 \\[.1in] & = \{(x+1)^3 - 7^m(x^2 + x + 1)\}\{(x+1)^3 + 7^m(x^2 + x + 1)\} \end{align*} Also each factor exceeds 1. It suffices to check the smaller one; $\sqrt{7x} \le x$ gives \begin{align*} (x+1)^3 - 7^m(x^2 + x + 1) & = (x+1)^3 - \sqrt{7x} (x^2 + x + 1) \\[.1in] & \ge x^3 + 3x^2 + 3x + 1 - x(x^2 + x + 1) \\[.1in] & = 2x^2 + 2x + 1 \ge 113 > 1. \end{align*} Hence $(x^7 + 1)/(x+1)$ is composite and the proof is complete. \vspace{.1in} This problem was suggested by Titu Andreescu. \item %KED3 \noindent Let $ABC$ be an acute triangle with $\omega, \Omega,$ and $R$ being its incircle, circumcircle, and circumradius, respectively. Circle $\omega_A$ is tangent internally to $\Omega$ at $A$ and tangent externally to $\omega$. Circle $\Omega_A$ is tangent internally to $\Omega$ at $A$ and tangent internally to $\omega$. Let $P_A$ and $Q_A$ denote the centers of $\omega_A$ and $\Omega_A$, respectively. Define points $P_B, Q_B, P_C, Q_C$ analogously. Prove that \[ 8P_AQ_A \cdot P_BQ_B \cdot P_C Q_C \leq R^3, \] with equality if and only if triangle $ABC$ is equilateral. \vspace*{.1in} {\bf Solution:} Let the incircle touch the sides $AB, BC$, and $CA$ at $C_1, A_1$, and $B_1$, respectively. Set $AB = c$, $BC = a$, $CA = b$. By equal tangents, we may assume that $AB_1 = AC_1 = x$, $BC_1 = BA_1 = y$, and $CA_1 = CB_1 = z$. Then $a = y + z$, $b = z + x$, $c = x + y$. By the AM-GM inequality, we have $a \ge 2\sqrt{yz}$, $b \ge 2\sqrt{zx}$, and $c \ge 2\sqrt{xy}$. Multiplying the last three inequalities yields \[ abc \ge 8xyz, \eqno{(\dag)}, \] with equality if and only if $x = y = z$; that is, triangle $ABC$ is equilateral. \vspace*{.1in} Let $k$ denote the area of triangle $ABC$. By the Extended Law of Sines, $c = 2R\sin\angle C$. Hence \[ k = \frac{ab\sin\angle C}{2} = \frac{abc}{4R} \quad \mbox{or}\quad R = \frac{abc}{4k}. \eqno{(\ddag)} \] We are going to show that \[ P_AQ_A = \frac{xa^2}{4k}. \eqno{(*)} \] In exactly the same way, we can also establish its cyclic analogous forms \[ P_BQ_B = \frac{yb^2}{4k} \quad \mbox{and} \quad P_CQ_C = \frac{zc^2}{4k}. \] Multiplying the last three equations together gives \[ P_AQ_A\cdot P_BQ_B\cdot P_CQ_C = \frac{xyza^2b^2c^2}{64k^3}. \] Further considering $(\dag)$ and $(\ddag)$, we have \[ 8P_AQ_A\cdot P_BQ_B\cdot P_CQC = \frac{8xyza^2b^2c^2}{64k^3} \le \frac{a^3b^3c^3}{64k^3} = R^3, \] with equality if and only if triangle $ABC$ is equilateral. \vspace*{.1in} Hence it suffices to show $(*)$. Let $r, r_A, r_A'$ denote the radii of $\omega, \omega_A, \Omega_A$, respectively. We consider the inversion $\mathbf{I}$ with center $A$ and radius $x$. Clearly, $\mathbf{I} (B_1) = B_1$, $\mathbf{I} (C_1) = C_1$, and $\mathbf{I} (\omega) = \omega$. Let ray $AO$ intersect $\omega_A$ and $\Omega_A$ at $S$ and $T$, respectively. It is not difficult to see that $AT > AS$, because $\omega$ is tangent to $\omega_A$ and $\Omega_A$ externally and internally, respectively. Set $S_1 = \mathbf{I} (S)$ and $T_1 = \mathbf{I} (T)$. Let $\ell$ denote the line tangent to $\Omega$ at $A$. Then the image of $\omega_A$ (under the inversion) is the line (denoted by $\ell_1$) passing through $S_1$ and parallel to $\ell$, and the image of $\Omega_A$ is the line (denoted by $\ell_2$) passing through $T_1$ and parallel to $\ell$. Furthermore, since $\omega$ is tangent to both $\omega_A$ and $\Omega_A$, $\ell_1$ and $\ell_2$ are also tangent to the image of $\omega$, which is $\omega$ itself. Thus the distance between these two lines is $2r$; that is, $S_1T_1 = 2r$. Hence we can consider the following configuration. (The darkened circle is $\omega_A$, and its image is the darkened line $\ell_1$.) \begin{center} \epsfbox{kiran072.eps} % \\ %{\footnotesize Figure 1.57.} \end{center} By the definition of inversion, we have $AS_1\cdot AS = AT_1\cdot AT = x^2$. Note that $AS = 2r_A$, $AT = 2r_A'$, and $S_1T_1 = 2r$. We have \[ r_A = \frac{x^2}{2AS_1}. \quad \mbox{and}\quad r_A' = \frac{x^2}{2AT_1} = \frac{x^2}{2(AS_1-2r)}. \] Hence \[ P_AQ_A = AQ_A - AP_A = r_A' - r_A = \frac{x^2}{2}\left( \frac{1}{AS_1-2r} + \frac{1}{AS_1} \right). \] Let $H_A$ be the foot of the perpendicular from $A$ to side $BC$. It is well known that $\angle BAS_1 = \angle BAO = 90\dg - \angle C = \angle CAH_A$. Since ray $AI$ bisects $\angle BAC$, it follows that rays $AS_1$ and $AH_A$ are symmetric with respect to ray $AI$. Further note that both line $\ell_1$ (passing through $S_1$) and line $BC$ (passing through $H_A$) are tangent to $\omega$. We conclude that $AS_1 = AH_A$. In light of this observation and using the fact $2k = AH_A\cdot BC = (AB + BC + CA)r$, we can compute $P_AQ_A$ as follows: \begin{align*} P_AQ_A & = \frac{x^2}{2}\left(\frac{1}{AH_A-2r} - \frac{1}{AH_A}\right) = \frac{x^2}{4k}\left(\frac{2k}{AH_A-2r} - \frac{2k}{AH_A}\right) \\[.1in] & = \frac{x^2}{4k} \left(\frac{1}{\frac{1}{BC}-\frac{2}{AB+BC+CA}} - BC \right) = \frac{x^2}{4k} \left( \frac{1}{\frac{1}{y+z}-\frac{1}{x+y+z}} - (y+z) \right) \\[.1in] & = \frac{x^2}{4k} \left( \frac{(y+z)(x+y+z)}{x} - (y+z) \right) \\[.1in] & = \frac{x(y+z)^2}{4k} = \frac{xa^2}{4k}, \end{align*} establishing $(*)$. Our proof is complete. \vspace{.1in} {\bf Note:} Trigonometric solutions of $(*)$ are also possible. \\ {\bf Query:} For a given triangle, how can one construct $\omega_A$ and $\Omega_A$ by ruler and compass? \vspace{.1in} This problem was suggested by Kiran Kedlaya and Sungyoon Kim. \end{enumerate} \vfill {\small \begin{center} Copyright \copyright\ \ Committee on the American Mathematics Competitions,\\ Mathematical Association of America \end{center} } \end{document}