From: rusin@cs.niu.edu (David Rusin)
Newsgroups: sci.math
Subject: Re: Putnam 2005
Date: Sun, 4 Dec 2005 06:41:51 +0000 (UTC)

In article <439219d7$0$20175$8fcfb975@news.wanadoo.fr>,
moubinool.omarjee <moubinool.omarjee@wanadoo.fr> wrote:
>Could some one post the Putnam 2005 problems
>
>Thank you
>
>
>

Here are the problems from the 2005 Putnam exam. I didn't have as much
time to work on them this year but I will try to post my answers to
some of them later this evening.


A1. Show that every positive integer is a sum of one or more numbers of the 
form   2^r 3^s,  where  r  and  s  are nonnegative integers and no summand 
divides another. (For example, 23=9+8+6.)

A2. Let S = {(a,b) | a = 1, 2, ..., n,  b = 1, 2, 3}.  A _rook tour_ of  S   
is a polygonal path made up of line segments connecting points  p_1, p_2, ..., 
p_{3n}  in sequence such that  (i) p_i \in S,   (ii)  p_i  and  p_{i+1}  are
a unit distance apart, for  1 <= i < 3n,   (iii)  for each  p \in S  there is
a unique  i  such that  p_i = p.   How many rook tours are there that begin
at  (1,1)  and end at  (n,1) ?

(An example of such a rook tour for  n=5  is depicted below)

    *---*---*   *---*
    |       |   |   |
    *---*   *   *   *
        |   |   |   |
    *---*   *---*   *

A3. Let  p(z)  be a polynomial of degree  n,  all of whose zeros have 
absolute value  1  in the complex plane.  Put  g(z) = p(z)/z^{n/2}.  Show 
that all the zeros of  g'(z) = 0  have absolute value  1.

A4.  Let  H  be an  n x n  matrix all of whose entries are  +- 1  and whose 
rows are mutually orthogonal. Suppose  H  has an  a x b  submatrix whose
entries are all  1.  Show that  ab <= n .

A5. Evaluate 
                                 /1
                                |   ln(x + 1)
                                |   --------- dx
                                |     2
                               /0    x  + 1

[That's  \int_0^1 ln(x+1) / (x^2+1)  dx   in one-line notations. --djr]

A6. Let  n  be given,  n >= 4,  and suppose that  P_1, P_2, ..., P_n  are
n  randomly, independently and uniformly, chosen points on a circle.
Consider the convex  n-gon  whose vertices are the  P_i.  What is the
probability that at least one of the vertex angles of this polygon is acute?


B1. Find a nonzero polynomial  P(x,y)  such that  P([a], [2a])=0  for
all real numebrs  a.  (Note:  [v]  is the greatest integer less than or
equal to  v.)

B2. Find all positive integers  n, k_1, ..., k_n  such that
k_1 + ... + k_n = 5n-4  and    1/k_1 + ... + 1/k_n = 1.

B3. Find all differentiable functions  f : (0, oo) -> (0, oo)  for which 
there is a positive real number  a  such that
  f'( a/x ) = x/(f(x))
for all  x > 0.

B4. For positive integers  m  and  n,  let  f(m,n)  denote the number of
n-tuples  (x_1, xs_2, ..., x_n)  of integers such that  
|x_1| + |x_2| + ... + |x_n| <= m.  Show that  f(m,n) = f(n,m) .

B5. Let  P(x_1, ..., x_n)  denote a polynomial with real coefficients in 
the variables  x_1, ..., x_n,  and suppose that
   (a) ( d^2/dx_1^2 + ...  + d^2/dx_n^2 ) P(x_1, ..., x_n) = 0
and that
   (b)    x_1^2 + ... + x_n^2   divides  P(x_1, x_2, ..., x_n).
Show that  P = 0  identically.

B6. Let  S_n  denote the set of all permutations of the numbers  1, 2, ..., n.
For  pi\in S_n,  let  sigma(pi) = 1  if  pi  is an even permutation and
sigma(pi) = -1 if  pi  is an odd permutation. Also, let  nu(pi)  denore the
number of fixed points of  pi. Show that
   \sum_{pi in S_n}   sigma(pi)/(nu(pi)+1) = (-1)^{n+1}  n/n+1.