\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}
\def\dps{\displaystyle}
\newsymbol\nmid 232D
\tolerance=1600
\comment
\hsize=33pc
\vsize=42pc
\endcomment
\hsize=6.5in
\vsize=9in
\baselineskip=12pt
\lineskip=12pt
\centerline{\bf 2009 Missouri Collegiate Mathematics Competition}
\vskip 6pt
\centerline{\bf Session I}
\bigskip
1. For the parabola having equation $y = -x^2$ let $a<0$ and $b>0$ with $P : (a,-a^2)$
and $Q : (b,-b^2)$. Let $M$ be the midpoint of $PQ$ and let $R$ be the intersection of the
vertical line through $M$ with the parabola. Finally, let $l$ be the tangent line to the
parabola at $Q$. Prove that every vertical line segment with one end on $PQ$ and the
other end on $l$ is bisected by the line through $Q$ and $R$.
\bigskip
Solution.
\medskip
The equation of line $l$ is
$$y = -2bx + b^2 .$$
The equation of the line containing $P$ and $Q$ is
$$y = -(b+a) x + ab .$$
The equation of the line containing $Q$ and $R$ is
$$y = - \left( {a+3b \over 2} \right) x + \left( {ab+b^2 \over 2} \right) .$$
The $y$-coordinate of the midpoint of the vertical segment from $PQ$ to $l$ is the average
ordinate of the first two lines:
$$y_{\text{avg}} = {1 \over 2} ( -2bx + b^2 - (b+a)x + ab)$$
and the right side simplifies to the right side of the equation of the line through $Q$ and $R$.
\medskip
$\underline{\text{Remark}}$. This problem is a part of the method Archimedes
used in his discovery that the area of a segment of a parabola (in this problem, the area
between the parabola and line segment $PQ$) is equal to ${4 \over 3}$ of the area of the
triangle formed by $P$, $Q$, and the vertex of the segment of the parabola between $P$ and
$Q$ (in this problem, the point $R$). Note that the vertex of a segment of a parabola is not
necessarily the same as the vertex of the whole parabola.
\bigskip
2. Prove that for any $x$ in the half-open interval $(0, \pi/2
\rbrack$ one has
$$\left( {\sin x \over x} \right) ^3 > \cos x .$$
\bigskip
Solution.
\medskip
On $(0, \pi /2 \rbrack$,
$$\cases \sin x > x - {x^3 \over 6} &\\
\cos x < 1 - {x^2 \over 2} + {x^4 \over 24} ,& \endcases$$
so
$$\eqalign{ \left( {\sin x \over x} \right) ^3 > \cos x \ \ &\text{if}\ \
\left( 1 - {x^2 \over 6} \right) ^3 > 1 - {x^2 \over 2} + {x^4 \over 24} \cr
&\text{iff}\ \ {x^4 \over 12} - {x^6 \over 216} > {x^4 \over 24} \cr
&\text{iff}\ \ {x^4 \over 24} > {x^6 \over 216} \cr &\text{iff}\ \ 3
> x .\cr}$$
But $x \le \pi / 2 \approx 1.57 < 3$, so the desired result
follows.
\bigskip 3. Let $A$ be a set with $|A|=n$, and let $k$ be a
positive integer. Determine the number of subset sequences of the
form
$\dps S_1 \subseteq S_2 \subseteq \cdots \subseteq S_k \subseteq A$.
\bigskip
Solution.
\medskip
For any $a \in A$, either $a \not \in S_k$ or
there is the least $i$ for which $a \in S_i$ where $1 \le i \le k$.
Therefore, there are $k+1$ such choices for each $a$. We conclude
that there are $(k+1)^n$ ways to form sequence $\dps S_1 \subseteq
S_2 \subseteq \cdots \subseteq S_k \subseteq A$.
\bigskip
4. Find the value of the infinite
product
$$\left( {7 \over 9} \right) \cdot \left( {26 \over 28}
\right) \cdot \left( {63 \over 65} \right) \cdot \cdots = \lim_{n
\to \infty} \prod _{k=2}^n \left( {k^3 - 1 \over k^3 + 1} \right)
.$$
\vfill\eject
Solution.
\medskip
We rewrite the $n$th partial
product so as to reveal two sets of telescoping products:
$$\eqalign{
\prod_{k=2}^n {k^3 - 1 \over k^3 + 1} &= \prod_{k=2}^n \left( {k-1 \over k+1}
\right) \prod_{k=2}^n \left( {k^2 + k + 1 \over k^2 - k + 1} \right) \cr &=
\prod_{k=2}^n \left( {k-1 \over k+1} \right) \prod_{k=2}^n \left( {k^2 + k + 1
\over (k-1)^2 + (k-1) + 1} \right) \cr &= \prod_{k=2}^n \left( {(k-1)((k-1) +
1) \over k(k+1)} \right) \prod_{k=2}^n \left( {k^2 + k + 1 \over (k-1)^2 +
(k-1) + 1} \right) \cr &= {2 \over n(n+1)} \cdot {n^2 + n + 1 \over 3} \cr &=
{2 \over 3} \left( 1 + {1 \over n(n+1)} \right) .\cr}$$
Hence,
$$\prod_{k=2}^\infty {k^3 - 1 \over k^3 + 1} = {2 \over 3} \lim_{n \to \infty}
\left( 1 + {1 \over n(n+1)} \right) = {2 \over 3} .$$
\comment We first note
that
$$k^3 - 1 = (k-1)(k^2 + k + 1) \ \ \text{and}\ \ k^3 + 1 = (k+1) (k^2 - k + 1) .$$
Furthermore,
$$k^2 - k + 1 = (k-1)^2 + (k-1) + 1 .$$
Let us consider the partial product $P_n$ whose initial factor is the $k=2$ case and whose final
factor uses $k=n$. The linear factors telescope to $(1 \cdot 2)/(n(n+1))$, while the
quadratic factors telescope to $(n^2 + n + 1)/3$. So
$$P_n = \left( {2 \over 3} \right)
\left( {n^2 + n + 1 \over n(n+1)} \right)$$
and the limit as $n$ approaches infinity is $2/3$.
\endcomment
\medskip
$\underline{\text{Remark}}$. The problem was suggested by Nick Hobson.
\bigskip
5. Evaluate
$$\int\!\!\! \intop_S\!\!\! \int \min \{ x, y, z \} \, \text{d}V ,$$
where $S = \{ (x,y,z) \in \R^3 \ \vert \ 0 \le x \le 1, \ 0 \le y \le 1, \ 0 \le z \le 1 \}$.
\bigskip
Solution.
\medskip
Inside the square-based pyramid $P$
bounded by $z=0$, $x=1$, $y=1$, $z=y$, and $z=x$ either the inequality $z \le x \le y$ or
$z \le y \le x$ holds.
In either case $\min \{ x, y, z \} = z$ in this region, and
$$\int\!\!\! \intop_P\!\!\! \int \min \{ x, y, z \} \, \text{d}V = \int_0^1 \!\!\int_z^1 \!\!
\int_z^1 z \, \text{d}x \, \text{d}y \, \text{d}z = {1 \over 12} .$$
By symmetry, there are two more such pyramids, one where the
minimum coordinate is $x$ and another where the minimum coordinate is $y$. Thus,
$$\int\!\!\! \intop_S\!\!\! \int \min \{ x, y, z \} \, \text{d}V = 3 \left( {1 \over 12} \right) = {1 \over 4} .$$
Or, consider the
triangle-based pyramid in which $z \le y \le x$ (half of the one above), bounded by $z=0$, $x=1$, $z=y$,
and $y=x$. Integrating over this pyramid, we get
$$\int_0^1 \!\!\int_0^x \!\!\int_0^y z\, \text{d}z \, \text{d}y \, \text{d}x = {1 \over 24} .$$
There are six such pyramids, making the desired integral, as before, $1/4$.
\vfill\eject
\centerline{\bf 2009 Missouri Collegiate Mathematics Competition}
\vskip 6pt
\centerline{\bf Session II}
\bigskip
1. A piece of wire of length $x$ is cut into two pieces, one of which is formed into a
square and the other into a circle, such that the total area enclosed by the two figures is
a positive constant $A$. Find the ratio of the length of the edge of the square to the length
of the radius of the circle that makes the length of the wire a maximum. Similarly, find the
ratio that makes the length of the wire a minimum.
\bigskip
Solution. \medskip Let $s$ be the length of an edge of the square and $r$ be the length of the
radius of the circle. Then
$$x = 4s + 2\pi r\ \ \text{and}\ \ A = s^2 + \pi r^2 .$$
Let $t=s/r$, the ratio of the edge of the square to the radius of the circle. Calculating
$r$ and $s$ in terms of $t$ gives
$$r = \sqrt {A \over t^2 + \pi}\ \ \text{and}\ \ s = t \sqrt {A \over t^2 + \pi} .$$
Then
$$x = 4t \sqrt {A \over t^2 + \pi} + 2\pi \sqrt {A \over t^2 + \pi} = (4t+2\pi) \sqrt
{A \over t^2 + \pi} ,\ \ t \in \lbrack 0, \infty ) .$$
Differentiating $x$ with respect to $t$ gives
$$x' = {2 \sqrt A \over (t^2 + \pi)^{3/2}} (-\pi t + 2\pi ) ,$$
so $t=2$ is the critical value in the domain. $x' > 0$ for $t<2$ and $x' < 0$ for $t>2$.
At $t=0$, $x=2 \sqrt {\pi A}$; at $t=2$, $x=2 \sqrt {A(4+\pi)}$; and as $t \to \infty$,
$x \to 4 \sqrt A$. The maximum thus occurs at $t=2$, and the minimum occurs at $t=0$.
\bigskip
2. Determine the number of subsets $S$ of the set $\{ 1, 2, \ldots , n \}$ such that
$S$ contains no two consecutive integers. Express the answer in terms of the Fibonacci numbers
($F_1 = 1$, $F_2 = 1$, $F_n = F_{n-1} + F_{n-2}$ for $n \ge 3$) and prove your answer.
\bigskip
Solution.
\medskip
Let $K_n$ be the number of such subsets $S$. If $n \in S$, then $n-1 \not\in S$. The
rest of the elements of $S$ are from $\{ 1, 2, \ldots , n-2 \}$. Thus, there are $K_{n-2}$
such $S$. If $n \not\in S$, then $S$ consists of elements of $\{ 1, 2, \ldots , n-1 \}$ and
there are $K_{n-1}$ such subsets $S$. Thus, $K_n = K_{n-1} + K_{n-2}$ for $n \ge 3$, with
$K_1 = 2$ and $K_2 = 3$. Therefore, $K_n = F_{n+2}$ since $F_3 = 2$ and $F_4 = 3$.
\bigskip
3. Consider a piece of paper glued to the outside of the cylinder $x^2 + y^2 = 1$.
Suppose that we open a compass to a radius $r$ ($0 < r < 2$), put the stationary point of
the compass at the point $(1,0,0)$ on the cylinder, and draw a ``circle'' on the paper
(that is, we use the pencil end of the compass to draw a curve).
If we now remove the paper from the cylinder and draw a coordinate system with the
origin at the stationary compass point, the $Y$ axis in the same direction as the original
$z$ axis, and the $X$ axis oriented appropriately, we can now consider the ``circle''
as a plane figure. Find an equation for this figure in the $XY$-plane.
\bigskip
Solution. \medskip In the three-dimensional coordinate system, the curve will be the
intersection of the surfaces $(x-1)^2 + y^2 + z^2 = r^2$ and $x^2 + y^2 = 1$.
Simplifying, we get $2-2x+z^2 = r^2$.
We know that we can substitute $Y$ for $z$. To find $X$, we notice that (because the
radius of the cylinder is 1) $X$ is the angle $\theta$ from the positive $x$-axis to the
plane through the $z$-axis containing the point $(x,y,z)$. We can conclude that
$x= \cos (\theta) = \cos (X)$ so the desired equation is
$$2 - 2 \cos (X) + Y^2 = r^2 .$$
\medskip
$\underline{\text{Remark}}$. This problem was suggested by David Goldberg, Ann Arbor, MI.)
\bigskip
4. Determine
$$\lim_{n \to \infty} \sum_{k=1}^n \left( \sin \left( {\pi/2 \over k} \right) - \cos
\left( {\pi/2 \over k} \right) - \sin \left( {\pi/2 \over k+2} \right) + \cos \left(
{\pi/2 \over k+2} \right) \right) .$$
\bigskip
Solution. \medskip Let $S_n$ be the $n$th partial sum:
$$S_n = \sum_{k=1}^n \left( \sin \left( {\pi/2 \over k} \right) - \cos \left( {\pi/2 \over k}
\right) - \sin \left( {\pi/2 \over k+2} \right) + \cos \left( {\pi/2 \over k+2} \right)
\right) .$$
The first few partial sums are:
$$\eqalign{
S_1 &= 1 - \sin (\pi/6) + \cos (\pi/6) ;\cr
S_2 &= S_1 + \sin (\pi/4) - \cos (\pi/4) - \sin (\pi/8) + \cos (\pi/8) \cr
&= 1 - \sin (\pi/6) + \cos (\pi/6) - \sin (\pi/8) + \cos (\pi/8) ;\cr
S_3 &= S_2 + \sin (\pi/6) - \cos (\pi/6) - \sin (\pi/10) + \cos (\pi/10) \cr
&= 1 - \sin (\pi/8) + \cos (\pi/8) - \sin (\pi/10) + \cos (\pi/10); \cr
S_4 &= S_3 + \sin (\pi/8) - \cos (\pi/8) - \sin (\pi/12) + \cos (\pi/12) \cr
&= 1 - \sin(\pi/10) + \cos (\pi/10) - \sin (\pi/12) + \cos (\pi/12) .\cr}$$
By induction we have
$$S_n = 1 - \sin \left( {\pi/2 \over n+1} \right) - \sin \left( {\pi/2 \over n+2}
\right) + \cos \left( {\pi/2 \over n+1} \right) + \cos \left( {\pi/2 \over n+2} \right) ,$$
and
$$\lim_{n \to \infty} S_n = 1 - 0 - 0 + 1 + 1 = 3 .$$
\vfill\eject
5. Mersenne primes continue to make news. A number $M_p = 2^p - 1$ is a Mersenne prime if and
only if $p$ is prime and $2^p-1$ is also prime. Let the operator $DS$ denote ``form the sum of the
digits''; for example, $DS(5119) = 16$. Let the operator $DR$ denote ``execute $DS$ repeatedly
until a result in the interval $\lbrack 1,9 \rbrack$ is obtained''; for example,
$DR (5119) = DS^2 (5119) = DS (16) = 7$.
\medskip
\item{(a)} Prove the following lemma.
\medskip
$\underline{\text{Lemma}}$. If $A$ and $B$ are natural numbers, then
$$DR(AB) = DR(DR(A) \cdot DR(B)) .$$
\medskip
\item{(b)} Prove that for any Mersenne prime greater than 7, $DR(M_p) = 1 \text{ or } 4$.
(You may use the Lemma in part (a) without proving part (a)).
\bigskip
Solution.
\medskip
\item{(a)} Let
$$A = \sum_{k=0}^s a_k 10^k$$
be a natural number. Then
$$DS(A) = \sum_{k=0}^s a_k ,$$
so upon subtraction,
$$A - DS(A) = \sum_{k=0}^s a_k (10^k - 1) \equiv 0 \pmod 9 .$$
If we set $DS(A) = A'$, then $A' - DS(A') \equiv 0 \pmod 9$.
Combining this with the previous congruence gives $A - DS^2 (A) \equiv 0 \pmod 9$.
This process is continued until for some $n$, one has $DS^n (A) = DR (A)$ and
$$A \equiv DR (A) \pmod 9 .\eqno(*)$$
Similarly, for any other natural number $B$, $B \equiv DR (B) \pmod 9$, and multiplication of the
congruences gives
$$AB \equiv DR(A) \cdot DR(B) \pmod 9 .\eqno(**)$$
Application of ($*$) to ($**$) gives, finally,
$$DR (AB) = DR ( DR(A) \cdot DR(B) ) .\eqno(***)$$
This is an equality, rather than a congruence, since both sides lie in the interval $\lbrack 1,9
\rbrack$.
\medskip
\item{(b)} If $N$, a natural number, can be written in the form $N = 9a+b$, $1 \le b \le 8$, then eq.
($*$) shows that $DR(N)$ is of the form $9a'+b$, where $a'=0$. But whenever $N = 9a+b$, $b=0$, then from
eq. ($*$) and the definition of $DR(N)$, we always have $DR(N)=9$. Hence, the equality
$$DR(N-1) = DR(N) - 1$$
holds if and only if 9 does not divide $n-1$ (i.e., $9 \nmid (N-1)$).
Now consider a Mersenne prime, $M_p$; as $9 \nmid M_p$, then
$$DR(M_p) = DR(M_p + 1) - 1 . \eqno(****)$$
All primes $p$ larger than 3 are of the form $6k+1$ or $6k+5$.
The first case, together with eq. ($****$), yields
$$\eqalign{
DR(M_p) &= DR(2^{6k+1}) - 1 \cr
&= DR [ DR(64^k) \cdot DR(2) ] - 1 \ \ \ \ \ \ \ \ \text{from ($***$)} \cr
&= DR [ 1^k \cdot 2] - 1 \ \ \ \ \ \ \ \ \text{from ($***$), repeatedly} \cr
&= 1 .\cr}$$
For the second case ($p=6k+5$), we obtain similarly,
$$\eqalign{
DR(M_p) &= DR(2^{6k+5}) - 1 \cr
&= DR [ DR(64^k) \cdot DR(32)] - 1 \cr
&= DR[1^k \cdot 5] - 1 \cr
&= 4. \cr}$$
\bye