\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