MathLinks :: View topic - Year 15, Round 4, Problem 3

\documentclass[12pt]{article}
%\pagestyle{empty}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\topmargin}{-0.5in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}
\usepackage[pdftex]{graphicx}
\usepackage{amsmath,amssymb}
\begin{document}
\begin{center}\large\bfseries
USA Mathematical Talent Search\\
CREDITS and QUICK ANSWERS\\
Round 4 --- Year 15 --- Academic Year 2003--2004\\
\end{center}
\setlength{\parindent}{0pt}
\setlength{\parskip}{3pt}

\textbf{1/4/15.}
\parbox[t]{5.75in}{\footnotesize\sffamily
Find, with proof, the smallest positive integer $n$ for which the sum of the digits of $29n$ is as small as possible.}

This problem was fashioned after Problem 3 of the 2nd Lithuanian Olympiad administered at Vilnius University on September 30, 2000.

We search for $29n$ rather than directly for $n$. Numbers with only a single nonzero digit are that digit times a power of ten, which would not be divisible by $29$. Of the numbers with two nonzero digits, the smallest digit sum occurs with both nonzero digits being~$1$. The smallest such number must begin and end in~$1$, because if it ended in zero, we could divide by $10$. So we are looking for the smallest integer of the form $10^e+i$ that is a multiple of $29$.

The powers of $10$ mod~$29$ are $1$, $10$, $13$, $14$, $24$, $8$, $22$, $17$, $25$, $18$, $6$, $2$, $20$, $26$, $28$, $19$, $16$, $15$, $5$, $21$, $7$, $12$, $4$, $11$, $23$, $27$, $9$, $3$, $1$, $\ldots$. so $10^{14}\equiv 28\pmod{29}$. Therefore $10^{14}+1$ is divisible by $29$, and $n=(10^{14}+1)/29 = 3448275862069$.
\bigskip

\textbf{2/4/15.}
\parbox[t]{5.75in}{\footnotesize\sffamily
For four integer values of $n$ greater than six, there exist right triangles whose side lengths are integers equivalent to $4$, $5$, and $6$ modulo~$n$, in some order. Find those values. Prove that at most four such values exist. Also, for at least one of those values of $n$, provide an example of such a triangle.}

This problem was devised by Dr.~Peter Anspach of the NSA, after a lunchtime conversation among mathematicians about trying to create a $(4,5,6)$ right triangle.

Let $a$, $b$, and $c$ be the sides of such a right triangle, with $a^2+b^2=c^2$. If $c\equiv 4\pmod n$, then $5^2+6^2\equiv 4^2\pmod n$ so $n$ is a factor of $5^2+6^2-4^2 = 45$. If $c\equiv 5\pmod n$, then $n$ is a factor of $4^2+6^2-5^2 = 27$. If $c\equiv 6\pmod n$, then $n$ is a factor of $4^2+5^2-6^2 = 5$, but since $n>6$, we can reject this case. Thus, $n$ is a factor of $27$ or $45$, so $n$ is $9$, $15$, $27$, or $45$.

Given an $n$, a triple $(a,b,c)$ that forms a right triangle can be found by trial and error, by applying number theory to an equation such as $(9x+5)^2+(9y+6)^2 =(9z+4)^2$, or by the $(r(s^2-t^2),2rst,r(s^2+t^2))$ method of finding Pythagorean triples after solving for $r$, $s$, and $t$ that give the right values mod~$n$. The first three solutions for each case are:
\begin{description}
\item for $n=9$ and $c\equiv 4\pmod{9}$: $(24,32,40)$, $(51,68,85)$, $(78,104,130)$;
\item for $n=9$ and $c\equiv 5\pmod{9}$: $(40,96,104)$, $(15,112,113)$, $(60,175,185)$;
\item for $n=15$ and $c\equiv 4\pmod{15}$: $(65,156,169)$, $(140,336,364)$, $(215,516,559)$;
\item for $n=27$ and $c\equiv 5\pmod{27}$: $(168,490,518)$, $(33,544,545)$, $(814,1248,1490)$;
\item for $n=45$ and $c\equiv 4\pmod{45}$: $(1176, 2975,3199)$, $(3920,16926,17374)$, $(1760,17556,17644)$.
\end{description} \vfil
\eject

\textbf{3/4/15.} \parbox[t]{5.75in}{\footnotesize\sffamily Find a nonzero polynomial $f(w,x,y,z)$ in the four indeterminates $w$, $x$, $y$, and~$z$ of minimum degree such that switching any two indeterminates in the polynomial gives the same polynomial except that its sign is reversed. For example, $f(z,x,y,w) = -f(w,x,y,z)$. Prove that the degree of the polynomial is as small as possible.}

This problem was invented by Dr.~David Grabiner, an NSA mathematician who helps with the evaluation and grading of problems for the USAMTS.

Consider any two of the indeterminants, say $w$ and $x$.
If the standard form of $f (w,x,y,z)$ has a term $kw^ax^by^cz^d$, then it must have a matching term $-kw^bx^ay^cz^d$. Grouping them together gives either $k(w^{a-b}-x^{a-b})w^bx^by^cz^d$ or $k(x^{b-a}-w^{b-a})w^ax^ay^cz^d$, which both are divisible by $w-x$. Since the
entire polynomial can be grouped this way, it is divisible by $w-x$.

Thus, for every pair of indeterminants, the polynomial is divisible by their difference. This means $f(w,x,y,z)$ is divisible by $(w-x)(w-y)(w-z)(x-y)(x-z)(y-z)$. Letting $f(w,x,y,z)= (w-x)(w-y)(w-z)(x-y)(x-z)(y-z)$ keeps the degree to a minimum, and it works because switching any two indeterminants in $(w-x)(w-y)(w-z)(x-y)(x-z)(y-z)$ gives the same polynomial except that
its sign is reversed.
\bigskip

\textbf{4/4/15.}
\parbox[t]{5.75in}{\footnotesize\sffamily
For each nonnegative integer $n$ define the function $f_n(x)$ by
\begin{displaymath}
f_n(x) = \sin^n(x) + \sin^n(x + \frac{2\pi}{3}) + \sin^n(x + \frac{4\pi}{3})
\end{displaymath}
for all real numbers $x$, where the sine functions use radians. The functions $f_n(x)$ can be also expressed as polynomials in $\sin(3x)$ with rational coefficients. For example, \begin{eqnarray*}
&\displaystyle f_0(x) = 3,\qquad f_1(x) = 0,\qquad f_2(x) = \frac32,\qquad f_3(x) = -\frac34\sin(3x),\\
\noalign{\smallskip}
&\displaystyle f_4(x) = \frac98,\qquad f_5(x) = -\frac{15}{16}\sin(3x),\qquad f_6(x) = \frac{27}{32} + \frac{3}{16}\sin^2(3x),
\end{eqnarray*}
for all real numbers~$x$. Find an expression for $f_7(x)$ as a polynomial in $\sin(3x)$ with rational coefficients, and prove that it holds for all real numbers $x$.}

This problem was devised by the distinguished Hungarian mathematician and poet Mih\'aly Bencze of Brasso, Transylvania.

The triple angle formula for sine is $\sin(3x)=3\sin(x)-4\sin^3(x)$. But
since $\sin(3x)$ also equals $\sin(3({x + \frac{2\pi}{3}}))$ and $\sin(3({x + \frac{4\pi}{3}}))$, it also expands to $3\sin({x + \frac{2\pi}{3}}) - 4\sin^3({x + \frac{2\pi}{3}})$ and $3\sin({x + \frac{4\pi}{3}}) - 4\sin^3({x + \frac{4\pi}{3}})$. Thus, for all real numbers~$x$,
\begin{eqnarray*}
f_n(x)\sin(3x) &=& \sin^n(x)\sin(3x) + \sin^n(x + \frac{2\pi}{3})\sin(3x) + \sin^n(x + \frac{4\pi}{3})\sin(3x)\\
&=& \sin^n(x)\bigl(3\sin(x) - 4\sin^3(x)\bigr)\\
&& \qquad {}+ \sin^n(x + \frac{2\pi}{3})\bigl(3\sin(x + \frac{2\pi}{3}) - 4\sin^3(x + \frac{2\pi}{3})\bigr)\\
&& \qquad {}+ \sin^n(x + \frac{4\pi}{3})\bigl(3\sin(x + \frac{4\pi}{3}) - 4\sin^3(x + \frac{4\pi}{3})\bigr)\\
&=&3\bigl(\sin^{n+l}(x)+\sin^{n+l}(x + \frac{2\pi}{3})+\sin^{n+l}(x + \frac{4\pi}{3})\bigr)\\
&&\qquad {}-4\bigl(\sin^{n+3}(x) + \sin^{n+3}(x + \frac{2\pi}{3}) + \sin^{n+3}(x + \frac{4\pi}{3})\bigl)\\
&=&3f_{n+l}(x) - 4f_{n+3}(x).
\end{eqnarray*}
Setting $n$ to 4 and rearranging gives
$f_7(x) = \frac34f_5(x) - \frac14f_4(x)\sin(3x) = (\frac34)(-\frac{15}{16})\sin(3x) - (\frac14)(\frac98)\sin(3x) = (-\frac{63}{64})\sin(3x)$.
\bigskip

\textbf{5/4/15.} \parbox[t]{2.75in}{\footnotesize\sffamily
Triangle $ABC$ is an obtuse isosceles triangle with the property that three squares of equal size can be inscribed in it as shown on the right. The ratio $AC/AB$ is an irrational number that is the root of a cubic polynomial. Determine that polynomial.} \raisebox{-70pt}[0pt]{\setlength{\unitlength}{2pt}
\begin{picture}(95,40)
\put(10,6){\line(1,0){80}}
\put(10,6){\line(4,3){40}}
\put(90,6){\line(-4,3){40}}
\put (5,0){A}
\put (48,37){B}
\put(91,0){C}
\put(39.1,6){\line(0,1){21.8}}
\put(39.1,27.8){\line(1,0){21.8}}
\put(60.9,6){\line(0,1){21.8}}
\put(45.7,6){\line(-3,4){12.85}}
\put (45.7, 6){\line (4, 3){17.1}}
\put(50,36){\line(3,-4){12.85}}
\put(54.3,6){\line(3,4){12.85}}
\put(54.3,6){\line(-4,3){17.1}}
\put(50,36){\line(-3,-4){12.85}}
\put(29,24){D}
\put(36, 30){E}
\put(60,30){F}
\put(67,24){G}
\put(37,0){J}
\put(43,0){K}
\put (53,0){K}
\put(59,0){M}
\put (31,16){H}
\put(65.5,16){I}
\end{picture}}
\medskip

This triangle was apparently discovered by the Italian mathematician Eugenio Calabi. It is the only non-equilateral triangle into which we can fit three equal squares in this manner. The triangle is displayed on page 266 of {\em The Book of Numbers,} by John H. Conway and Richard K. Guy, published by Springer-Verlag in 1996.
\medskip

Let $s$ be the length of a side of the squares. By symmetry, $AJ=MC$, so $2(AJ)={AC-JM}={AC-s}$. $AD=AB-BD=AB-s$. Triangle $AEJ$ is congruent to triangle $AKD$, so $AD=AJ$. So ${AC-s}={2(AB-s)}$, giving $s=2(AB)-AC$ and $AJ=AC-AB$.

Let $P$ be the midpoint of side $\overline{AC}$. Triangle $AEJ$ is
similar to triangle $ABP$. So $AE/AJ=AB/AP=2(AB/AC)$. $AE=2(AC-AB)(AB/AC)$.

By the Pythagorean Theorem $(AE)^2=(AJ)^2+s^2$, which converts to \begin{eqnarray}
\left(2(AC-AB)\left(\frac{AB}{AC}\right)\right)^2
&=& (AC-AB)^2 + (2(AB)-AC)^2\\
\left(2(AC-AB)(AB)\right)^2
&=&(AC)^2(AC-AB)^2 + (AC)^2(2(AB)-AC)^2.
\end{eqnarray}
Let $x=AC/AB$. Equation (2) converts to
\begin{eqnarray*}
4(x-1)^2 &=& x^2(x-1)^2 + x^2(2-x)^2\\
(4-x^2)(x-1)^2 - x^2(2-x)^2 &=& 0\\
(2-x)(x+2)(x-1)^2 - x^2(2-x)^2 &=& 0\\
(2-x)\bigl((x+2)(x-1)^2 - x^2(2-x)\bigr) &=& 0\\
(2-x)(2x^3-2x^2-3x+2) &=& 0
\end{eqnarray*}
By the triangle inequality, $AC<AB+BC=2(AB)$, so $x<2$ and $2-x\ne 0$. Therefore, $AC/AB$ is the root of the cubic polynomial $2x^3-2x^2-3x+2$.

\end{document}