%Format: AMS TeX
\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 1996 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 area bounded by the 
normal line and the parabola 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 area bounded by the normal line and the parabola is
$$A = \int _q^p \left( p^2 - {1 \over 2p} (x - p) - x^2 
\right) dx = \int_q^p (p - x) \left( p + x + {1 \over 2p} \right) dx .$$
Using the generalized Leibniz rule to differentiate the integral with 
respect to $p$ yields
$$ {dA \over dp} = 0 - 0 + \int_q^p \left( 2p + {x \over 2p^2} \right) 
dx = 2p(p-q) + {p^2 - q^2 \over 4p^2} .$$
Setting this to $0$, factoring out $p-q$ and substituting
$-1/2p = p+q$ gives $p=1/2$ as the minimum. 
Thus,
$$P = \biggl( {1 \over 2}, {1 \over 4} \biggr) .$$
\bigskip
From the Putnam Exam, 1939, 14(i)
\smallskip
2. If
$$\eqalign{
&u = 1 + {x^3 \over 3!} + {x^6 \over 6!} + \cdots ,\cr
&v = {x \over 1!} + {x^4 \over 4!} + {x^7 \over 7!} + \cdots ,\cr
&w = {x^2 \over 2!} + {x^5 \over 5!} + {x^8 \over 8!} + \cdots ,\cr}$$
prove that
$$u^3 + v^3 + w^3 - 3uvw = 1.$$
\bigskip
Solution.
\smallskip
The power series for $u$, $v$, and $w$ converge for all $x$, and
$${du \over dx} = w,\ \ \ {dv \over dx} = u,\ \ \ {dw \over dx} = v,$$
as we see by differentiating them.  Letting
$$f = u^3 + v^3 + w^3 - 3uvw,$$
we have
$$\eqalign{
f' &= 3u^2 u' + 3v^2 v' + 3w^2 w' - 3uvw' - 3uv' w - 3u'vw\cr
&= 3u^2 w + 3v^2 u + 3w^2 v - 3uv^2 - 3u^2 w - 3vw^2 = 0 .\cr}$$
Thus $f = \text{constant}$.  But $f(0) = (u(0))^3 = 1$, so $f(x) = 1$ 
for all $x$.
\bigskip
From the All-Soviet Union Mathematics Competition, Moscow, 1965, 056
\smallskip
3. Each of the numbers $x_1, x_2, \ldots , x_n$ can be 1, 0, or -1.  
What is the minimum possible value of the sum of all products of pairs of 
these numbers?
\vfill\eject
Solution.
\smallskip
Let
$$S_n = \sum_{1 \le i < j \le n} x_i x_j = { \left( \sum_{1 \le i \le 
n} x_i \right) ^2 - \sum_{1 \le i \le n} x_i^2 \over 2} .$$
To minimize the last expression, we will consider two cases.

Case 1.  $n$ is even.  $S_n$ can be minimized by choosing 
half ($n/2$) of the $x_i$'s to be 1 and the other half ($n/2$) of the 
$x_i$'s to be -1.  The minimum $S_n$ is $-n/2$

Case 2.  $n$ is odd.  $S_n$ can be minimized by choosing $(n-1)/2$ of the
$x_i$'s to be 1 and $(n-1)/2$ of the $x_i$'s to be -1.  The value of 
the one left over has no effect on $S_n$.  The minimum $S_n$ is $-(n-1)/2$.
\bigskip
From the All-Soviet Union Mathematics Competition, Moscow, 1963, 033
\smallskip
4. A $6 \times 6$ board is tiled with $2 \times 1$
dominos.  Prove that the board can be cut into two parts by a straight
line that does not cut dominos.
\bigskip
Solution.
\smallskip
Suppose the $6 \times 6$ tiled board cannot be cut by a straight line 
without cutting a domino.  Thus for the 5 horizontal and 5 vertical lines, 
there are 10 dominos which are cut by the 10 lines, e.g. the domino cut 
by the second vertical line is denoted with a horizontal line segment 
and the region to the left of the vertical line is marked with an $A$ and 
the region to the right of the vertical line is marked with a $B$.
\vskip 14pc
But the $A$ area has an odd number of squares and thus the tiling must 
have another domino which is cut by the second vertical line.  Likewise, 
each of the 10 lines cuts 2 dominos, for a total of 20 dominos.  But this 
is a contradiction, since the tiling consists of 18 dominos.
\vfill\eject
From the 11th Canadian Mathematics Olympiad, 1979, 3
\smallskip 
5. Let $a, b, c, d, e$ be integers such that $1 \le a < b < c < d < e$.
Prove that
$${1 \over [a,b]} + {1 \over [b,c]} + {1 \over [c,d]} + {1 \over [d,e]}
\le {15 \over 16},$$
where $[m,n]$ denotes the least common multiple of $m$ and $n$ (e.g.
$[4,6] = 12$).
\bigskip
Solution.
\smallskip
Let $S$ denote the sum on the left of the proposed inequality.  Since $1 
\le a < \cdots < e$, we have
$$[a,b] \ge 2a,\ \ [b,c] \ge 2b,\ \ [c,d] \ge 2c,\ \ [d,e] \ge 2d ,$$
and $b \ge 2$, $c \ge 3$.  We consider two cases:

Case 1. $c=3$.  If $d=4$, then $[a,b] = 2$, $[b,c]=6$, $[c,d]=12$, and 
$[d,e] \ge 8$; hence
$$S \le {1 \over 2} + {1 \over 6} + {1 \over 12} + {1 \over 8} = {7 \over 
8} < {15 \over 16}.$$
If $d \ge 5$, then $[c,d] \ge 6$ and $[d,e] \ge 10$; hence
$$S \le {1 \over 2} + {1 \over 6} + {1 \over 6} + {1 \over 10} = {14 \over 
15} < {15 \over 16} .$$

Case 2. $c \ge 4$.  If $5 \le d \le 7$, then $[c,d] = 20, 28, 30, 35$, or 
$42$, except when $c=4$ and $d=6$.  In the exceptional case, we have
$$S \le {1 \over 2} + {1 \over 4} + {1 \over 12} + {1 \over 12} = {11 
\over 12} < {15 \over 16} ;$$
and otherwise
$$S \le {1 \over 2} + {1 \over 4} + {1 \over 20} + {1 \over 10} = {9 \over 
10} < {15 \over 16} .$$
Finally, if $d \ge 8$, we have
$$S \le {1 \over 2} + {1 \over 4} + {1 \over 8} + {1 \over 16} = {15 \over 
16} .$$
\vfill\eject
\centerline{\bf Session II}
From the Putnam Exam, 1939, 9 (i) and (ii)
\smallskip
1. Evaluate the definite integrals
\smallskip
(a) $$\int_1^3 {dx \over \sqrt {(x-1)(3-x)}} ,$$
\smallskip
(b) $$\int_1^\infty {dx \over e^{x+1} + e^{3-x}} .$$
\bigskip
Solution.
\smallskip
(a)  Since the integrand is not defined at either bound of integration, 
one should write
$$\eqalign{
&\int_1^3 {dx \over \sqrt {(x-1)(3-x)}} = \lim_{{\scriptstyle \epsilon \to 
0^+} \atop {\scriptstyle \delta \to 0^+}} \int_{1+\epsilon}^{3-\delta} {dx 
\over \sqrt {(x-1)(3-x)}} \cr
&= \lim_{{\scriptstyle \epsilon \to 0^+} \atop {\scriptstyle \delta \to 
0^+}} \int_{1+\epsilon}^{3-\delta} {dx \over \sqrt {1- (x-2)^2}} = 
\lim_{{\scriptstyle \epsilon \to 0^+} \atop {\scriptstyle \delta \to 0^+}} 
\arcsin (x-2) \bigg\vert _{1+\epsilon}^{3-\delta} \cr
&= \lim_{{\scriptstyle \epsilon \to 0^+} \atop {\scriptstyle \delta \to 
0^+}} [ \arcsin (1-\delta) - \arcsin (\epsilon - 1)] = {\pi \over 2} + {\pi 
\over 2} = \pi .\cr}$$
\smallskip
(b)  The difficulty here is with the infinite interval of integration.  
Let $y=x-1$; then
$$\eqalign{
\int {dx \over e^{x+1} + e^{3-x}} &= {1 \over e^2} \int {dx \over e^{x-1} 
+ e^{1-x}} = {1 \over e^2} \int {dy \over e^y + e^{-y}} \cr
&= {1 \over e^2} \int {e^y dy \over e^{2y} + 1} = {1 \over e^2} \arctan 
e^y + c .\cr}$$
Hence
$$\eqalign{
\int_1^\infty {dx \over e^{x+1} + e^{3-x}} &= \lim_{N \to \infty} 
\int_1^N {dx \over e^{x+1} + e^{3-x}} \cr
&= \lim_{N \to \infty} {1 \over e^2} [\arctan e^{N-1} - \arctan e^0 ]\cr
&= {1 \over e^2} \left( {\pi \over 2} - {\pi \over 4} \right) = {\pi \over 
4e^2} .\cr}$$
\bigskip
From the All-Soviet Union Mathematics Competition, Moscow, 1962, 024
\smallskip
2. Let $x, y, z$ be three different integers.  Prove that
$$(x-y)^5 + (y-z)^5 + (z-x)^5$$
is divisible by $5(x-y)(y-z)(z-x)$.
\bigskip
Solution.
\smallskip
$$\eqalign{
&(x-y)^5 + (y-z)^5 + (z-x)^5 \cr
&= (x-z+z-y)^5 + (y-z)^5 + (z-x)^5 \cr
&= (x-z)^5 + 5(x-z)^4 (z-y) + 10 (x-z)^3 (z-y)^2 + 10 (x-z)^2 (z-y)^3 \cr
&\ \ \ + 5(x-z) (z-y)^4 + (z-y)^5 + (y-z)^5 + (z-x)^5 \cr
&= 5(x-z)^4 (z-y) + 10(x-z)^3 (z-y)^2 + 10(x-z)^2 (z-y)^3 + 5(x-z) (z-y)^4 
\cr
&= 5 (x-z)(z-y) \left( (x-z)^3 + 2(x-z)^2 (z-y) + 2(x-z) (z-y)^2 + (z-y)^3 
\right) .\cr}$$
But,
$$\eqalign{
&(x-z)^3 + 2(x-z)^2 (z-y) + 2(x-z) (z-y)^2 + (z-y)^3 \cr
&= (x-y+y-z)^3 + 2(x-y+y-z)^2 (z-y) + 2(x-y+y-z) (z-y)^2 + (z-y)^3 \cr
&= (x-y)^3 + 3(x-y)^2 (y-z) + 3(x-y) (y-z)^2 + (y-z)^3 + 2(x-y)^2 (z-y) \cr
&\ + 4(x-y) (y-z) (z-y) + 2(y-z)^2 (z-y) + 2(x-y) (z-y)^2 + 2(y-z) (z-y)^2 
+ (z-y)^3 \cr
&= (x-y)^3 + 3(x-y)^2 (y-z) + 3(x-y) (y-z)^2 + 2(x-y)^2 (z-y) \cr
&\ \ \ \ + 4(x-y) (y-z) (z-y) + 2(x-y) (z-y)^2\cr}$$
has a factor of $x-y$.  Therefore, the result follows.
\bigskip
From Crux Mathematicorum, 1979, Practice Set 4-1
\smallskip
3. What is the probability of an odd number of sixes turning up in a 
random toss of $n$ fair dice?
\bigskip
Solution.
\smallskip
For $0 \le k \le n$, the probability of $k$ sixes turning up in a random 
toss of $n$ fair dice is
$${n \choose k} \left( {5 \over 6} \right) ^{n-k} \left( {1 \over 6} 
\right) ^k ;$$
hence, with $a=5/6$ and $b=1/6$, the required probability is
$$\eqalign{
P &= {n \choose 1} a^{n-1} b + {n \choose 3} a^{n-3} b^3 + {n \choose 5} 
a^{n-5} b^5 + \cdots \cr
&= \ \text{sum of the even-ranked terms in the expansion of }\ (a+b)^n \cr
&= {1 \over 2} \{ (a+b)^n - (a-b)^n \} \cr
&= {1 \over 2} \left\{ 1 - \left( {2 \over 3} \right) ^n \right\} .\cr}$$
\bigskip
From the Putnam Exam, 1938, 6
\smallskip
4. A swimmer stands at one corner of a square swimming pool and wishes to
reach the diagonally opposite corner.  If $w$ is the swimmer's walking 
speed and $s$ is the swimmer's swimming speed ($s<w$), find the 
swimmer's path for shortest time. [Consider two cases: (i) $w/s < \sqrt 
2$, and (ii) $w/s > \sqrt 2$.]
\bigskip
Solution.
\smallskip
Let the square pool be denoted by $ABCD$, with the swimmer initially at 
$A$ and desirous of reaching $C$.  The path of least time can evidently be 
described as follows.  The swimmer walks from $A$ to $E$ (a point on side 
$AB$), swims from $E$ to $F$ where $F$ is on $BC$, and then walks from $F$ 
to $C$.  Note that a path like $AGHC$ is time equivalent to a path of the 
type described with $F=C$.
\vskip 17pc
Let $\overline{AE} = x$, $\overline{EF} = y$, $\overline{FC} = z$.  Then 
the time $T$ is given by $T = (x+z)/w + (y/s)$.  If the sum $x+z$ is 
fixed, then the sum $y \sin \alpha + y \cos \alpha$ is also fixed, and $y$ 
is minimal when $(\sin \alpha + \cos \alpha )$ is maximal.  This maximum 
is attained for $\alpha = 45^\circ$.

Thus for a minimal time path, $x=z$ and $y = \sqrt 2 (l - x)$, where $l$ 
is the length of a side of the pool.  Accordingly, we have to minimize $T 
= (2x/w) + \sqrt 2 (l-x)/s$ for $0 \le x \le l$.

But $T$ is a linear function of $x$, so its maximum occurs at an endpoint 
of the interval.  If $x=0$, $T=\sqrt {2l}/s$, and if $x=l$, $T=2l/w$.

If $\sqrt {2l}/s < 2l/w$ then $w/s < \sqrt 2$, and conversely.  Hence, if 
$w/s < \sqrt 2$ the minimal path is unique and the swimmer should swim 
diagonally across the pool from $A$ to $C$.  If $w/s > \sqrt 2$, the 
swimmer should walk from $A$ to $B$ to $C$.  Finally, if $w/s = \sqrt 
2$, $T$ is independent of $x$ and there are infinitely many minimizing 
paths, in fact any path $AEFC$ for which $\alpha = 45^\circ$.
\vfill\eject
From the International Mathematical Olympiad, 1977, 2
\smallskip
5. In a finite sequence of real numbers, the sum of any seven successive
terms is negative and the sum of any eleven successive terms is positive.
Determine the maximum number of terms in the sequence.
\bigskip
Solution.
\smallskip
Denote by $S_n$ a sequence of $n$ terms having the desired property.  We 
shall prove that there is no $S_{17}$.  Then we shall construct an 
$S_{16}$ which automatically furnishes also $S_n$ for $n<16$.  This will 
demonstrate that 16 is the desired maximum number of terms.

We denote the terms of $S_{17}$ by $a_1$, $a_2$, $\ldots$, $a_{17}$ and 
write all sets of seven consecutive terms in rows of the table below:
$$\matrix
&a_1&a_2&a_3&a_4&a_5&a_6&a_7\\
&a_2&a_3&a_4&a_5&a_6&a_7&a_8\\
&a_3&a_4&a_5&a_6&a_7&a_8&a_9\\
&.&.&.&.&.&.&.\\
&.&.&.&.&.&.&.\\
&a_{11}&a_{12}&a_{13}&a_{14}&a_{15}&a_{16}&a_{17} \endmatrix .$$
We note that the columns in this table contain all sets of eleven 
consecutive terms of $S_{17}$.  Now we add all entries of the table first 
by adding all entries in each row, then by adding the row sums.  By 
hypothesis, each row sum is negative, hence the total is also negative.  
Then we add all entries of the table by adding the entries in each column 
and then adding the column sums.  By hypothesis each column sum is 
positive, hence the total is positive, which contradicts what we just 
found by adding the rows.  We conclude that there is no $S_{17}$.

An example of $S_{16}$ is the sequence
$$5,5,-13,5,5,5,-13,5,5,-13,5,5,5,-13,5,5,$$
and any $n$ consecutive terms of $S_{16}$ lead to a sequence $S_n$ for $11 
\le n \le 16$.  Thus to obtain an $S_{14}$, just pick any 14 consecutive 
terms of $S_{16}$.

We shall now show how the above $S_{16}$ can be found by a method other 
than guessing.

Assume we can find a sequence $S_{16}$ that reads the same from left to 
right as from right to left, and that the sum of any seven consecutive 
terms is -1 and the sum of any eleven consecutive terms is 1.  Then
$$\eqalign{
&a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7 = -1\cr
&a_2 + a_3 + a_4 + a_5 + a_6 + a_7 + a_8 = -1\cr
&a_3 + a_4 + a_5 + a_6 + a_7 + a_8 + a_8 = -1\cr
&a_4 + a_5 + a_6 + a_7 + a_8 + a_8 + a_7 = -1\cr
&a_5 + a_6 + a_7 + a_8 + a_8 + a_7 + a_6 = -1 .\cr}$$
Subtracting the second equation from the first, then the third from the 
second, etc., we obtain
$$a_1 = a_8,\ \ a_2 = a_8,\ \ a_3 = a_7,\ \ a_4 = a_6 .$$
Now writing the sum of eleven consecutive terms
$$\eqalign{
&a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7 + a_8 + a_8 + a_7 + a_6 = 1\cr
&a_2 + a_3 + a_4 + a_5 + a_6 + a_7 + a_8 + a_8 + a_7 + a_6 + a_5 = 1\cr
&a_3 + a_4 + a_5 + a_6 + a_7 + a_8 + a_8 + a_7 + a_6 + a_5 + a_4 = 1\cr}$$
and subtracting the second equation from the first and the third from the 
second, we obtain
$$a_1 = a_5\ \ \text{and}\ \ a_2 = a_4 .$$
It follows that $S_{16}$ has the form
$$a_1, a_1, a_3, a_1, a_1, a_1, a_3, a_1, a_1, a_3, a_1, a_1, a_1, a_3, 
a_1, a_1,$$
where the sum of any seven consecutive terms is $5a_1 + 2a_3 = -1$ and the 
sum of any eleven consecutive terms is $8a_1 + 3a_3 = 1$.  The solution of 
this pair of equations is $a_1 = 5$, $a_3 = -13$ and leads to the $S_{16}$ 
above.
\bye
