[Solutions] William Lowell Putnam Mathematical Competition 2004

1. Basketball star Shanille O'Keal's team statistician keeps track of the number, $S(N),$ of successful free throws she has made in her first $N$ attempts of the season. Early in the season, $S(N)$ was less than 80% of $N,$ but by the end of the season, $S(N)$ was more than 80% of $N.$ Was there necessarily a moment in between when $S(N)$ was exactly 80% of $N$?
2. For $i=1,2,$ let $T_i$ be a triangle with side length $a_i,b_i,c_i,$ and area $A_i.$ Suppose that $a_1\le a_2, b_1\le b_2, c_1\le c_2,$ and that $T_2$ is an acute triangle. Does it follow that $A_1\le A_2$?
3. Define a sequence $\{u_n\}_{n=0}^{\infty}$ by $u_0=u_1=u_2=1,$ and thereafter by the condition that $$\det\begin{vmatrix} u_n & u_{n+1} \\ u_{n+2} & u_{n+3} \end{vmatrix}=n!$$ for all $n\ge 0.$ Show that $u_n$ is an integer for all $n.$ (By convention, $0!=1$.)
4. Show that for any positive integer $n$ there is an integer $N$ such that the product $x_1x_2\cdots x_n$ can be expressed identically in the form \[x_1x_2\cdots x_n=\sum_{i=1}^Nc_i(a_{i1}x_1+a_{i2}x_2+\cdots +a_{in}x_n)^n\] where the $c_i$ are rational numbers and each $a_{ij}$ is one of the numbers, $-1,0,1.$
5. An $m\times n$ checkerboard is colored randomly: each square is independently assigned red or black with probability $\frac12.$ we say that two squares, $p$ and $q$, are in the same connected monochromatic region if there is a sequence of squares, all of the same color, starting at $p$ and ending at $q,$ in which successive squares in the sequence share a common side. Show that the expected number of connected monochromatic regions is greater than $\frac{mn}8.$
6. Suppose that $f(x,y)$ is a continuous real-valued function on the unit square $0\le x\le1,0\le y\le1.$ Show that $$\int_0^1\left(\int_0^1f(x,y)dx\right)^2dy + \int_0^1\left(\int_0^1f(x,y)dy\right)^2dx$$ $$\le\left(\int_0^1\int_0^1f(x,y)dxdy\right)^2 + \int_0^1\int_0^1\left[f(x,y)\right]^2dxdy.$$
7. Let $P(x)=c_nx^n+c_{n-1}x^{n-1}+\cdots+c_0$ be a polynomial with integer coefficients. Suppose that $r$ is a rational number such that $P(r)=0$. Show that the $n$ numbers $c_nr$, $c_nr^2+c_{n-1}r$, $c_nr^3+c_{n-1}r^2+c_{n-1}r$, $\dots$, $c_nr^n+c_{n-1}r^{n-1}+\cdots+c_1r$ are all integers.
8. Let $m$ and $n$ be positive integers. Show that $$\frac{(m+n)!}{(m+n)^{m+n}} < \frac{m!}{m^m}\cdot\frac{n!}{n^n}.$$
9. Determine all real numbers $a>0$ for which there exists a nonnegative continuous function $f(x)$ defined on $[0,a]$ with the property that the region $R=\{(x,y): 0\le x\le a, 0\le y\le f(x)\}$ has perimeter $k$ units and area $k$ square units for some real number $k$. 
10. Let $n$ be a positive integer, $n \ge 2$, and put $\theta=\frac{2\pi}{n}$. Define points $P_k=(k,0)$ in the xy-plane, for $k=1,2,\dots,n$. Let $R_k$ be the map that rotates the plane counterclockwise by the angle $\theta$ about the point $P_k$. Let $R$ denote the map obtained by applying in order, $R_1$, then $R_2$, ..., then $R_n$. For an arbitrary point $(x,y)$, find and simplify the coordinates of $R(x,y)$.
11. Evaluate $$\lim_{x\to 1^-}\prod_{n=0}^{\infty}\left(\frac{1+x^{n+1}}{1+x^n}\right)^{x^n}.$$
12. Let $A$ be a nonempty set of positive integers, and let $N(x)$ denote the number of elements of $A$ not exceeding $x$. Let $B$ denote the set of positive integers $b$ that can be written in the form $b=a-a^{\prime}$ with $a\in A$ and $a^{\prime}\in A$. Let $b_1<b_2<\cdots$ be the members of $B$, listed in increasing order. Show that if the sequence $b_{i+1}-b_i$ is unbounded, then $$\lim_{x\to \infty}\frac{N(x)}{x}=0.$$

[DOWNLOAD SOLUTIONS ##download##]