\input amstex
\input epsfx
\hyphenation{Mass-achusetts Central Missouri Wis-con-sin Muthuvel}
\raggedbottom
\overfullrule=0pt
\loadmsam
\loadmsbm
\loadeufm
\def\R{\Bbb R}
\def\Z{\Bbb Z}
\def\Q{\Bbb Q}
\def\C{\Bbb C}
\def\N{\Bbb N}
\tolerance=1600
\hsize=33pc
\vsize=42pc
\centerline{\bf 1997 Missouri MAA Collegiate Mathematics Competition}
\vskip 6pt
\baselineskip=12pt
\lineskip=12pt
\centerline{\bf Session I}
\bigskip
1.  Let $P \ne (0,0)$ be a point on the parabola $y=x^2$.  The normal  
line to the parabola at $P$ will intersect the parabola at another point, 
say $Q$.  Find the coordinates of $P$ so that the $y$-coordinate of 
$Q$ is a minimum.
\bigskip
Solution.
\smallskip
Let $P$ have the coordinates $(p, p^2)$ and $Q$ have the coordinates 
$(q, q^2)$.  Without loss of generality, let $p>0$.  The slope of the 
tangent line to the parabola at $P$ is $2p$ so the slope of the normal 
line to the parabola at $P$ is $-1/2p$.  Thus, the equation of the 
normal line to the parabola at $P$ is 
$$y - p^2 = {-1 \over 2p} (x - p) .$$
Therefore, the point $Q$, the intersection of the normal line and the 
parabola has the $x$-coordinate
$$q = -p - {1 \over 2p} .$$
Hence, the $y$-coordinate of $Q$ is
$$y = q^2 = \biggl( -p - {1 \over 2p} \biggr) ^2 = p^2 + 1 + {1 
\over 4p^2} .$$
Taking the derivative of $y$ as a function of $p$,	
$$y' = 2p - {1 \over 2} p^{-3} = {4p^4 - 1 \over 2p^3} .$$ 
Minimizing $y$ as a function of $p$ yields $p = \sqrt {1/2}$ so
$$P = \biggl( \sqrt {1 \over 2}, {1 \over 2} \biggr) .$$
\bigskip
From Crux Mathematicorum, 1979, Practice 3-2
\smallskip
2. Prove that from any row of $n$ integers one may always select a 
block of adjacent integers whose sum is divisible by $n$.
\bigskip
Solution.
\smallskip
Let the row of integers be $a_1, a_2, \ldots , a_n$ and consider the 
$n$ sums
$$s_1 = a_1,\ s_2 = a_1 + a_2,\ \ldots \ , s_n = a_1 + a_2 + \cdots + 
a_n .$$
If some $s_i \equiv 0 \pmod n$, we are through.  Otherwise we have $n$ 
sums with at most $n-1$ possible residues modulo $n$; hence, by the 
pigeonhole principle, there must be two sums $s_j$ and $s_k$, with 
$j>k$, such that $s_j \equiv s_k \pmod n$, and then
$$s_j - s_k = a_{k+1} + a_{k+2} + \cdots + a_j \equiv 0 \pmod n .$$
\bigskip
3. Find conditions on the parameters $a$, $b$, $c$, and $d$ so that
$$f(x,y) = a \sin (x+y) + b \cos (x+y) + c \sin (x-y) + d \cos (x-y)$$
can be written as $f(x,y) = g(x) h(y)$.
\bigskip
Solution.
\smallskip
Expansion of the sines and cosines gives
$$f(x,y) = (a+c) \sin x \cos y + (a-c) \cos x \sin y + (b+d) \cos x \cos y 
+ (d-b) \sin x \sin y .$$
So, if the factorization is possible,
$$f(x,y) = (A \sin x + B \cos x) (C \sin y + D \cos y),$$
or
$$f(x,y) = AD \sin x \cos y + BC \cos x \sin y + BD \cos x \cos y + AC 
\sin x \sin y .$$
Thus we need to have
$$\eqalign{
&a+c = AD\cr
&a-c = BC\cr
&b+d = BD\cr
&d-b = AC .\cr}$$
Hence,
$${a+c \over d-b} = {AD \over AC} = {D \over C} = {BD \over BC} = {b+d 
\over a-c} .$$
Therefore,
$$a^2 + b^2 = c^2 + d^2 .$$
\bigskip
4. A point $P$ is in the interior of a circle of radius $r$.  Place 
the vertex of a right angle at $P$ and denote by $A$ and $B$ the 
points where the sides of the right angle intersect the circle.  Let 
$Q$ be the point which completes the rectangle $PAQB$.  What is the 
locus of $Q$? 
\bigskip
Solution.
\smallskip
Let the center of the circle be the origin, $O$, and let $\overrightarrow 
p$ be the vector from $O$ to $P$.  $\vert \overrightarrow p \vert ^2 < 
r^2$ since $P$ is in the interior of the circle.  Let $\overrightarrow v 
= \overrightarrow {PA}$ and $\overrightarrow w = \overrightarrow {PB}$.  
We know $\overrightarrow v \perp \overrightarrow w$.  Let 
$\overrightarrow a = \overrightarrow {OA}$ and $\overrightarrow b = 
\overrightarrow {OB}$, and note that $\vert \overrightarrow a \vert = 
\vert \overrightarrow b \vert = r$.  Also, $\overrightarrow a = 
\overrightarrow p + \overrightarrow v$ and $\overrightarrow b = 
\overrightarrow p + \overrightarrow w$.  If $\overrightarrow q = 
\overrightarrow {OQ} = \overrightarrow p + \overrightarrow v + 
\overrightarrow w$, then
$$\eqalign{
\vert \overrightarrow q \vert ^2 &= ( \overrightarrow p + \overrightarrow 
v + \overrightarrow w ) \cdot ( \overrightarrow p + \overrightarrow v + 
\overrightarrow w )\cr
&= \vert \overrightarrow p \vert ^2 + 2 \overrightarrow p \cdot 
\overrightarrow v + 2 \overrightarrow p \cdot \overrightarrow w + 
\overrightarrow v \cdot \overrightarrow v + \overrightarrow w \cdot 
\overrightarrow w \cr
&= \vert \overrightarrow p \vert ^2 + \overrightarrow a \cdot 
\overrightarrow v + \overrightarrow b \cdot \overrightarrow w + 
\overrightarrow p \cdot \overrightarrow v + \overrightarrow p \cdot 
\overrightarrow w \cr
&= \vert \overrightarrow p \vert ^2 + ( \overrightarrow a + 
\overrightarrow p ) \cdot \overrightarrow v + ( \overrightarrow b + 
\overrightarrow p ) \cdot \overrightarrow w \cr
&= \vert \overrightarrow p \vert ^2 + ( \overrightarrow a + 
\overrightarrow p ) \cdot ( \overrightarrow a - \overrightarrow p ) + ( 
\overrightarrow b + \overrightarrow p ) \cdot ( \overrightarrow b - 
\overrightarrow p ) \cr
&= \vert \overrightarrow p \vert ^2 + \vert \overrightarrow a \vert ^2 - 
\vert \overrightarrow p \vert ^2 + \vert \overrightarrow b \vert ^2 - 
\vert \overrightarrow p \vert ^2 \cr
&= 2r^2 - \vert \overrightarrow p \vert ^2 .\cr}$$

Thus, the distance from $O$ to $Q$ is constant, and the locus of $Q$ is a 
circle centered at $O$ with $(\text{radius})^2$ $2r^2 - \vert 
\overrightarrow p \vert ^2$.
\bigskip
5. Let $\{ L_n \}_{n=0}^\infty $ be the sequence of Lucas numbers: 
$L_0 = 2$, $L_1 = 1$, $L_n = L_{n-1} + L_{n-2}$ for $n \ge 2$.  Let 
$DR(N)$ denote the digital root of a positive integer $N$, defined as 
the sum of the digits of $N$, composed enough times until a value 
between 1 and 9 is obtained.  For example, $DR(667) = DR(19) = DR(10) 
= 1$.  Show that there is a smallest positive integer $k$ such that 
$DR(L_{n+k}) = DR(L_n)$ for all integers $n \ge 0$.
\bigskip
Solution.
\smallskip
Let the integer $N > 0$ be represented by
$$N = \sum_{i=0}^r a_i 10^i ,$$
where the integers $a_i$ satisfy $1 \le a_r \le 9$, $0 \le a_i \le 9$ for 
$i=0, 1, 2, \ldots , r-1$, and $a_i = 0$ for $i > r$.  Then
$$N = \sum_{i=0}^r a_i + \sum_{i=1}^r a_i (10^i - 1)$$
and as $9 \ \vert \ (10^i - 1)$, then
$$N \equiv \sum_{i=0}^r a_i \pmod 9 ,$$
where
$$\sum_{i=0}^r a_i = DS (N)$$
is the digital sum of $N$.  Continuation of this reasoning with $DS(N)$ 
itself leads ultimately to $N \equiv DR(N) \pmod 9$.  It follows that if 
$N$, $M$ are two positive integers, then
$$N+M \equiv DR(N) + DR(M) \pmod 9 .$$
But
$$N+M \equiv DR (N+M) \pmod 9 ,$$
so
$$DR(N+M) \equiv DR(N) + DR(M) \equiv DR [ DR(N) + DR(M)] \pmod 9 .$$
As digital roots lie in $[1, 9]$, then we must have the equality
$$DR(N+M) = DR[ DR(N) + DR(M) ] .$$
Since 
$$L_n = L_{n-1} + L_{n-2} \ \ (n \ge 2) ,$$
then the sequence of digital roots of the Lucas numbers is completely 
determined by the first two: $DR(L_0) = 2$, $DR(L_1) = 1$.  There are only 
81 distinct pairs of the integers $1, 2, \ldots 9$, so there must be some 
minimal starting integer $s$ and some minimal period integer $p$ such that 
$DR(L_{s+p}) = DR(L_s)$ and $DR(L_{s+p+1}) = DR(L_{s+1})$.  By 
inspecting the Lucas sequence, it follows that $s=0$ and $p=24$.   
Therefore, the smallest positive integer $k$ such that
$$DR(L_{n+k}) = DR(L_n)$$
for all integers $n \ge 0$ is 24.
\vfill\eject
\centerline{\bf 1997 Missouri MAA Collegiate Mathematics Competition}
\vskip 6pt
\centerline{\bf Session II}
Modified from the 1979 Putnam Exam.
\smallskip
1. Find positive integers $n$ and $a_1, a_2, \ldots , a_n$ such that
$$a_1 + a_2 + \cdots + a_n = 1997$$
and the product $a_1 a_2 \cdots a_n$ is as large as possible.
\bigskip
Solution.
\smallskip
We see that $n=666$ and that all but one of the $a_i$ equal 3 and the 
exceptional $a_i$ is a 2 as follows.  No $a_i$ can be greater than 4 
since one could increase the product by replacing 5 by $2 \cdot 3$, 6 
by $3 \cdot 3$, 7 by $3 \cdot 4$, etc.  There cannot be both a 2 and a 
4 or three 2's among the $a_i$ since $2 \cdot 4 < 3 \cdot 3$ and $2 
\cdot 2 \cdot 2 < 3 \cdot 3$.  Also, there cannot be two 4's since $4 
\cdot 4 < 2 \cdot 3 \cdot 3$.  Clearly, no $a_i$ is a 1.  Hence the 
$a_i$ are 3's except possibly for a 4 or for a 2 or for two 2's.  Since 
$1997 = 3 \cdot 665 + 2$, the only exception is a 2 and $n=666$. 
\bigskip
From the All-Soviet Mathematics Competition, 1962 - Problem 19
\smallskip
2. Let $a$, $b$, $c$, $d$ be positive numbers with $abcd = 1$.  Prove that
$$a^2 + b^2 + c^2 + d^2 + ab + ac + ad + bc + bd + cd \ge 10.$$
\bigskip
Solution.
\smallskip
By the A.M.-G.M. $\ne$,
$${a^2 + b^2 + c^2 + d^2 \over 4} \ge \root 4 \of {a^2 b^2 c^2 d^2} = 1$$
and
$${ab + ac + ad + bc + bd + cd \over 6} \ge \root 6 \of {a^3 b^3 c^3 d^3} 
= 1 .$$
The result follows. 
\vfill\eject
From one of Martin Gardner's books
\smallskip
3. A wooden cube of edge 3 is formed by gluing together 27 small cubes 
of edge 1.  A termite, beginning with any one of the outer small 
cubes, begins to eat its way through the large cube, always moving 
perpendicular to a face (i.e., no diagonal movements are allowed - 
don't ask why, who knows the mind of a termite?)  Is it possible for 
the termite to follow a path entirely within the large cube (emerging 
and crawling on the outside is also not allowed) which passes through 
each small cube exactly once and ends in the center cube?  Generalize 
the problem to the case where the large cube has edge $n$, an odd 
integer. 
\bigskip
Solution.
\smallskip
\eps{cube.ps}
Consider the graph with a vertex for each small cube and an edge 
connects two vertices if their corresponding cubes are adjacent.

Now, suppose the termite begins at an outer vertex, follows the 
edges of the graph, visits each vertex exactly once, and ends at the 
center vertex.  This path alternates visiting the 13 $\circ$ and 14 
$\bullet$ vertices and must end in the center $\circ$ vertex.  
However, no matter if we start at an outer $\circ$ or $\bullet$ vertex, 
this is impossible.

In the $5 \times 5 \times 5$ case, if the corner vertex is a $\bullet$  
vertex, then there are 62 $\circ$ vertices, 63 $\bullet$ vertices and 
the center vertex is a $\bullet$ vertex.  By a parity argument, the 
only possible requested paths, if they exist, must start in an outer 
$\bullet$ vertex.  Furthermore, by experimentation, if the termite 
starts in any $\bullet$ vertex on the outside, then the termite can 
travel on a path which visits every vertex exactly once and ends in 
the center $\bullet$ vertex.

Similar arguments show that if $n=2k-1$ and $k$ is even, then the 
termite cannot start on an outer vertex and end up in the center.  But, 
if $n=2k-1$ and $k$ is odd, then the termite can start in a corner 
vertex and end up in the center.
\bigskip
From an article by Nancy Edwards in {\it The Pentagon}, Fall 1971.
\smallskip
4. Define a family of curves by
$$S_n = \{ (x,y) : y = {1 \over n} \sin (n^2 x),\ 0 \le x \le \pi \},$$
where $n$ is a positive integer.  What is the limit of the length of 
$S_n$ as $n \to \infty$? 
\bigskip
Solution.
\smallskip
Denote the length of $S_n$ by $L(S_n)$.  Then
$$L(S_n) = \int_0^\pi \sqrt {1 + n^2 \cos ^2 (n^2 x)} dx .$$
Clearly,
$$\sqrt {1 + n^2 \cos ^2 (n^2 x)} > \sqrt {n^2 \cos ^2 (n^2 x)} = n \vert 
\cos (n^2 x) \vert ,$$
so
$$L(S_n) > \int_0^\pi n \vert \cos (n^2 x) \vert dx .$$
The period of $\cos (n^2 x)$ is $2 \pi / n^2$, and $\cos (n^2 x) \ge 0$ 
for $0 \le x \le \pi / 2n^2$, so
$$\eqalign{
L(S_n) &> 2n^3 \int_0^{\pi / 2n^2} \cos (n^2 x) dx \cr
&= 2n^3 \biggl( {\sin (n^2 x) \over n^2} \biggr) _0^{\pi / 2n^2} \cr
&= 2n .\cr}$$
Therefore,
$$\lim_{n \to \infty} L(S_n) = \infty .$$
\vfill\eject
From the 1982/3 International Mathematical Olympiad
\smallskip
5. Consider the infinite sequences $\{ x_n \}$ of positive real 
numbers with the following properties:
$$x_0 = 1,\ \ \text{and for all } i \ge 0,\ \ x_{i+1} \le x_i .$$
(a) Prove that for every such sequence, there is an $n \ge 1$ such 
that
$${x_0^2 \over x_1} + {x_1^2 \over x_2} + \cdots + {x_{n-1}^2 \over 
x_n} \ge 3.999 .$$
(b) Find such a sequence for which
$${x_0^2 \over x_1} + {x_1^2 \over x_2} + \cdots + {x_{n-1}^2 \over 
x_n} < 4\ \ \text{for all } n.$$
\bigskip
Solution.
\smallskip
(a) We will prove the series
$${x_0^2 \over x_1} + {x_1^2 \over x_2} + {x_2^2 \over x_3} + \cdots ,\ 
\ \text{where} \ 1 = x_0 \ge x_1 \ge x_2 \ge \cdots > 0,\leqno(1)$$
has sum $\ge 4$ (with the obvious convention that this holds if the 
series diverges).  This clearly implies that some partial sum of the 
series is $\ge 3.999$.

Let $L$ be the $\inf$ ( $=$ greatest lower bound) of the sums of all 
series of the form (1).  Clearly $L > 1$ since the first term ${1 \over 
x_1} \ge 1$.  For any $\epsilon > 0$, we can find a sequence $\{ x_n 
\}$ such that
$$L + \epsilon > {x_0^2 \over x_1} + {x_1^2 \over x_2} + {x_2^2 \over 
x_3} + \cdots .\leqno(2)$$
Setting $y_n = x_{n+1}/x_1$ $(n \ge 0)$, we note that $1 = y_0 \ge y_1 
\ge y_2 \ge \cdots > 0$.  The series on the right side of (2) can be 
written in the form
$${1 \over x_1} + x_1 \biggl( {y_0^2 \over y_1} + {y_1^2 \over y_2} + 
{y_2^2 \over y_3} + \cdots \biggr) .$$
By the definition of $L$, the series in parentheses has sum $\ge L$.  
Hence from (2) we have
$$L + \epsilon > {1 \over x_1} + x_1 L .$$
Applying the A.M.-G.M. inequality to the right side, we get $L + 
\epsilon > 2 \sqrt L$.  Since this holds for all $\epsilon > 0$, it 
follows that $L \ge 2 \sqrt L$.  Hence $L^2 \ge 4L$, and since $L > 0$, 
this implies that $L \ge 4$.
\smallskip
(b) Let $x_n = {1 / 2^n}$.  Then
$$\sum_{n=0}^\infty {x_n^2 \over x_{n+1}} = \sum_{n=0}^\infty {1 \over 
2^{n-1}} = 4,$$
so all partial sums of the series are $<4$.
\bye
