\documentclass[12pt]{article} \usepackage{amssymb, latexsym, amsmath, amsthm} \usepackage{epic, eepic} \pagestyle{empty} \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}{3ex} \setlength{\smallskipamount}{1ex} \def\RR{{\Bbb R}} \newtheorem{fact}{Proposition} \newcommand\dg{\raisebox{.15pt}{$^{\circ}$}} \def\th{^{\mbox{\scriptsize th}}} \begin{document} \setlength{\baselineskip}{.25in} \begin{center} ${\bf 34\th}$ \textbf{United States of America Mathematical Olympiad} \end{center} \begin{enumerate} \item Determine all composite positive integers $n$ for which it is possible to arrange all divisors of $n$ that are greater than 1 in a circle so that no two adjacent divisors are relatively prime. {\bf Solution.} No such circular arrangement exists for $n = pq$, where $p$ and $q$ are distinct primes. In that case, the numbers to be arranged are $p, q$ and $pq$, and in any circular arrangement, $p$ and $q$ will be adjacent. We claim that the desired circular arrangement exists in all other cases. If $n = p^e$ where $e \ge 2$, an arbitrary circular arrangement works. Henceforth we assume that $n$ has prime factorization $p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$, where $p_1 < p_2 < \cdots < p_k$ and either $k > 2$ or else $\max(e_1, e_2) > 1$. To construct the desired circular arrangement of $D_n := \{d: \; d|n \; \text{and} \; d > 1\}$, start with the circular arrangement of $n, \, p_1p_2, \, p_2p_3, \, \ldots, \, p_{k-1}p_k$ as shown. \setlength{\unitlength}{.4pt} \begin{center} \begin{picture}(600,175)(-300,-70) \thinlines \put(0,0){\ellipse{500}{150}} \put(0,75){\circle*{15}} \put(-8,95){$n$} \put(100,68.738635){\circle*{15}} \put(85,90){$p_1 p_2$} \put(200,45){\circle*{15}} \put(182,65){$p_2 p_3$} \put(-100,68.738635){\circle*{15}} \put(-140,90){$p_{k-1}p_k$} \put(-205,42.92726){\circle*{8}} \put(-185,50.445515){\circle*{8}} \put(-225,32.69174){\circle*{8}} \end{picture} \end{center} Then between $n$ and $p_1p_2$, place (in arbitrary order) all other members of $D_n$ that have $p_1$ as their smallest prime factor. Between $p_1p_2$ and $p_2p_3$, place all members of $D_n$ other than $p_2 p_3$ that have $p_2$ as their smallest prime factor. Continue in this way, ending by placing $p_k, p_k^2, \ldots, p_k^{e_k}$ between $p_{k-1}p_k$ and $n$. It is easy to see that each element of $D_n$ is placed exactly one time, and any two adjacent elements have a common prime factor. Hence this arrangement has the desired property. {\em Note.} In graph theory terms, this construction yields a Hamiltonian cycle\footnote{A {\em cycle} of length $k$ in a graph is a sequence of distinct vertices $v_1, v_2, \ldots, v_k$ such that $\{v_1,v_2\}, \{v_2, v_3\}, \ldots \{v_{k-1},v_k\},\{v_k, v_1\}$ are edges. A cycle that uses every vertex of the graph is a {\em Hamiltonian cycle}.} in the graph with vertex set $D_n$ in which two vertices form an edge if the two corresponding numbers have a common prime factor. The graphs below illustrate the construction for the special cases $n = p^2q$ and $n=pqr$. \setlength{\unitlength}{.3pt} \begin{center} \begin{picture}(250,350)(-125,-200) \thinlines \put(0,200){\circle*{20}} \put(0,0){\circle*{20}} \put(86.5,50){\circle*{20}} \put(-86.5,50){\circle*{20}} \put(0,-100){\circle*{20}} \put(-5,235){$q$} \path(0,200)(86.5,50)(0,0)(-86.5,50)(0,200) \path(-86.5,50)(86.5,50)(0,-100)(-86.5,50)(0,0)(86.5,50) \path(0,0)(0,-100) \put(-15,-150){$p^2$} \put(-150,45){$pq$} \put(115,45){$n$} \put(-5,25){$p$} \Thicklines \path(86.5,50)(0,0)(0,-100)(-86.5,50)(0,200)(86.5,50) \put(-60,-200){$n=p^2q$} \end{picture} \hspace*{1in} \begin{picture}(250,350)(-125,-200) \thinlines \path(-173,-100)(173,-100)(0,200)(-173,-100) \path(0,-100)(0,200) \path(-173,-100)(86.5,50) \path(173,-100)(-86.5,50) \path(0,-100)(86.5,50)(-86.5,50)(0,-100) \put(173,-100){\circle*{20}}\put(-173,-100){\circle*{20}} \put(0,200){\circle*{20}} \put(0,0){\circle*{20}} \put(86.5,50){\circle*{20}} \put(-86.5,50){\circle*{20}} \put(0,-100){\circle*{20}} \put(-5,235){$p$} \put(115,45){$pq$} \put(200,-120){$q$} \put(-15,-145){$qr$} \put(-215,-120){$r$} \put(-145,45){$rp$} \put(8,18){$n$} \Thicklines \path(0,0)(-86.5,50)(0,200)(86.5,50)(173,-100)(0,-100)(-173,-100)(0,0) \put(-60,-200){$n=pqr$} \end{picture} \end{center} This problem was proposed by Zuming Feng. \item Prove that the system \begin{align*} x^6+x^3+x^3y+y & = 147^{157} \\[.1in] x^3+x^3y+y^2+y+z^9 & = 157^{147} \end{align*} has no solutions in integers $x$, $y$, and $z$. {\bf First Solution.} Add the two equations, then add 1 to each side to obtain \begin{equation} (x^3+y+1)^2+z^9=147^{157}+157^{147}+1. \end{equation} We prove that the two sides of this expression cannot be congruent modulo 19. We choose 19 because the least common multiple of the exponents 2 and 9 is 18, and by Fermat's Theorem, $a^{18}\equiv1\pmod{19}$ when $a$ is not a multiple of 19. In particular, $(z^9)^2\equiv 0$ or $1\pmod{19}$, and it follows that the possible remainders when $z^9$ is divided by 19 are \begin{equation} -1,\,0,\,1. \end{equation} Next calculate $n^2$ modulo 19 for $n=0,\,1,\dots,9$ to see that the possible residues modulo 19 are $$-8,\,-3,\,-2,\,0,\,1,\,4,\,5,\,6,\,7,\,9.\eqno{(3)}$$ Finally, apply Fermat's Theorem to see that $$147^{157}+157^{147}+1\equiv 14\pmod{19}.$$ Because we cannot obtain 14 (or $-5$) by adding a number from list (2) to a number from list (3), it follows that the left side of (1) cannot be congruent to 14 modulo 19. Thus the system has no solution in integers $x,\,y,\,z$. {\bf Second Solution.} We will show there is no solution to the system modulo 13. Add the two equations and add 1 to obtain \[ (x^3+y+1)^2+z^9=147^{157}+157^{147}+1. \] By Fermat's Theorem, $a^{12}\equiv 1$ (mod $13$) when $a$ is not a multiple of 13. Hence we compute $147^{157}\equiv 4^1\equiv 4$ (mod $13$) and $157^{147}\equiv 1^3\equiv 1$ (mod $13$). Thus \[ (x^3+y+1)^2+z^9\equiv 6 {\rm ~(mod~}13). \] The cubes mod 13 are $0, \pm 1$, and $\pm 5$. Writing the first equation as \[ (x^3+1)(x^3+y) \equiv 4 {\rm ~(mod~}13), \] we see that there is no solution in case $x^3 \equiv -1 {\rm ~(mod~}13)$ and for $x^3$ congruent to $0, 1, 5, -5$ (mod 13), correspondingly $x^3 + y$ must be congruent to $4, 2, 5, -1$. Hence \[ (x^3+y+1)^2\equiv 12, 9, 10, {\rm ~or~} 0 {\rm ~(mod~}13). \] Also $z^9$ is a cube, hence $z^9$ must be 0, 1, 5, 8, or 12 (mod 13). It is easy to check that 6 (mod 13) is not obtained by adding one of 0, 9, 10, 12 to one of 0, 1, 5, 8, 12. Hence the system has no solutions in integers. {\em Note.} This argument shows there is no solution even if $z^9$ is replaced by $z^3$. This problem was proposed by R\u{a}zvan Gelca. \item Let $ABC$ be an acute-angled triangle, and let $P$ and $Q$ be two points on side $BC$. Construct point $C_1$ in such a way that convex quadrilateral $APBC_1$ is cyclic, $QC_1 \parallel CA$, and $C_1$ and $Q$ lie on opposite sides of line $AB$. Construct point $B_1$ in such a way that convex quadrilateral $APCB_1$ is cyclic, $QB_1 \parallel BA$, and $B_1$ and $Q$ lie on opposite sides of line $AC$. Prove that points $B_1, C_1,P$, and $Q$ lie on a circle. {\bf Solution.} Let $\alpha, \beta, \gamma$ denote the angles of $\Delta ABC$. Without loss of generality, we assume that $Q$ is on the segment $\overline{BP}$. \setlength{\unitlength}{.3pt} \begin{center} \begin{picture}(760,550)(-171,-50) \thicklines \path(0,0)(420,0)(150,360)(0,0) \put(135,155){\circle{411.0960958}} \put(345,225){\circle{474.341649}}\ \path(120,0)(-55.023582,233.364775) \path(120,0)(311.58549,459.805176) \put(105,-35){$Q$} \put(125,377){$A$} \put(-20,-40){$B$} \put(410,-40){$C$} \put(-100,238){$C_1$} \put(300,475){$B_1$} \put(260,-40){$P$} \put(360,18){$\gamma$} \put(22,17){$\beta$} \put(140,310){$\alpha$} \end{picture} \end{center} We guess that $B_1$ is on the line through $C_1$ and $A$. To confirm that our guess is correct and prove that $B_1, C_1, P$, and $Q$ lie on a circle, we start by letting $B_2$ be the point other than $A$ that is on the line through $C_1$ and $A$, and on the circle through $C,P$, and $A$. Two applications of the Inscribed Angle Theorem yield $\angle PC_1A \cong \angle PBA$ and $\angle AB_2P \cong \angle ACP$, from which we conclude that $\Delta PC_1B_2 \sim \Delta ABC$. \begin{center} \begin{picture}(760,550)(-171,-50) \thicklines \path(0,0)(420,0)(150,360)(0,0) \put(135,155){\circle{411.0960958}} \put(345,225){\circle{474.341649}}\ \path(120,0)(-55.023582,233.364775) \put(105,-35){$Q$} \put(125,377){$A$} \put(-20,-40){$B$} \put(410,-40){$C$} \put(-100,238){$C_1$} \put(300,475){$B_2$} \put(260,-40){$P$} \path(-55.023582,233.364775)(311.58549,459.805176)(270,0)(-55.024582,233.364775) \put(360,18){$\gamma$} \put(275,405){$\gamma$} \put(22,17){$\beta$} \put(-23,225){$\beta$} \put(240,35){$\alpha$} \end{picture} \end{center} From $QC_1 \parallel CA$ we have $m \angle PQC_1 = \pi - \gamma$ so quadrilateral $PQC_1B_2$ is cyclic. By the Inscribed Angle Theorem, $m \angle B_2 Q C_1 = \alpha$. \begin{center} \begin{picture}(760,550)(-171,-50) \thicklines \path(0,0)(420,0)(150,360)(0,0) \put(135,155){\circle{411.0960958}} \put(345,225){\circle{474.341649}}\ \path(120,0)(-55.023582,233.364775) \path(120,0)(311.58549,459.805176) \put(105,-35){$Q$} \put(125,377){$A$} \put(-20,-40){$B$} \put(410,-40){$C$} \put(-100,238){$C_1$} \put(300,475){$B_2$} \put(260,-40){$P$} \put(360,18){$\gamma$} \put(22,17){$\beta$} \put(102,39){$\alpha$} \end{picture} \end{center} Finally, $m \angle PQB_2 = (\pi - \gamma) - \alpha = \beta$, from which it follows that $B_1 = B_2$ and thus $P,Q,C_1$, and $B_1$ are concyclic. This problem was proposed by Zuming Feng. \item Legs $L_1, L_2, L_3, L_4$ of a square table each have length $n$, where $n$ is a positive integer. For how many ordered 4-tuples $(k_1, k_2, k_3, k_4)$ of nonnegative integers can we cut a piece of length $k_i$ from the end of leg $L_i \; (i=1,2,3,4)$ and still have a stable table? (The table is {\em stable} if it can be placed so that all four of the leg ends touch the floor. Note that a cut leg of length 0 is permitted.) {\bf Solution.} Turn the table upside down so its surface lies in the $xy$-plane. We may assume that the corner with leg $L_1$ is at $(1,0)$, and the corners with legs $L_2, L_3, L_4$ are at $(0,1), (-1,0), (0,-1)$, respectively. (We may do this because rescaling the $x$ and $y$ coordinates does not affect the stability of the cut table.) For $i=1,2,3,4$, let $\ell_i$ be the length of leg $L_i$ after it is cut. Thus $0 \le \ell_i \le n$ for each $i$. The table will be stable if and only if the four points $F_1(1,0,\ell_1), \, F_2(0,1,\ell_2), \, F_3(-1,0,\ell_3)$, and $F_4(0,-1,\ell_4)$ are coplanar. This will be the case if and only if $\overline{F_1F_3}$ intersects $\overline{F_2F_4}$, and this will happen if and only if the midpoints of the two segments coincide, that is, \begin{equation} (0,0,(\ell_1 + \ell_3)/2) = (0,0,(\ell_2 + \ell_4)/2). \tag{$\ast$} \end{equation} Because each $\ell_i$ is an integer satisfying $0 \le \ell_i \le n$, the third coordinate for each of these midpoints can be any of the numbers $0, \frac{1}{2}, 1, \frac{3}{2}, \ldots, n$. For each nonnegative integer $k \le n$, let $S_k$ be the number of solutions of $x+y=k$ where $x,y$ are integers satisfying $0 \le x,y \le n$. The number of stable tables (in other words, the number of solutions of ($\ast$)) is $N = \sum_{k=0}^n S_k^2$. Next we determine $S_k$. For $0 \le k \le n$, the solutions to $x+y = k$ are described by the ordered pairs $(j,k-j)$, $0 \le j \le k$. Thus $S_k = k+1$ in this case. For each $n+1 \le k \le 2 n$, the solutions to $x+y = k$ are given by $(x,y) = (j,k-j)$, $k-n \le j \le n$. Thus $S_k = 2n-k+1$ in this case. The number of stable tables is therefore \begin{align*} N & = 1^2 + 2^2 + \cdots n^2 + (n+1)^2 + n^2 + \cdots + 1^2 \\[.1in] & = 2 \, \frac{n(n+1)(2n+1)}{6} + (n+1)^2 \\[.1in] & = \frac{1}{3}(n+1)(2n^2 + 4n + 3). \end{align*} This problem was proposed by Elgin Johnston. \item Let $n$ be an integer greater than 1. Suppose $2n$ points are given in the plane, no three of which are collinear. Suppose $n$ of the given $2n$ points are colored blue and the other $n$ colored red. A line in the plane is called a {\em balancing line} if it passes through one blue and one red point and, for each side of the line, the number of blue points on that side is equal to the number of red points on the same side. Prove that there exist at least two balancing lines. {\bf Solution.} We will show that every vertex of the convex hull of the set of given $2n$ points lies on a balancing line. Let $R$ be a vertex of the convex hull of the given $2n$ points and assume, without loss of generality, that $R$ is red. Since $R$ is a vertex of the convex hull, there exists a line $\ell$ through $R$ such that all of the given points (except $R$) lie on the same side of $\ell$. If we rotate $\ell$ about $R$ in the clockwise direction, we will encounter all of the blue points in some order. Denote the blue points by $B_1, \ B_2, \dots, \ B_n$ in the order in which they are encountered as $\ell$ is rotated clockwise about $R$. For $i=1,\dots,n$, let $b_i$ and $r_i$ be the numbers of blue points and red points, respectively, that are encountered before the point $B_i$ as $\ell$ is rotated (in particular, $B_i$ is not counted in $b_i$ and $R$ is never counted). Then \[ b_i = i-1, \] for $i=1,\dots,n$, and \[ 0 \leq r_1 \leq r_2 \leq \dots \leq r_n \leq n-1. \] We show now that $b_i=r_i$, for some $i=1,\dots,n$. Define $d_i=r_i-b_i$, $i=1,\dots,n$. Then $d_1=r_1 \geq 0$ and $d_n = r_n - b_n = r_n - (n-1) \leq 0$. Thus the sequence $d_1,\dots,d_n$ starts nonnegative and ends nonpositive. As $i$ grows, $r_i$ does not decrease, while $b_i$ always increases by exactly 1. This means that the sequence $d_1,\dots,d_n$ can never decrease by more than 1 between consecutive terms. Indeed, \[ d_i - d_{i+1} = (r_i - r_{i+1}) + (b_{i+1}-b_i) \leq 0 + 1 = 1, \] for $i=1,\dots,n-1$. Since the integer-valued sequence $d_1, d_2,\dots,d_n$ starts nonnegative, ends nonpositive, and never decreases by more than 1 (so it never jumps over any integer value on the way down), it must attain the value 0 at some point, i.e., there exists some $i=1,\dots,n$ for which $d_i=0$. For such an $i$, we have $r_i=b_i$ and $RB_i$ is a balancing line. Since $n \geq 2$, the convex hull of the $2n$ points has at least $3$ vertices, and since each of the vertices of the convex hull lies on a balancing line, there must be at least two distinct balancing lines. {\em Notes.} The main ingredient in the solution above is a discrete version of a ``tortoise-and-hare'' argument. Indeed, the tortoise crawls slowly but methodically and is at distance $b_i=i-1$ from the start at the moment $i$, $i=1,\dots,n$, while the hare possibly jumps ahead at first ($r_1 \geq 0 = b_1$), but eventually becomes lazy or distracted and finishes at most as far as the tortoise ($r_n \leq n-1 = b_n$). Since the tortoise does not skip any value and the hare never goes back towards the start, the tortoise must be even with the hare at some point. We also note that a point not on the convex hull need not lie on any balancing line (for example, let $n=2$ and let the convex hull be a triangle). One can show (with much more work) that there are always at least $n$ balancing lines; this is a theorem of J. Pach and R. Pinchasi (On the number of balanced lines, {\em Discrete and Computational Geometry} {\bf 25} (2001), 611--628). This is the best possible bound. Indeed, if $n$ consecutive vertices in a regular $2n$-gon are colored blue and the other $n$ are colored red, there are exactly $n$ balancing lines. This problem was proposed by Kiran Kedlaya. \item For $m$ a positive integer, let $s(m)$ be the sum of the digits of $m$. For $n\ge 2$, let $f(n)$ be the minimal $k$ for which there exists a set $S$ of $n$ positive integers such that $s\left(\sum_{x\in X} x\right)=k$ for any nonempty subset $X\subset S$. Prove that there are constants $010^q$. Suppose the most significant digit of $M$ is the $10^m$ digit, $m\ge q$. Then $N=M-10^{m-q}(10^q-1)$ is a smaller positive multiple of $10^q-1$ and has $s(N)\le s(M)<9q$, a contradiction. \vspace{.10in} Finally, since $10^{q+1} > n$, we have $q+1 > \log_{10} n$. Since $f(n)\ge 9q$ and $f(n)\ge 9$, we have $$f(n)\ge \frac{9q+9}{2} > \frac{9}{2}\log_{10} n.$$ Weaker versions of Lemmas 1 and 2 are still sufficient to prove the desired type of lower bound. \vspace{.10in} \noindent This problem was proposed by Titu Andreescu and Gabriel Dospinescu. \end{enumerate} \vfill {\small \begin{center} Copyright \copyright\ \ Committee on the American Mathematics Competitions,\\ Mathematical Association of America \end{center} } \end{document}