\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
\comment
\hsize=33pc
\vsize=42pc
\endcomment
\hsize=6.5in
\vsize=9in
\baselineskip=12pt
\lineskip=12pt
\centerline{\bf 2006 Missouri Collegiate Mathematics Competition}
\vskip 6pt
\centerline{\bf Session I}
\bigskip
1. Find
$$\lim_{n \to \infty} \biggl( {n \over n^2 + 1} + {n \over n^2 + 4} + {n \over n^2 + 9} + \cdots + {1 \over 2n} \biggr) .$$
\bigskip
Solution.
\medskip
$$\eqalign{
&{n \over n^2 + 1} + {n \over n^2 + 4} + {n \over n^2 + 9} + \cdots + {1 \over 2n} \cr
&= {1 \over n} \biggl( {1 \over 1 + {1 \over n^2}} + {1 \over 1 + {4 \over n^2}} + {1 \over 1 + {9 \over n^2}} + \cdots + {1 \over 1 + {n^2 \over n^2}} \biggr) \cr
&= {1 \over n} \cdot \sum_{r=1}^n {1 \over 1 + \bigl( {r \over n} \bigr) ^2 } .\cr}$$
This is a Riemann sum.  When we take the limit of this as $n$ goes to infinity, the sum changes into an integral given by
$$\int_0^1 {1 \over 1+x^2} \, dx = \text{Tan}^{-1} x \bigg\vert _0^1 = {\pi \over 4} .$$
\bigskip
2.  You have a supply of unit squares, $1 \times 2$ rectangles and $1 \times 3$ rectangles.  With these you wish to ``tile'' a rectangular strip of dimensions $1 \times n$ ($n$ is a positive integer).  For example, if $W_n$ is the number of ways a $1 \times n$ strip can be tiled, then $W_3 = 4$ since
$$3 = 2+1 = 1+2 = 1+1+1 .$$
\comment
$$\epsfxsize=15pc \epsfbox{tiling.eps}$$
\endcomment
Determine how many tiling patterns $W_n$ exist when $n=16$ and prove your answer.
\bigskip
Solution.
\medskip
In tiling a $1 \times n$ strip, the {\it last} piece put in place is either a $1 \times 1$ square, a $1 \times 2$ rectangle, or a $1 \times 3$ rectangle.  The $1 \times 1$ square comes after $W_{n-1}$ ways of tiling a $1 \times (n-1)$ strip.  The $1 \times 2$ rectangle comes after $W_{n-2}$ ways of tiling a $1 \times (n-2)$ strip.  The $1 \times 3$ rectangle comes after $W_{n-3}$ ways of tiling a $1 \times (n-3)$ strip.  Hence,
$$W_n = W_{n-1} + W_{n-2} + W_{n-3}$$
for $n \ge 4$.  A simple computation then yields $W_{16} = 10,609$.
\vfill\eject
3. Let $\{ a_n \}$ be the sequence defined recursively by
$$a_0 = 1,\ a_1 = 0,\ \text{and}\ a_n = {1 \over n} a_{n-2} \ \ \text{for}\ \ n \ge 2 .$$
If the function $f$ is defined by
$$f(x) = \sum_{n=0}^\infty a_n x^n ,$$
find the exact value of $f(2)$. 
\bigskip
Solution.
\medskip
Using the recurrence relation it is easy to see that $a_n = 0$ for all odd $n$.  The even terms
$$a_0 = 1,\ a_2 = {1 \over 2},\ a_4 = {1 \over 8},\ a_6 = {1 \over 48} ,\ \ldots$$
are given by
$$a_{2n} = {1 \over 2^n n!} .$$
Thus, the function $f$ is
$$\eqalign{
f(x) &= \sum_{n=0}^\infty a_n x^n = \sum_{n=0}^\infty a_{2n} x^{2n} \cr
&= \sum_{n=0}^\infty {1 \over 2^n n!} x^{2n} = \sum_{n=0}^\infty {1 \over n!} \biggl( {x^2 \over 2} \biggr) ^n \cr
&= e^{x^2 / 2} .\cr}$$
So the exact value of $f(2)$ is $f(2) = e^{2^2 / 2} = e^2$.
\bigskip
4.  Find all positive integers $c$ such that $n(n+c)$ is never a perfect square for any positive integer $n$.
\bigskip
Solution.
\medskip
Write $n(n+c) = m^2$; then $n^2 + cn - m^2 = 0$, and
$$n = {-c \pm \sqrt {c^2 +4m^2} \over 2} .$$
For $n$ to be integral, it is necessary that $c^2 + 4m^2$ be a perfect square.  
\medskip
Let us consider the situation when $c=1$, $c=2$, or $c=4$  If $c=1$ or $c=2$, $c^2 + 4m^2$ is between $(2m)^2$ and $(2m+1)^2$ and so cannot be a perfect.  If $c=4$, then $4^2 + 4m^2 = 4(4+m^2)$ must be a perfect square.  Therefore, $4+m^2$ must be a perfect square.  Since $m^2 < 4+m^2$, $4+m^2 = (m+1)^2$.  But then $4 = 2m+1$.  This cannot occur since the left and right sides of the equation have opposite parity.
\medskip
For the remaining values of $c$ we consider 3 cases.
\medskip
$\underline{\text{Case 1}}$.  $c>1$ is odd.  Choose
$$n = \biggl( {c-1 \over 2} \biggr) ^2 ;$$
then
$$n(n+c) = \biggl( {c^2 - 1 \over 4} \biggr) ^2 ,$$
so no members in this class are acceptable answers.
\medskip
$\underline{\text{Case 2}}$.  $c=2^r,\ r \ge 3$.  Choose $n=2^{r-3}$; then
$$n(n+c) = \bigl( 3 \cdot 2^{r-3} \bigr) ^2 ,$$
so no members in this class are acceptable answers.
\medskip
$\underline{\text{Case 3}}$.  $c=2^r s$, $s$ odd, $s>1$.  Choose
$$n = 2^r \biggl( {s-1 \over 2} \biggr) ^2 ;$$
then
$$n(n+c) = \biggl( 2^r {s^2 - 1 \over 4} \biggr) ^2 ,$$
so no members in this class are acceptable answers.
\medskip
In summary, the set of integers $c$ requested is $\{ 1, 2, 4 \}$.
\vfill\eject
5. Let $f(t)$ and $f'(t)$ be differentiable on $[a,x]$ and for each $x$ suppose there is a number $c_x$ such that $a < c_x < x$ and
$$\int_a^x f(t) \, dt = f(c_x) (x-a) .$$
Assume that $f' (a) \ne 0$.  Then prove that
$$\lim_{x \to a} {c_x - a \over x - a} = {1 \over 2} .$$
\bigskip
Solution.
\medskip
\comment
Define $K$ by
$$K = \lim_{x \to a} {\int_a^x f(t) \, dt - f(a) (x-a) \over (x-a)^2} .$$
From the form of the Mean Value Theorem for integrals given in the hypotheses, we have
$$\eqalign{
K &= \lim_{x \to a} {f(x) (x-a) - f(a) (x-a) \over (x-a)^2} \cr
&= \lim_{x \to a} \biggl( {f(c_x) - f(a) \over c_x - a} \cdot {c_x - a \over x-a} \biggr) \cr
&= \lim_{c_x \to a} {f(c_x) - f(a) \over c_x - a} \cdot \lim_{x \to a} {c_x - a \over x-a} \ \ \ \ \ \text{since $c_x \to a$ as $x \to a$} \cr
&= f' (a) \lim_{x \to a} {c_x - a \over x-a} .\cr}$$
Alternatively, by l'H\^{o}pital's Theorem we have (upon  applying the Fundamental Theorem of the Calculus)
$$K = \lim_{x \to a} {f(x) - f(a) \over 2 (x-a)} = {1 \over 2} f' (a) .$$
Since $f' (a) \ne 0$ by hypothesis, then
$${1 \over 2} f' (a) = f' (a) \lim_{x \to a} {c_x - a \over x-a}$$
implies
$$\lim_{x \to a} {c_x - a \over x-a} = {1 \over 2} .$$
\endcomment
Let
$$F(x) = \int _a^x f(t) \, dt .$$
Using Taylor's expansion of $F(x)$, we have
$$F(x) = F(a) + (x-a) F' (a) + {(x-a)^2 \over 2} F'' ( \theta _x ) ,$$
where $\theta _x$ lies strictly between $a$ and $x$, and as $x$ goes to $a$, $\theta _x$ also goes to $a$.  We also have $F(a) = 0$, $F' (x) = f(x)$, and $F'' (x) = f' (x)$.  Thus,
$$F(x) = 0 + (x-a) f(a) + {(x-a)^2 \over 2} f' (\theta _x ) .$$
By definition,
$$f(c_x ) = {1 \over x-a} F(x) = f(a) + {x-a \over 2} f' (\theta _x ) .$$
Therefore,
$${f(c_x ) - f(a) \over x-a} = {1 \over 2} f' (\theta _x ) .$$
On the other hand we can write
$${f(c_x ) - f(a) \over x-a}$$
as a product
$${f(c_x ) - f(a) \over c_x - a} \cdot {c_x - a \over x-a} .$$
On taking the limits of these as $x$ goes to $a$, we get
$$\lim _{x \to a} {1 \over 2} f' (\theta _x ) = \lim _{x \to a} {f(c_x ) - f(a) \over c_x - a} \cdot {c_x - a \over x-a} .$$
This gives
$${1 \over 2} f' (a) = \lim _{x \to a} {f(c_x ) - f(a) \over c_x - a} \lim _{x \to a} {c_x - a \over x-a} .$$
In other words,
$${1 \over 2} f' (a) = f' (a) \cdot \lim _{x \to a} {c_x - a \over x-a} .$$
This shows
$$\lim _{x \to a} {c_x - a \over x-a} = {1 \over 2} .$$
\vfill\eject
\centerline{\bf 2006 Missouri Collegiate Mathematics Competition}
\vskip 6pt
\centerline{\bf Session II}
\bigskip
1. The array below is called a magic square because the sum of the three numbers along any row, any column, or the two diagonals, is the same (namely, $15$).
$$\vbox{\tabskip=0pt \offinterlineskip
\def\tablerule{\noalign{\hrule}}
\halign to125pt{\strut#& \vrule#\tabskip=1em plus2em& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#\tabskip=0pt\cr\tablerule
&&\omit&&\omit&&\omit&\cr
&&\hfil$8$\hfil&&\hfil$1$\hfil&&\hfil$6$\hfil&\cr
&&\omit&&\omit&&\omit&\cr
\tablerule
&&\omit&&\omit&&\omit&\cr
&&\hfil$3$\hfil&&\hfil$5$\hfil&&\hfil$7$\hfil&\cr
&&\omit&&\omit&&\omit&\cr
\tablerule
&&\omit&&\omit&&\omit&\cr
&&\hfil$4$\hfil&&\hfil$9$\hfil&&\hfil$2$\hfil&\cr
&&\omit&&\omit&&\omit&\cr
\tablerule \cr}}$$
\item{(a)} Construct a $3 \times 3$ multi-magic square, that is, a $3 \times 3$ array of $9$ distinct integers such that the PRODUCT of the three numbers along any row, any column, or the two diagonals, is the same.
\item{(b)} Show that no multi-magic square can be constructed with nine {\it consecutive} integers.
\bigskip
Solution.
\medskip
\item{(a)} There are many possibilities, but among the easiest to construct might be the following, which makes use of the square above and the property of exponents:
$$\vbox{\tabskip=0pt \offinterlineskip
\def\tablerule{\noalign{\hrule}}
\halign to200pt{\strut#& \vrule#\tabskip=1em plus2em& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#\tabskip=0pt\cr\tablerule
&&\omit&&\omit&&\omit&\cr
&&\hfil$2^8 = 256$\hfil&&\hfil$2^1=2$\hfil&&\hfil$2^6 = 64$\hfil&\cr
&&\omit&&\omit&&\omit&\cr
\tablerule
&&\omit&&\omit&&\omit&\cr
&&\hfil$2^3 = 8$\hfil&&\hfil$2^5 = 32$\hfil&&\hfil$2^7 = 128$\hfil&\cr
&&\omit&&\omit&&\omit&\cr
\tablerule
&&\omit&&\omit&&\omit&\cr
&&\hfil$2^4 = 16$\hfil&&\hfil$2^9 = 512$\hfil&&\hfil$2^2 = 4$\hfil&\cr
&&\omit&&\omit&&\omit&\cr
\tablerule \cr}}$$
\item{(b)} There can be no multi-magic square consisting of nine consecutive integers.  Reducing the entries modulo five shows that among nine consecutive integers, there are at most two multiples of $5$.  Thus, at least one of the columns will have a product which is not a multiple of $5$.
\bigskip
2. Evaluate the limit:
$$\lim_{n \to \infty} {1 \over n^4} \sum_{k=3}^n {k \choose 3} .$$
\bigskip
Solution.
\medskip
Using the identity
$${n \choose r} + {n \choose r-1} = {n+1 \choose r}$$
we have
$$\eqalign{
\sum_{k=3}^n {k \choose 3} &= {3 \choose 3} + \sum_{k=4}^n {k \choose 3} \cr
&= {3 \choose 3} + \sum_{k=4}^n \biggl( {k+1 \choose 4} - {k \choose 4} \biggr) \cr
&= {3 \choose 3} + {n+1 \choose 4} - {4 \choose 4} \cr
&= {n+1 \choose 4} = {(n+1) n (n-1) (n-2) \over 24} .\cr}$$
Therefore,
$$\lim_{n \to \infty} {(n+1) n (n-1) (n-2) \over 24 n^4} = {1 \over 24} .$$
\bigskip
3. Define a sequence of positive integers $\{ x_n \ \vert \ n=1, 2, 3, \ldots \}$ to be {\it Dence} if every positive integer can be expressed as a sum of distinct members of the sequence.  Now consider the sequence in which $x_1 = 1$, $x_2 = 2$, $x_3 = 4$, $x_4 = 7$, $x_5 = 15$, and $x_{k+1} = 2x_k - 7$ for all $k \ge 5$.  Prove that this sequence is Dence.
\bigskip
Solution.
\medskip
By trial all of the positive integers from $1$ to $23 (= x_6)$ are expressible as sums of distinct $x_k$'s.  Now assume that if $n \ge 6$, all of the integers from $1$ to $x_n$ are expressible as sums of distinct $x_k$'s.  Choose any $x \in [x_n + 1, x_{n+1} ]$.  If $x=x_n + 1$, we have trivially $x = x_1 + x_n$.  At the other endpoint representation is even more trivial: $x=x_{n+1}$.  Finally, if $x \in (x_n + 1, x_{n+1} )$, then
$$x_n + 1 + 1 \le x \le 2x_n - 7 - 1 .$$
Writing $x = x_n + r$, then we have
$$2 \le r \le x_n - 8 .$$
By assumption,
$$x_n - 8 = \sum_{k<n} x_k $$
holds, so $x$ itself is representable as a sum of distinct $x_k$'s.  By the Principle of Mathematical Induction every positive integer is expressible as a sum of distinct $x_k$'s, so $\{ x_k \ \vert \ k=1, 2, 3, \ldots \}$ is Dence.
\vfill\eject
Micahel Dorff and Leon Hall, University of Missouri-Rolla
\medskip
4. For a convex polygon with $n$ sides, let $T$ be a point in the interior of the polygon.  Triangulate the polygon by drawing line segments from $T$ to each vertex.  Denote the distance from $T$ to side $s_i$ of the polygon by $r_i$ and the area of the corresponding triangle by $A_i$.  Let $A$ be the total area of the polygon.  Show that the number $r$, defined by
$${1 \over r} = \sum_{i=1}^n \biggl( {A_i \over A} \biggr) \biggl( {1 \over r_i} \biggr) ,$$
is independent of the position (inside the polygon) of $T$.
\bigskip
Solution.
\medskip
Since
$$A_i = {s_i r_i \over 2} ,$$
we get
$${A \over r} = \sum_{i=1}^n {s_i \over 2} = {P \over 2} ,$$
where $P$ is the perimeter of the polygon, making
$$r = {2A \over P}$$
which is independent of the position of $T$.  If the area and perimeter of the polygon are both expressed as functions of $r$, then
$${dA \over dr} = P .$$
\bigskip
5. Let
$$\{ a_n \}_{n=1}^\infty \ \ \text{and}\ \ \{ \Delta a_n \} _{n=1}^\infty = \{ a_n - a_{n+1} \} _{n=1}^\infty $$
be two decreasing sequences of positive numbers that converge to $0$.  Prove that the magnitude of the error, $\vert R_n \vert$, made in approximating the sum of the series
$$\sum_{k=1}^\infty (-1)^{k-1} a_k$$
by its $n$ partial sum is bounded as follows:
$${a_{n+1} \over 2} < \vert R_n \vert < {a_n \over 2} .$$
\vfill\eject
Solution.
\medskip
\comment
Let
$$S_n = \sum_{k=1}^n (-1)^{k-1} a_k ,\ \ X_n = S_n + (-1)^n {a_{n+1} \over 2} ,\ \ \text{and}\ \ \Delta a_n = a_n - a_{n+1}$$
for each positive integer $n$.  Then
$$\eqalign{
X_{2k-1} - X_{2k} &= (S_{2k-1} - S_{2k} ) - \biggl( {a_{2k} \over 2} + {a_{2k+1} \over 2} \biggr) \cr
&= a_{2k} - {1 \over 2} a_{2k} - {1 \over 2} a_{2k+1} = {1 \over 2} \Delta a_{2k} > 0 \cr}$$
by hypothesis.  Additionally, we find that
$$X_{2k+2} - X_{2k} = {1 \over 2} \bigl( \Delta a_{2k+1} - \Delta a_{2k+2} \bigr) > 0$$
and
$$X_{2k-1} - X_{2k+1} = {1 \over 2} \bigl( \Delta a_{2k} - \Delta a_{2k+1} \bigr) > 0 .$$
Thus, the interval $[X_{2k+2} , X_{2k+1} ]$ is contained in the interval $[ X_{2k} , X_{2k-1} ]$, and by extension we have a nested sequence of closed, bounded intervals:
$$[X_2 , X_1 ] \supset [X_4 , X_3 ] \supset [X_6 , X_5 ] \supset \cdots .$$
The lengths of the intervals approach $0$ because
$$\lim_{k \to \infty} (X_{2k-1} - X_{2k} ) = \lim_{k \to \infty} \Delta a_{2k} = 0 ,$$
by hypothesis.  There is, therefore, a unique point common to all of the intervals.  This point is the sum $S$ of the alternating series because
$$\lim_{n \to \infty} X_n = \lim_{n \to \infty} S_n + \lim_{n \to \infty} (-1)^n {a_{n+1} \over 2} = S + 0 = S .$$
It follows that for an arbitrary interval $[ X_{2n} , X_{2n-1} ]$ one has
$$S_{2n} + {a_{2n+1} \over 2} = X_{2n} < S < X_{2n-1} = S_{2n-1} - {a_{2n} \over 2} = \biggl( S_{2n} + {a_{2n} \over 2} \biggr) - {a_{2n} \over 2} ,$$
or equivalently,
$${a_{2n+1} \over 2} < S - S_{2n} < {a_{2n} \over 2} .\eqno(1)$$
Alternatively, because of the nesting of the intervals
$$S_{2k+1} - {a_{2k+1} \over 2} = S_{2k} + {a_{2k+1} \over 2} = X_{2k} < S < X_{2k+1} = S_{2k+1} - {a_{2k+2} \over 2} ,$$
or equivalently,
$${a_{2k+2} \over 2} < S_{2k+1} - S < {a_{2k+1} \over 2} .\eqno(2)$$
Equations (1) and (2) can be combined to read
$${a_{n+1} \over 2} < \vert R_n \vert < {a_n \over 2} ,$$
where $\vert R_n \vert = \vert S - S_n \vert$.
\endcomment
$$\epsfxsize=30pc \epsfbox{figstairs.eps}$$
Consider a function which looks like $f(x) = 1/x$.  It should have two properties: (a) $f(n)$ decreases to zero, and (b) $f(n) - f(n+1)$ decreases to zero.  Let $f(n) = a_n$.

Note that $a_n = a_n \cdot 1 = \text{the area of the rectangle $R$}$ say, whose base goes from $x=n$ to $x=n+1$, and whose height is $a_n$.  Also, consider the rectangles enclosed by the two ordinates $x=n$, and $x=n+1$, and the horizontal lines $y=a_n$, and $y=a_{n+1}$.  Let us call this rectangular area $A_n$.  These areas are shown in the diagram.  Also note that for each $n$, $A_n = a_n - a_{n+1}$.

The important thing to note is that if we translate all the areas $A_{n+1}$, $A_{n+2}$, $A_{n+3}$, $A_{n+4}$, etc. horizontally to the left, they will fit inside $R$ without overlapping and fill the entire rectangle.  In other words, 
$$a_n = A_n + A_{n+1} + A_{n+2} + A_{n+3} + A_{n+4} + \cdots .$$
Now consider the series
$$\sum_{k=1}^\infty (-1)^{k-1} a_k .$$
This is equal to
$$(a_1 - a_2) + (a_3 - a_4) + (a_5 - a_6) + (a_7 - a_8) + \cdots .$$
Let $S_n$ denote its partial sum.  Then,
$$S_n = \cases
(a_1 - a_2) + (a_3 - a_4) + (a_5 - a_6) + \cdots + (a_{n-1} - a_n) &$\text{if $n$ is even}$,\\
(a_1 - a_2) + (a_3 - a_4) + \cdots + (a_{n-2} - a_{n-1} ) + a_n &$\text{if $n$ is odd}$. 
\endcases$$
The error $R_n$ is either
$$R_n = \cases
(a_{n+1} - a_{n+2}) + (a_{n+3} - a_{n+4}) + \cdots &$\text{if $n$ is even}$,\\
-a_{n+1} + a_{n+2} - a_{n+3} + a_{n+4} - \cdots &$\text{if $n$ is odd}$.
\endcases$$
In either case
$$| R_n | = A_{n+1} + A_{n+3} + A_{n+5} + \cdots .$$
We know that
$$a_n = A_n + A_{n+1} + A_{n+2} + A_{n+3} + A_{n+4} + \cdots ,$$
and
$$a_{n+1} = A_{n+1} + A_{n+2} + A_{n+3} + A_{n+4} + \cdots .$$
We will now use the fact that $A_n$ is a decreasing sequence.
$$a_n > A_{n+1} + A_{n+1} + A_{n+3} + A_{n+3} + A_{n+5} + A_{n+5} + \cdots = 2( A_{n+1} + A_{n+3} + A_{n+5} + \cdots ) = 2 | R_n | .$$
Similarly,
$$a_{n+1} = A_{n+1} + A_{n+2} + A_{n+3} + A_{n+4} + \cdots < A_{n+1} + A_{n+1} + A_{n+3} + A_{n+3} + A_{n+5} + A_{n+5} + \cdots = 2 | R_n | .$$
Thus,
$$a_{n+1} < 2 | R_n | < a_n .$$
\bye 