Putnam Exam 2003

Putnam Exam 2003

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

       Questions from the 64th Putnam exam, Dec 6 2003.

Let  n  be a fixed positive integer. How many ways are there to write  n
as a sum of positive integers,  n = a_1 + a_2 + ... + a_k,  with  k  an 
arbitrary positive integer and  a_1 \le a_2 \le .. a_k \le a_1  + 1?
For example, with n=4, there are four ways: 4, 2+2, 1+1+2, 1+1+1+1.

Let a1, a2, ..., a_n  and  b1, b2, ..., b_n  be nonnegative real numbers.
Show that
      (a1 a2 ... a_n)^{1/n} + (b1 b2 ... b_n)^{1/n} <=
                       ( (a1+b1) (a2+b2) ... (a_n + b_n) )^{1/n}

Find the minimum value of 
  | sin x + cos x + tan x + cot x + sec x + csc x |
for real numbers  x.

Suppose that a,b,c,A,B < C  are real numbers, a\ne 0 and A \ne 0, such that
          | a x^2 + b x + c | <= | A x^2 + B x + C |
for all real numbers  x. Show that
              | b^2 - 4 a c | <= | B^2 - 4 A C |   .

A Dyck n-path is a lattice path of  n  upsteps (1,1) and  n  downsteps (1,-1)
that starts at the origin  O  and never dips below the  x-axis. 
A return is a maximal sequence of contiguous downsteps that terminates
on the  x-axis. For example, the Dyck 5-path illustrated has two returns,
of length  3  and  1  respectively.
             / \          
        *   *   *         
       / \ /     \        
      *   *       *   *   
     /             \ / \  
  O *---------------*---*

Show that there is a one-to-one correspondence between the Dyck  n-paths
with no return of even length and the Dyck (n-1) paths.

For a set  S  of nonnegative integers, let  r_S(n)  denote the number of
ordered pairs  (s_1, s_2)  such that  s_1 \in S, s_2 \in S, s_1 \ne s2,
and  s_1 + s_2 = n.  Is it possible to partition the nonnegative
integers into two sets  A  and  B  in such a way that  r_A(n) = r_B(n)
for all  n ?


Do there exist polynomials  a(x), b(x), c(y), d(y)  such that
       1 + x y + x^2 y^2 = a(x) c(y) + b(x) d(y)
holds identically?

Let  n  be a positive integer. Starting with the sequence  
1, 1/2, 1/3, ..., 1/n  form a new sequence of  n-1  entries
3/4, 5/12, ..., (2n-1)/{2n(n-1)}  by taking the averages of
two consecutive entries in the first sequence. Repeat the
averaging of neighbors on the second sequence to obtain a third 
sequence of  n-2  entries and continue the final sequence produced
consists of a single number  x_n.  Show that  x_n < {2/n} .

Show that for each positive integer  n,
    n ! = \Prod_{i=1}^n  lcm{1, 2, ..., [n/i] } .
(Here lcm denotes the least common multiple, and  [x]  denotes the
greatest integer \le  x .)

Let  f(z) = a z^4 + b z^3 + c z^2 + d z + e = a(z-r_1)(z-r_2)(z-r_3)(z-r_4)
where  a,b,c,d,e  are integers, a \ne 0.  Show that if  r_1 + r_2  is a
rational number, and if  r_1 + r_2 \ne r_3 + r_4  then  r_1 r_2  is a
rational number.

Let  A,B, and C  be equidistant points on the circumference of a circle
of unit radius centered at  O,  and let  P  be any point in the circle's
interior.  Let  a, b, c  be the distance from  P  to A, B, C  respectively.
Show that there is a triangle with side lengths  a, b, c  and that the
area of this triangle depends only on the distance from  P  to  O.

Let  f(x)  be  a continuous real-valued function defined on the interval
[0,1]. Show that 
   \int_0^1 \int_0^1 | f(x) + f(y) | dx dy > = \int_0^1 |f(x)| dx.