%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 \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