\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 2004 Missouri 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 $x$-axis at a point, say $Q$.  Let $O=(0,0)$ and form the triangle $OPQ$.  Let $OQ$ be the base of this triangle.  Find the minimum  ratio of the length of the base of $\triangle OPQ$ to its height.
\bigskip
Solution.
\medskip
Let $P = (p,p^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) ,\ p \ne 0.$$
The point $Q$ lies on the normal line and has a $y$-coordinate of $0$.  Therefore, the $x$-coordinate of $Q$ is $p+2p^3$.  Hence, the length of the base of $\triangle OPQ$ is $\vert p + 2p^3 \vert$ and the height is $p^2$.  Therefore, the ratio $R(p)$ of the length of the base of this triangle to its height is
$$R(p) = {\vert p+2p^3 \vert \over p^2} = \bigg\vert 2p + {1 \over p} \bigg\vert .$$
Critical points occur where
$$R' (p) = \cases 
2 - {1 \over p^2},&\text{for $p>0$}\\
-2 + {1 \over p^2},&\text{for $p<0$.}
\endcases$$
is zero; these occur at
$$p = \pm {1 \over \sqrt 2} .$$
Thus, the minimum ratio is
$$R_{\text{min}} (p) = \bigg\vert \pm {2 \over \sqrt 2} \pm \sqrt 2 \bigg\vert = 2\sqrt 2 .$$
That this is a relative minimum of $R(p)$ follows because
$$R'' (p) = \cases 
{2 \over p^3},&\text{for $p>0$}\\
{-2 \over p^3},&\text{for $p<0$}
\endcases$$
is positive for any $p \ne 0$.
\comment
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 area under the parabola between $P$ and $Q$ is a minimum.
\bigskip
Solution.
\medskip
Let $p>0$, $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} .$$
Solving for $q$, we obtain
$$q = -p - {1 \over 2p} .$$
Now the area under the parabola between $P$ and $Q$ is
$$\eqalign{
A &= \int_q^p x^2 \, dx = {x^3 \over 3} \bigg\vert _q^p \cr
&= {p^3 \over 3} - {q^3 \over 3} = {1 \over 3} (p-q) (p^2 + pq + q^2) \cr
&= {1 \over 3} \biggl( 2p + {1 \over 2p} \biggr) \cdot \biggl( p^2 + p^2 + 1 + {1 \over 4p^2} + p \biggl( -p - {1 \over 2p} \biggr) \biggr) \cr
&= {2 \over 3} p^3 + {1 \over 2} p + {1 \over 4} p^{-1} + {1 \over 24} p^{-3} . \cr}$$
Differentiating this quantity with respect to $p$, we obtain
$${dA \over dp} = 2p^2 + {1 \over 2} - {1 \over 4} p^{-2} - {1 \over 8} p^{-4}
= {1 \over 8p^4} ( 16p^6 + 4p^4 - 2p^2 - 1) .$$
Setting this quantity equal to 0 and solving for $p$ (with the aid of a calculator), we have
$$p = 0.644004 \ldots$$
Therefore, the coordinates of $P$ so that the area under the normal line between $P$ and $Q$ is a minimum are $( 0.644004 \ldots , 0.414741 \ldots )$.
\endcomment
\vfill\eject
2.  The numbers $\pm 1, \pm 2, \ldots \pm 2004$ are written on a blackboard.  You decide to pick two numbers $x$ and $y$ at random, erase them, and write their product, $xy$, on the board.  You continue this process until only one number remains.  Prove that the last number is positive.
\bigskip
Solution.
\medskip
\comment
Note that if the two numbers picked and erased are both positive or both negative, their product and the number replacing the two numbers is positive.  Also, if the two numbers picked and erased are of opposite sign, their product is negative.  Thus, the number of negative numbers on the blackboard at any one time is always even.  Therefore, the last number on the board is positive.
\endcomment
Let
$$P = (1 \cdot 2 \cdot 3 \cdots 2004) \cdot (-1 \cdot -2 \cdot -3 \cdots -2004) .$$
$P$ is obviously positive.  If two numbrs $x$, $y$ are removed from the list and the product $xy$ is added to the list, then the product of the elements of the new list is still $P$.  This could continue until only one element is left, and this element must necessarily be $P$ which is positive.
\bigskip
From {\it Quantum,} ``Problems Teach Us How to Think,'' 11.3 (Jan/Feb 2001), p. 43 by V. Proizvolov.
\medskip
3.  A chess position possesses the following property:  On every vertical column and on every horizontal row, there is an odd number of pieces.  Prove that there is an even number of pieces on black squares.
\bigskip
Solution.
\medskip
\comment
Number the vertical columns and horizontal rows of the chess board and put the letter $A$ in the black squares of the vertical rows that received an odd ``vertical'' number.  Put the letter $B$ in all the other black squares.  Similarly, put the letter $C$ in the white squares of the horizontal rows that received an odd ``horizontal'' number.
$$\epsfxsize=15pc \epsfbox{board2.eps}$$
Let the number of pieces on $A$ squares be $a$, on $B$ squares be $b$, and on $C$ squares be $c$.  The statement of the problem implies that both $a+c$ and $b+c$ are even.  Therefore, $a+b$ is also even -- that is, there is an even number of pieces on the black squares.
\endcomment
A chessboard has a black square in the lower left corner.  Let $1 \le i \le 8$.  Let $c_i$ denote the number of pieces in column $i$ and $r_i$ denote the number of pieces in row $i$.  By the statement of the problem, every $c_i$ and $r_i$ is odd.  The quantity
$$c_2 + c_4 + c_6 + c_8$$
is the number of pieces in columns 2, 4, 6, and 8.  The quantity
$$r_1 + r_3 + r_5 + r_7$$
is the number of pieces in rows 1, 3, 5, and 7.  Consider the sum
$$S = c_2 + c_4 + c_6 + c_8 + r_1 + r_3 + r_5 + r_7 .$$
\comment
of these 8 odd numbers is even and counts all the pieces on black squares plus twice the number of pieces on the white squares in an odd row and even column.  Therefore, the number of pieces on black squares is even.
\endcomment
Each even-indexed $c_k$ tallies all the black pieces in that column and all white pieces in an odd row and that even column.  Each odd-indexed $r_k$ tallies all the black pieces in that row and all white pieces in an even column and that odd row.  All the black pieces on the board are tallied, and none is counted twice; let their number be $S_1$.  The white pieces tallied by the $c_k$'s are the same as the white pieces tallied by the $r_k$'s; let their number be $S_2$.  It follows that $S = S_1 + 2S_2$.  Since $S$ is even because it is the sum of 8 odd integers and $2S_2$ is even, then $S_1$ (the number of black pieces) must also be even.
\bigskip
4.  At a point $P$ on the curve
$$\biggl( {x \over a} \biggr) ^{2/3} + \biggl( {y \over b} \biggr) ^{2/3} = 1 ,$$
the tangent to the curve meets the $x$-axis at $(h,0)$ and the $y$-axis at $(0,k)$.  As $P$ moves on the given curve, find the locus of points $Q(h,k)$.
\bigskip
Solution.
\medskip
The algebraic work is easier if the equation of the curve is written in a parametric form
$$x = a \cos ^3 \theta \quad \text{and} \quad y = b \sin ^3 \theta .$$
Then
$${dx \over d\theta} = 3a \cos ^2 \theta (-\sin \theta ), \ \  {dy \over d\theta} = 3b \sin ^2 \theta (\cos \theta) , \ \ \text{and} \ \ {dy \over dx} = -{b \over a} \tan \theta .$$
The equation of the tangent line at any point $\theta$ is given by
$$y - b \sin ^3 \theta = -{b \over a} \tan \theta (x-a\cos ^3 \theta ) .$$
Then $h$ and $k$, the $x$- and $y$- intercepts of this line, are
$$h = a \cos \theta \quad \text{and} \quad k = b \sin \theta .$$
This shows that the locus of the point $Q(h,k)$ is an ellipse given by
$${x^2 \over a^2} + {y^2 \over b^2} = 1 .$$
\bigskip
5.  Let $a$, $b$, $c$, and $d$ be integers.  Suppose that each of the three quadratics $ax^2 + bx +c$, $ax^2 + bx + (c+d)$, and $ax^2 + bx + (c+2d)$ factors over the integers, i.e. has rational roots.  Let $S = ad>0$.  Show that $S$ represents the area of some Pythagorean triangle (integer-sided right triangle).
\bigskip
Solution.
\medskip
If $ax^2 + bx + c$ is factorable over the integers, then from the quadratic formula, $b^2 - 4ac$ is a perfect square.  Similarly, $b^2 - 4a(c+d)$ and $b^2 -4a(c+2d)$ are also perfect squares.  Assume $ad > 0$.  Then there are positive integers $M>N>P$ such that
$$\cases
M^2 = b^2 - 4ac ,&\text{ }\\
N^2 = b^2 - 4a(c+d) ,&\text{ }\\
P^2 = b^2 - 4a(c+2d) . &\text{ }
\endcases $$
Hence, $M^2 - N^2 = N^2 - P^2 = 4ad$ and this implies that $M$, $N$, and $P$ are either all even or all odd, and that $M^2 + P^2 = 2N^2$.  This last equation can be rewritten as
$$\biggl( {M-P \over 2} \biggr) ^2 + \biggl( {M+P \over 2} \biggr) ^2 = N^2 .$$
$(M-P)/2$ and $(M+P)/2$ are positive integers, so
$$\biggl( {M-P \over 2}, {M+P \over 2}, N \biggr)$$
is a Pythagorean triple, and thus the sides of a Pythagorean triangle whose area is
$$A = {1 \over 2} \cdot {M-P \over 2} \cdot {M+P \over 2} = {M^2 - P^2 \over 8} = {8ad \over 8} = ad .$$
\vfill\eject
\centerline{\bf 2004 Missouri Collegiate Mathematics Competition}
\vskip 6pt
\centerline{\bf Session II}
\bigskip
From Problem 1.5.2, {\it Berkeley Problems in Mathematics}, Springer, 1998, QA43.S695.  
\medskip
1.  Suppose $f$ is a continuous real-valued function on the interval $[0,1]$.  Show that
$$\int _0^1 x^2 f(x) \, dx = {1 \over 3} f( \xi )$$
for some $\xi \in [0,1]$.
\bigskip
Solution.
\medskip
Because $f$ is continuous, it attains its minimum and maximum at points $a$ and $b$, both in $[0,1]$, giving
$$f(a)\int_0^1 x^2dx \le \int_0^1x^2f(x) \, dx \le f(b)\int_0^1x^2 \, dx$$
or
$$f(a) \le 3\int_0^1 x^2f(x) \, dx \le f(b) .$$
Thus, the Intermediate Value Theorem guarantees a point $\xi \in [0,1]$ such that
$$f(\xi) = 3\int_0^1x^2f(x) \, dx .$$
\bigskip
From {\it Crux Mathematicorum}, Problem 2384, November, 1998.  Proposed by Paul Bracken, CRM, Universit\'{e} de Montr\'{e}al, Qu\'{e}bec.  Solution by Michel Bataille, Rouen, France.
\medskip
2.  Prove that $2(3n-1)^n \ge (3n+1)^n$ for all nonnegative integers $n$.
\bigskip
Solution.
\medskip
The inequality is obvious for $n=0$, so we may assume $n \ge 1$.  We have to prove
$$\biggl( {3n-1 \over 3n+1} \biggr) ^n \ge {1 \over 2} ,\eqno(1)$$
or, equivalently,
$$n \ln {3n-1 \over 3n+1} \ge \ln {1 \over 2} .\eqno(2)$$

To this aim, we introduce the function
$$f(x) = x \ln {3x-1 \over 3x+1}$$
defined on $[1, \infty )$.  We compute
$$f' (x) = \ln {3x-1 \over 3x+1} + {6x \over 9x^2 - 1} \quad \text{and} \quad f'' (x) = {-12 \over (9x^2 - 1)^2} .$$
Since $f'' (x) < 0$, $f'(x)$ is strictly decreasing on $[1, \infty )$.  Moreover,
$$\lim _{x \to \infty} f'(x) = 0 ,$$
so $f'(x)>0$ for all $x \in [1, \infty )$.  Hence $f$ is increasing on $[1, \infty )$ and, since $f(1) = \ln (1/2)$, the inequality (2) follows.
\bigskip
Comment.
\medskip
A natural tool for proving inequality (1) might have been Bernoulli's Inequality.  However, this Inequality does not provide sharp enough lower bounds and is ineffective in the present problem.
\bigskip
3.  Equations of two ellipses $E_1$ and $E_2$ are
$${x^2 \over a^2} + {y^2 \over b^2} - {2x \over c} = 0 \text{   and   } {x^2 \over b^2} + {y^2 \over a^2} + {2x \over c} = 0 ,$$
respectively.  $AB$ is a common tangent, meeting $E_1$ at $A$ and $E_2$ at $B$.  Prove that when $A$ and $B$ are joined to the origin $O$, angle $AOB$ is a right angle.
\bigskip
Solution.
\medskip
Since
$${x^2 \over a^2} - {2x \over c} + {y^2 \over b^2} = 0 ,$$
we have, by completing the square and some algebraic manipulations, that
$$\eqalign{
&{x^2 - {2a^2 \over c} x + {a^4 \over c^2} \over a^2} + {y^2 \over b^2} = {a^2 \over c^2} \cr
&{\biggl( x - {a^2 \over c} \biggr)^2 \over a^2} + {y^2 \over b^2} = {a^2 \over c^2} \cr
&{\biggl( x - {a^2 \over c} \biggr) ^2 \over {a^4 \over c^2}} + {y^2 \over {a^2 b^2 \over c^2}} = 1 .\cr}$$
Similarly, since
$${x^2 \over b^2} + {2x \over c} + {y^2 \over a^2} = 0 ,$$
it follows that
$${\biggl( x - {b^2 \over c} \biggr) ^2 \over {b^4 \over c^2}} + {y^2 \over {a^2 b^2 \over c^2}} = 1 .$$
Graphing ellipses $E_1$ and $E_2$ we have the following figure.
$$\epsfxsize=13pc \epsfbox{ellipse.eps}$$
and the common tangents are horizontal lines.  Thus,
$$A = \biggl( {a^2 \over c} , {ab \over c} \biggr) \quad \text{and} \quad B = \biggl( -{b^2 \over c} , {ab \over c} \biggr) .$$
Finally, the slopes of $OA$ and $OB$ are
$${ab \over a^2} = {b \over a} \quad \text{and} \quad {ba \over -b^2} = -{a \over b} ,$$
respectively.  Therefore $OA \perp OB$ so angle $AOB$ is a right angle.
\bigskip
From the Ninth Irish Mathematical Olympiad (1996).
\medskip
4.  For each positive integer $n$, let $s(n)$ denote the sum of the digits of $n$ (when $n$ is written in base 10).  Prove that for every positive integer $n$
$$s(2n) \le 2s(n) \le 10 s(2n) .$$
\bigskip
Solution.
\medskip
The strict inequality $s(2n) < 10 s(2n)$ is patently obvious.  Now let $5, 6, 7, 8, 9$ be designated ``big digits.''  If $I$ is a big digit in the integer $n$, then it contributes $2s(I) = 2I$ to the quantity $2s(n)$.  But
$$2I = 1 \cdot 10^1 + (2I-10) \cdot 10^0 ,$$
so $s(2I)$ contributes
$$1 + (2I-10) = 2I-9$$
to the quantity $s(2n)$.  Hence, if $n$ contains $L$ big digits, we have
$$s(2n) = 2s(n) - 9L ,$$
that is, $s(2n) \le 2s(n)$.  Finally,
$$s(n) \ge \text{ sum of its big digits } \ge 5L ,$$
so
$$20 s(n) \ge 2s(n) + 90 L ,$$
or
$$20s(n) - 90L = 10 s(2n) \ge 2s(n) ,$$
as desired.
\comment
Let $n \in \N$ and 
$$n = \sum_{i=0}^k d_i 10^i \quad (\text{decimal expansion}) .$$
We need the help of two lemmas to prove our result.  Here, $L(n)$ will denote the number of $d_i$ such that $d_i \ge 5$. 
\medskip
$\underline{\text{Lemma 1}}$.  
$$s \biggl( 2 \sum_{i=0}^k d_i \cdot 10^i \biggr) = \sum_{i=0}^k s(2d_i) .$$
\medskip
$\underline{\text{Proof}}$.
$$\eqalign{
\sum_{i=0}^k s(2d_i) &= \sum_{i=0}^k \biggl( \bigg[ {2 d_i \over 10} \bigg] + (2d_i \bmod 10 ) \biggr) \cr
&= \bigg[ {2d_n \over 10} \bigg] + \sum_{i=0}^{k-1} \biggl( (2d_{i+1} \bmod 10 ) + \bigg[ {2d_i \over 10} \bigg] \biggr) \cr
& \quad + (2d_0 \bmod 10 ) \cr
&= s \biggl( 2 \cdot \sum_{i=0}^k d_i \cdot 10^i \biggr) .\cr}$$
\medskip
$\underline{\text{Lemma 2}}$.  
$$s(2n) = 2 s(n) - 9 L(n) .$$
Using Lemma 1 and the fact that for any decimal digit $d$
$$s(2d) = 2d - 9 \bigg[ {2d \over 10} \bigg] ,$$
it follows that
$$\eqalign{
s(2n) &= s \biggl( 2 \sum_{i=0}^k d_i \cdot 10^i \biggr) = \sum_{i=0}^k s(2d_i) \cr
&= \sum_{i=0}^k \biggl( 2d_i - 9 \bigg[ {2 d_i \over 10} \bigg] \biggr) \cr
&= 2 \sum_{i=0}^k d_i - 9 \sum_{i=0}^k \bigg[ {d_i \over 5} \bigg] \cr
&= 2s(n) - 9L(n) .\cr}$$
\medskip
From Lemma 2 it follows that
$$s(2n) \le 2s(n) .$$
This was one of the inequalities we wanted to prove.  In addition,
$$s(n) = \sum_{d_i \le 4} d_i + \sum_{d_i \ge 5} d_i \ge \sum_{d_i \ge 5} d_i \ge 5 \sum_{d_i \ge 5} 1 = 5 L(n) .$$
Therefore, by Lemma 2 and the above inequality,
$$s(2n) - L(n) = 2s(n) - 9L(n) - L(n) = 2s(n) - 10 L(n) \ge 0$$
so
$$s(2n) \ge L(n) .$$
Again by Lemma 2 and the above inequaltiy
$$2s(n) = s(2n) + 9L(n) \le s(2n) + 9L(n) \le s(2n) + 9s(2n) = 10s(2n) .$$
This was the other inequality we wanted to prove.
\endcomment
\bigskip
5.  The Fibonacci numbers are defined by $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$, if $n \ge 2$.  Use the Fibonacci numbers to express the number $K_n$ of $n$-tuples $(x_1, x_2, \ldots , x_n)$ of 0's, 1's, and 2's such that 0 is never followed by 1.
\bigskip
Solution.
\medskip
$K_1 = 3 = F_4$ and $K_2 = 8 = F_6$.  We shall prove $K_n = F_{2n+2}$ by induction.
Assume $K_p = F_{2p+2}$ for $1 \le p \le m$.  We are to show $K_{m+1} = F_{2(m+1)+2}$.

If a sequence of length $m+1$ starts with $1$ or $2$ then there are $K_m$ subsequences of length $m$ are available to follow either of them.

However, for a sequence starting with $0$, the remaining subsequences of length $m$ can only start with $0$ or $2$.  Again, after the $2$ there are $K_{m-1}$ subsequences available.  And after $0$ only sequences sarting with either $0$ or $2$ are available.   For the last one number of the sequence, after $0$ it can only be either $0$ or $2$ and after $2$ it has $K_1$ choices.  Therefore,
$$\eqalign{
K_{m+1} & = K_m+K_m+K_{m-1}+K_{m-2}+\cdots +K_2+K_1+1+1 \cr
& = F_{2m+2}+F_{2m+2}+F_{2(m-1)+2}+F_{2(m-2)+2}+\cdots +F_6+F_4+F_2+F_1 \cr
& = F_{2m+2}+F_{2m+2}+F_{2m}+F_{2m-2}+\cdots +F_6+F_4+F_3 \cr
& = F_{2m+2}+F_{2m+2}+F_{2m}+F_{2m-2}+\cdots +F_6+F_5 \cr
& = F_{2m+2}+F_{2m+2}+F_{2m}+F_{2m-2}+\cdots +F_7 \cr
& \cdots \cr
& = F_{2m+2}+F_{2m+2}+F_{2m}+F_{2m-1} \cr
& = F_{2m+2}+F_{2m+2}+F_{2m+1} \cr
& = F_{2m+2}+F_{2m+3} \cr
& = F_{2m+4} \cr
& = F_{2(m+1)+2} . \cr}$$
And this completes the induction.
\bye 