\input amstex
\input epsfx
\hyphenation{Mass-achusetts Central Missouri Wis-con-sin Muthuvel}
\raggedbottom
\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
\baselineskip=12pt
\lineskip=12pt
\centerline{\bf 2000 Missouri MAA Collegiate Mathematics Competition}
\vskip 6pt
\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 distance between
the $x$-coordinates of $P$ and $Q$ is a minimum.
\bigskip
Solution.
\medskip
Let $P = (p,p^2)$ and $Q = (q,q^2)$. 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) .$$
Since $Q = (q,q^2)$ lies on the normal line,
$$q^2 - p^2 = - {1 \over 2p} (q-p)\ \ \text{or}\ \ q + p = - {1 \over
2p} .$$
Now the distance between the $x$-coordinates of $P$ and $Q$ is
$$D = \bigg\vert 2p + {1 \over 2p} \bigg\vert .$$
Assuming $p > 0$,
$$D = 2p + {1 \over 2p} .$$
Using the AM--GM Inequality, it is known that for all $x > 0$,
$$x + {1 \over x} \ge 2,$$
with equality when $x=1$.
Therefore, $p = 1/2$ if $p>0$ or $p = -1/2$.
Hence, the coordinates of $P$ resulting in a minimum distance between
the $x$-coordinates of $P$ and $Q$ are
$$\biggl( \pm {1 \over 2}, {1 \over 4} \biggr) .$$
\bigskip
From {\it Crux Mathematicorum}, Problem 323, Proposed by Jack Garfunkel,
Forest Hills High School, Flushing, New York and M. S. Klamkin,
University of Alberta, 4 (1978), 255--256.
\medskip
2. If $xyz = (1-x)(1-y)(1-z)$ where $0 \le x, y, z \le 1$, show that
$$x(1-z) + y(1-x) + z(1-y) \ge {3 \over 4} .$$
\bigskip
Solution by Basil C. Rennie, James Cook University of North Queensland,
Australia.
\medskip
From $0 \le x \le 1$ and $(x - 1/2)^2 \ge 0$, we get $0 \le x(1-x) \le
1/4$. From this and two similar results,
$$xyz(1-x)(1-y)(1-z) \le {1 \over 64} .\eqno(1)$$
By the given relation, the left side of (1) is $(xyz)^2$; so $xyz \le
1/8$. Using the relation again yields
$$x(1-z) + y(1-x) + z(1-y) = 1 - 2xyz \ge {3 \over 4} .$$
Equality occurs when $x = y = z = 1/2$.
\bigskip
3. Let $n \ge 3$ points be given in the plane. Prove that three of them form
an angle which is at most $\pi / n$.
\bigskip
Solution.
\medskip
Suppose the $n$ points are labeled as $P_j$, $1 \le j \le n$. Note that
if any $3$ of them are collinear then an angle of measure zero exists,
so we may assume no $3$ of them are collinear. Let $P$ be the convex
polygon obtained as the convex hull of the $n$ points. Then each of the
points is either a vertex or an interior point of $P$ and at least $3$
of them are vertices. Assume then that $P_1$, $P_2$, $P_n$ are adjacent
vertices of $P$ with $P_1$ ``between'' $P_2$ and $P_n$. Then (by
relabeling points as needed) we have
$$\eqalign{
\pi &= m ( \angle P_1 P_2 P_n ) + m( \angle P_1 P_n P_2 ) + m( \angle P_2
P_1 P_n ) \cr
&= m( \angle P_1 P_2 P_n ) + m( \angle P_1 P_n P_2 ) +
\sum_{i=2}^{n-1} m( \angle P_i P_1 P_{i+1} ) .\cr}$$
So by the pigeonhole principle, at least one of these $n$ angles has
measure less than or equal to $\pi / n$.
\bigskip
From Joh. Bernoulli, 1697.
\medskip
4. Justify as far as you can, the equality
$$\int_0^1 x^x dx = 1 - {1 \over 2^2} + {1 \over 3^3} - {1 \over 4^4} +
{1 \over 5^5} - \cdots .$$
\bigskip
Solution.
\medskip
Formally, we have ($\ln$ denotes the natural logarithm)
$$\int _0^1 x^x dx = \int _0^1 e^{x \ln x} dx = \sum_{n=0}^\infty {1 \over
n!} \int _0^1 (x \ln x)^n dx .$$
If $m \le n$, we have, using integration by parts,
$$\int _0^1 x^n (\ln x)^m dx = -{m \over n+1} \int _0^1 x^n (\ln x)^{m-1}
dx ,$$
and so
$$\int _0^1 (x \ln x)^n dx = (-1)^n {n! \over (n+1)^n} \int _0^1 x^n dx =
{(-1)^n n! \over (n+1)^{n+1}} .$$
We get, then,
$$\int _0^1 x^x dx = \sum_{n=1}^\infty {(-1)^{n-1} \over n^n} = 1 - {1
\over 2^2} + {1 \over 3^3} - {1 \over 4^4} + {1 \over 5^5} - \cdots .$$
%$\underline{\text{Note}}$. Mention should be made of the fact that
%$x^x \to 1$ as $x \to 0^+$, so that the integral is ``removably''
%improper. Also, the interchange of the integral and the sum requires
%justification, such as uniform convergence. This did not bother
%Bernoulli much in 1697, however.
\medskip
\noindent $\underline{\text{Note}}$. Bernoulli's 1697 solution ended here. The
need to deal with uniform convergence-type questions was not
recognized until later.
\medskip
\noindent Let $\{ f_n (x) \} _{n=0}^\infty$ be the sequence of functions defined
by
$$f_n (x) = \cases ( x \ln x )^n / n!,& \text{$n \ge 1$, $\ 0 < x \le 1$}\\
1,& \text{$n = 0$, $0 \le x \le 1 $.}
\endcases$$
$n$-fold application of L'H\^{o}pital's theorem gives
$$\lim_{x \to 0^+} f_n (x) = 0,\ \ (n > 0),$$
so $f_n (x)$ is continuous, and therefore integrable, on $[0,1]$. On
the interval $(0,1)$ $x \ln x$ is negative and has a single local
minimum of $-e^{-1}$. It follows that on $[0,1]$,
$$\vert f_n (x) \vert \le {1 \over e^n n!}$$
for $n \ge 0$. One sees easily that
$$\vert f_n (x) \vert < {1 \over n^2}$$
for all $n \ge 1$. But
$$\sum_{n=1}^\infty {1 \over n^2}$$
converges, so by the Weierstrass M-Test the sequence $\{ f_n (x) \}
_{n=0}^\infty$ converges uniformly on $[0,1]$. This, in turn,
guarantees that
$$\sum_{n=0}^\infty \int_0^1 f_n (x) dx = \int_0^1 \biggl(
\sum_{n=0}^\infty f_n (x) \biggr) dx = \int_0^1 x^x dx .$$
\bigskip
5. Show that a polynomial in $x$ with real coefficients which takes
rational values for rational $x$ and (real) irrational values for
(real) irrational $x$ must be linear.
\bigskip
Solution.
\medskip
Note that the polynomial cannot be constant. Denote the polynomial by
$f(x)$ and its degree by $n$. Since $x \in \Q$ implies $f(x) \in \Q$, we
know that $f(0) = y_0$, $f(1) = y_1$, $\ldots$, $f(n) = y_n$ are all
rational. Now consider
$$g(x) = \sum_{i=0}^n y_i L_i (x) ,$$
where
$$L_i (x) = \prod_{\scriptstyle k=0 \atop \scriptstyle k \ne i}^n {(x-k)
\over (i - k)} .$$
Since $f(x)$ and $g(x)$ are both polynomials of degree $n$ which agree at
the $n+1$ values $0, 1, \ldots , n$, $f(x)$ and $g(x)$ must have the same
coefficients, so $f(x)$ must have rational coefficients.
Now assume to the contrary that $n > 1$. Since the coefficients of $f(x)$
are rational, we can write
$$f(x) = (a_n x^n + \cdots + a_1 x + a_0 ) / d ,$$
where $a_i$ and $d$ are integers. We will derive a contradiction by
finding a rational value $r$ such that $f(x) = r$ has a real irrational
solution. Let $r = (p+a_0)/d$, with $p$ a prime number to be determined.
Without loss of generality, we may assume that $a_n > 0$. For
sufficiently large $p$, $f(x) = r$ has a positive root which is
approximately
$$\biggl( {p \over a_n} \biggr) ^{1/n} .$$
But by the Rational Root Test, the only positive rational roots of $f(x) =
r$ are $1 / \lambda$ or $p / \lambda$, where $\lambda$ is a divisor of
$a_n$. But for sufficiently large $p$, the former are too small while the
latter are too large, so $f(x) = r$ has a real irrational root.
Contradiction.
\vfill\eject
\centerline{\bf 2000 Missouri MAA Collegiate Mathematics Competition}
\vskip 6pt
\centerline{\bf Session II}
\bigskip
1. Two points are chosen at random (with a uniform distribution) from
the unit interval $[0,1]$. What is the probability that the points will
be within a distance of $\epsilon$ of each other?
\bigskip
Solution.
\medskip
Clearly if $\epsilon \ge 1$, then the probability is $1$. If $0 \le
\epsilon < 1$, then the probability is the area of the region defined
by $0 \le x \le 1$, $0 \le y \le 1$, and $\vert x-y \vert \le
\epsilon$ (divided by the area of the unit square). But this is $1-2
\cdot (1 - \epsilon )^2 / 2 = 2 \epsilon - \epsilon ^2$.
\eps{diag.eps}
\bigskip
From Macalester College Problem of the Week \# 820.
\medskip
2. Write Pascal's Triangle as an infinite array as follows:
$$\matrix 1&1&1&1&1&\cdots \cr
1&2&3&4&5&\cdots \cr
1&3&6&10&15&\cdots \cr
1&4&10&20&35&\cdots \cr
1&5&15&35&70&\cdots \cr
\vdots&\vdots&\vdots&\vdots&\vdots&\ddots \cr \endmatrix $$
where the first row and first column consist entirely of ones and every
other entry is formed by taking the sum of the entry to the left and the
entry above. For each positive integer $n$, let $D_n$ denote the $n$ by
$n$ matrix formed by the first $n$ rows and first $n$ columns of the
array. What is the determinant of $D_n$? Prove your answer.
\bigskip
Solution.
\medskip
Direct calculations for small values of $n$ suggest that $\det ( D_n
) = 1$ for all $n$.
\smallskip
Outline of Proof:
\smallskip
Perform the following elementary row operations on $D_n$ in the order
specified to change rows $n$ through $2$:
\smallskip
\item{1.} Subtract the $(n-1)$st row from the $n$th row,
\item{2.} Subtract the $(n-2)$nd row from the $(n-1)$st row,
$$\vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$
\item{$(n-1)$.} Subtract the $1$st row from the $2$nd row.
\smallskip
Because of the way the array is constructed, this will translate each
column one position to the right, and will make the first column a
one followed by $(n-1)$ zeros. Repeating this process for rows $n$
through $3$, then for rows $n$ through $4$, etc. gives an upper
triangular matrix with ones on the diagonal, which clearly has
determinant $1$.
\smallskip
Alternatively, expansion by minors of the first column after the
first set of row operations yields $\det ( D_n ) = \det ( D_{n-1} )$.
This and the values for small $n$ give the result.
\bigskip
3. Given an $n \times n$ checkerboard with the four corners removed,
characterize for which $n$ this deleted board can be covered with $3
\times 1$ rectangles.
\bigskip
Solution.
\medskip
There are three cases to consider. If $n \equiv 0 \pmod 3$, then
there are $n^2 - 4$ squares in the deleted board but since this is
not a multiple of $3$, such a covering is impossible. If $n \equiv 2
\pmod 3$, the board can be decomposed into a large central $n \times
(n-2)$ rectangle and two narrow peripheral $(n-2) \times 1$
rectangles each of which can clearly be covered by $3 \times 1$
rectangles. If $n \equiv 1 \pmod 3$ i.e. $n = 3k+1$, label the
squares $1$, $2$, or $3$ as shown in the figure. Any $3 \times 1$
rectangle put on the board will cover exactly one of each of these
numbers, so if a covering is possible, there must be the same number
of $1$'s, $2$'s, and $3$'s. However, there are $4 + 7 + \cdots +
(n-3) + (n-2) + (n-3) + \cdots + 7 + 4 = 3k^2 + 2k - 3$ squares
labeled with a $1$. If there were an equal number of squares with
each label there would be $[(3k+1)^2 - 4]/3 = 3k^2 + 2k - 1$ squares
labeled with a $1$. Contradiction.
\vfill\eject
\null
\eps{square.eps}
\bigskip
4. For $n \ge 2$, let $x_1, \ldots , x_n$ be non-zero real numbers
whose sum is zero. Show that there are $i,j$ with $1 \le i < j \le
n$ such that
$$1/2 \le \vert x_i / x_j \vert \le 2 .$$
\bigskip
Solution.
\medskip
Let $a = \min \{ x_i \}$ and $b = \max \{ x_i \}$. We may assume (by
replacing each $x_i$ with $-x_i$ if necessary) that $\vert a \vert >
b$. If $\vert a \vert \le 2b$, then $1 \le \vert a/b \vert \le 2$
and we are done. So assume that $b < \vert a \vert / 2$.
Now consider the (infinitely many) intervals
$$\ldots , \biggl[ {\vert a \vert \over 2^n} , {\vert a \vert \over
2^{n-1}} \biggr) , \ldots , \biggl[ {\vert a \vert \over 8} , {\vert
a \vert \over 4} \biggr) , \biggl[ {\vert a \vert \over 4}, {\vert a
\vert \over 2} \biggr) .$$
One of these intervals must contain $2$ of the positive $x_i$ values
for otherwise
$$\sum_{x_i > 0} x_i < {\vert a \vert \over 2} + {\vert a \vert \over
4} + \cdots = \vert a \vert \cdot \biggl( {1 \over 2} + {1 \over 4} +
{1 \over 8} + \cdots \biggr) = \vert a \vert ,$$
which is impossible since
$$\sum_{i=1}^n x_i = 0 .$$
So there exist $i \ne j$ such that $x_i$ and $x_j \in [ \vert a \vert
/ 2^n , \vert a \vert / 2^{n-1} )$ for some $n$ and consequently
$$1/2 \le x_i / x_j \le 2 .$$
\bigskip
From {\it From Erd\H{o}s to Kiev} by Ross Honsberger, Dolciani
Mathematical Exposition, 1995, pp. 164--166.
\medskip
5. This problem concerns sequences $x_1 x_2 \cdots x_n$ in which each
$x_i$ is either $a$, $b$, or $c$. Determine the number of those sequences
which have length $n$, begin and end with the letter $a$, and in which
adjacent terms are always different letters.
\bigskip
Solution.
\medskip
We begin by looking briefly at the sequences of a few small values of
$n$. Let the number of sequences of length $n$ be denoted by $t_n$.
$$
\vbox{\tabskip=0pt \offinterlineskip
\def\tablerule{\noalign{\hrule}}
\halign to200pt{\strut#& \vrule#\tabskip=1em plus2em&
\hfil#& \vrule#& #\hfil& \vrule#&
#\hfil& \vrule#\tabskip=0pt\cr\tablerule
&&$n$ &&Sequences &&$t_n$&\cr\tablerule
&&1 &&$a$ &&1&\cr\tablerule
&&2 &&none &&0&\cr\tablerule
&&3 &&$aba$, $aca$ &&2&\cr\tablerule
&&4 &&$abca$, $acba$ &&2&\cr\tablerule
&&5 &&$ababa$, $abaca$, $acaba$, &&&\cr
&& &&$acaca$, $abcba$, $acbca$ &&6&\cr\tablerule \noalign{\smallskip} }}
$$
In attempting to see how sequences of length $n$ might be derived from
shorter ones, one might notice that a sequence of length $n$ can be
obtained by attaching either $ba$ or $ca$ at the end of any sequence
of length $n-2$. For example,
\eps{abc.eps}
\bigskip
Of course, all the sequences generated in this way have the letter $a$ in
the third-last position. Conversely, a sequence of length $n$ whose
third-last term is the letter $a$ yields an acceptable sequence of length
$n-2$ when its last two terms are dropped. Thus the number of sequences
of length $n$ in which the third-last term is the letter $a$ is
$2t_{n-2}$.
For the rest of the sequences of length $n$, the third-last term is
either $b$ or $c$, and each sequence of this kind provides a single
sequence of length $n-1$ by simply deleting its second-last term:
$$\eqalign{
&a \cdots bca \to a \cdots ba,\cr
&a \cdots cba \to a \cdots ca.\cr}$$
(This is not allowed when the third-last term is the letter $a$.)
Conversely, there is only one possible letter that can be inserted
between the last two terms of a sequence, and doing so clearly extends
one of length $n-1$ to one of length $n$. Therefore there are $t_{n-1}$
sequences of length $n$ in which the third-last term is $b$ or $c$, and
we have altogether that
$$t_n = t_{n-1} + 2t_{n-2}$$
with initial conditions $t_1 = 1$ and $t_2 = 0$.
Now assume $t_n = r^n$. Substituting into the difference equation yields
the characteristic equation $r^2 - r - 2 = 0$, from which $r=2$ or $r=-1$. So
the general solution is
$$t_n = c_1 2^n + c_2 (-1)^n .$$
Using the initial conditions lets us find $c_1 = 1/6$ and $c_2 = -2/3$.
Therefore,
$$t_n = {1 \over 3} 2^{n-1} + {2 \over 3} (-1)^{n-1} .$$
%Now, if we attach the unknown numbers $t_n$ to the terms of a power
%series $f(x)$ as follows,
%$$f(x) = t_1 + t_2 x + t_3 x^2 + \cdots + t_n x^{n-1} + \cdots ,$$
%then
%$$x \cdot f(x) = t_1 x + t_2 x^2 + \cdots + t_{n-1} x^{n-1} + \cdots ,$$
%and
%$$2x^2 \cdot f(x) = 2t_1 x^2 + \cdots + 2t_{n-2} x^{n-1} + \cdots .$$
%Subtracting the second and third rows from the first, the recursion $t_n
%- t_{n-1} + 2t_{n-2} = 0$ gives (recall $t_1 = 1$ and $t_2 = 0$),
%$$(1-x-2x^2) f(x) = t_1 + (t_2 - t_1) x = 1-x ,$$
%and therefore
%$$f(x) = {1-x \over 1-x-2x^2} .$$
%Expanding this expression into its partial fractions, we obtain
%$${1-x \over (1-2x)(1+x)} = {A \over 1-2x} + {B \over 1+x}$$
%so
%$$1-x = A(1+x) + B(1-2x) .$$
%For $x=-1$ and $1/2$, respectively, we find $2=3B$ and $1/2 = 3A/2$,
%giving $A=1/3$ and $B=2/3$. Thus
%$$\eqalign{
%f(x) &= {1 \over 3} (1-2x)^{-1} + {2 \over 3} (1+x)^{-1} \cr
%&= {1 \over 3} (1+2x+ \cdots + 2^{n-1} x^{n-1} + \cdots ) \cr
%&\ \ + {2 \over 3} (1-x+ \cdots + (-1)^{n-1} x^{n-1} + \cdots ) ,\cr}$$
%from which the coefficient $t_n$ of $x^{n-1}$ is
%$$t_n = {1 \over 3} \cdot 2^{n-1} + {2 \over 3} \cdot (-1)^{n-1} =
%{2^{n-1} + 2(-1)^{n-1} \over 3} .$$
\bye