Putnam exam 2004

Questions to the 65rd annual Putnam exam:
Source: http://www.math.niu.edu/~rusin/problems-math/

A-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 ?

A-2.

For i = 1,2  let  T_i  be a triangle with side lengths  a_i, b_i, c_i,
and area  A_i.  Suppose that  a_1 <= a_2,  b_1 <= b_2,  c_1 <= c_2, 
and that  T_2  is an acute triangle. Does it follow that  A_1 <= A_2 ?

A-3.

Define a sequence { u_n }  by  u_0 = u_1 = u_2 = 1, and thereafter by the
condition that
        (  u_n    u_{n+1} )
     det(                 )  = n!
        ( u_{n+2} u_{n+3} )

for all n >= 0. Show that  u_n  is an integer for all  n.  
(By convention, 0! = 1.)

A-4.

Show that for any positive integer  n  there is an integer  N  such that
the product  x_1 x_2 ... x_n  can be expressed identically in the form

   x_1 x_2 ... x_n = 
         \sum_{i=1}^N  c_i ( a_{i1} x_1 + a_{i2} x_2 + ... + a_{in} x_n )^n

where the  c_i  are rational numbers and each  a_{ij}  is one of the
numbers,  -1, 0, 1 .

A-5.

An  m x n  checkerboard is colored randomly: each square is independently
assigned red or black with probability  1/2 . We say that two squares,
p  and  q,  are in the same connected monochromatic component 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  m n / 8 .

A-6.

Suppose that  f(x,y)  is a continuous real-valued function on the unit
square  0 <= x <= 1, 0 <= y <= 1.  Show that

  \int_0^1 ( \int_0^1  f(x,y) dx )^2 dy + 
  \int_0^1 ( \int_0^1  f(x,y) dy )^2 dx
    
is less than or equal to

  ( \int_0^1 \int_0^1  f(x,y) dx dy )^2 + 
  \int_0^1 \int_0^1 ( f(x,y) )^2 dx dy .


B-1.

Let  P(x) = c_n x^n + c_{n-1} x^{n-1} + ... + 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_n r , c_n r^2 + c_{n-1}, c_n r^3 + c_{n-1} r^2 + c_{n-2} r, ...,
      c_n r^n + c_{n-1} r^{n-1} + ... + c_1 r  
are integers.

B-2. 

Let  m  and  n  be positive integers.  Show that

    (m+n)!       m!    n!
 ----------- < ----- -----
 (m+n)^{m+n}    m^m   n^n


B-3. 

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 <= x <= a, 0 <= y <= f(x) }
has perimeter  k  units and area  k  square units for some real number  k.

B-4. 

Let  n  be a positive integer, n >= 2, and put  theta = 2 pi / n.
Define points  P_k = (k,0)  in the  xy-plane, for k = 1, 2, ..., 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 then simplify, the coordinates
of  R(x,y).

B-5.

Evaluate
            infty     1 + x^{n+1}   {x^n}
    lim    \prod   (--------------)
   x->1^-   n=0       1 +  x^n


[That's     \lim_{x\to 1^{-}} \prod_{n=0}^{\infty} 
            \left( {{1+x^{n+1}}\over{1+x^n}} \right)^{x^n}    in TeX -- djr]

B-6.

Let  A  be a non-empty 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'  with
a \in A  and  a' \in  A. Let  b_1 < b_2 < ... 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}  N(x)/x  = 0.