POLYA035:  (2003 Putnam A-Problems, 12/6/03).

[Putnam 2003:A1] 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 <= a_2 <= ... <= a_k <=a_1+1? For example, with n = 4, there are four ways: 4, 2+2, 1+1+2, 1+1+1+1.

[Putnam 2003:A2] Let a_1, a_2, \dots, a_n and b_1, b_2, ..., b_n be nonnegative real numbers. Show that
(a_1a_2...a_n)^(1/n) + (b_1b_2...b_n)^(1/n) <= ((a_1+b_1)(a_2+b_2)...(a_n+b_n))^(1/n).

[Putnam 2003:A3] Find the minimum value of |sin x + cos x + tan x + cot x + sec x + csc x| for real numbers x.

[Putnam 2003:A4]  Suppose that a,b, c, A, B, C are real numbers, a, A nonzero, such that  |ax^2+bx+c| <= |Ax^2+Bx+C| for all real numbers x. Show that |b^2-4ac|<=|B^2-4AC|.

[Putnam 2003:A5]  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

(0,0)->(1,1)->(2,2)->(3,1)->(4,2)->(5,3)->(6,2)->(7,1)->(8,0)->(9,1)->(10,0)

has two returns, of lengths 3 and 1 respectively. Show that there is a one-to-one correspondence between the Dyck n-paths with no return of even length and Dyck (n-1)-paths.

[Putnam 2003:A6] 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, s_2 are distinct elements of S 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?

***********************************************************************************************

[Putnam 2003:A1] 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 <= a_2 <= ... <= a_k <=a_1+1? For example, with n = 4, there are four ways: 4, 2+2, 1+1+2, 1+1+1+1.

[JPE] (12/6):  Suppose 1<=k<=n, n = kq+r (euclidean division); the only way to get n = a_1+...+a_k with a_1<=a_2<=...<=a_k<=a_1+1 is to take
a_i = q for i<=k-r and a_i = q+1 for i>k-r.  Hence, the problem has exactly n solutions.

[TS](12/8): [pdf]

[Putnam 2003:A2] Let a_1, a_2, \dots, a_n and b_1, b_2, ..., b_n be nonnegative real numbers. Show that
(a_1a_2...a_n)^(1/n) + (b_1b_2...b_n)^(1/n) <= ((a_1+b_1)(a_2+b_2)...(a_n+b_n))^(1/n).

[JPE](12/6): As f(x) = ln(1+exp(x)) is convex, we have f[(x_1+..+x_n)/n]<=[f(x_1)+..f(x_n)]/n.  Putting x_i = ln(a_i/b_i), we get the required inequality.

[TS] (12/7): We use the well known H\"older inequality
$\left|\sum_{k=1}^n x_ky_k\right|\le \left(\sum_{k=1}^n|x_k|^p\right)^{1/p}\left(\sum_{k=1}^n|y_k|^q\right)^{1/q}$
if $p,q\in[1,\infty]$ and $1/p+1/q = 1$. We apply it with $p = n$, $q=n/(n-1)$, $x_1=a_1^{1/n}$, $y_1=(a_2\cdots a_n)^{1/n}$,
$x_2=b_1^{1/n}$, $y_2=(b_2\cdots b_n)^{1/n}$. Then

\begin{eqnarray*}
(a_1a_2\cdots a_n)^{1/n}+(b_1b_2\cdots b_n)^{1/n} &=&
a_1^{1/n}(a_2\cdots a_n)^{1/n}+b_1^{1/n}(b_2\cdots b_n)^{1/n}\\
= x_1y_1+x_2y_2\le
\left(x_1^n+x_2^n\right)^{1/n}\left(y_1^{n/(n-1)}+y_2^{n/(n-1)}\right)^{(n-1)/n}\\
=(a_1+b_1)^{1/n}\left((a_2\cdots
a_n)^{1/(n-1)}+(b_2\cdots b_n)^{1/(n-1)} \right)^{(n-1)/n}.
\end{eqnarray*}
The case $n=1$ being trivial, the result follows at once by induction on $n$.

[Putnam 2003:A3] Find the minimum value of |sin x + cos x + tan x + cot x + sec x + csc x| for real numbers x.

[JPE] (12/6): The minimum value is 2 root(2)-1 corresponding to sin(2x)=2(1-root(2)) but my proof is very tedious...

[JPE] (12/7): Here is a shorter solution. Let T = sin(x)+cos(x), then sin(x)cos(x)=(T^2-1)/2. Thus we have to find the minimum value of f(T) = |(T^2-T+2)/(T-1)|. This minimum is f(1-root(2)) = 2root(2)-1.

[TS](12/8): [pdf

[Putnam 2003:A4]  Suppose that a,b, c, A, B, C are real numbers, a, A nonzero, such that  |ax^2+bx+c| <= |Ax^2+Bx+C| for all real numbers x. Show that |b^2-4ac|<=|B^2-4AC|.

[JPE](12/7): (1) If B^2-4AC>=0, the roots x_1, x_2 of Ax^2+Bx+C=0 (possibly x_1=x_2) are the roots of ax^2+bx+c=0; hence (x_1-x_2)^2 = (b^2-4ac)/a^2 = (B^2-4AC)/A^2
Now, if we look to what happens when x->infinity, xe get |a| <= |A| and the result.
(2) If B^2-4AC <0 and b^2-4ac>=0, we have (A+a)x^2+(B+b)x+(C+c)>=0 and (A-a)x^2+(B-b)x+(C-c)>=0. The discriminants of these two polynomials are <=0. Adding these two discriminants, we get b^2-4ac<=4AC-B^2.
(3) If B^2-4AC<0 and b^2-4ac<0, consider the ellipses E : Ax^2+Bxy+Cy^2=1 and e : ax^2+bxy+cy^2=1. E is contained in e and Area(E) = 2Pi/root(4AC-B^2); area(e) = 2Pi/root(4ac-b^2).

[JPE] (12/8): Alternatively, for (3), if b^2-4ac<0 and B^2-4AC<0, we can without loss of generality suppose a>0 and A>0. Then (4ac-b^2)/(4a) = Min |ax^2+bx+c| <= Min |Ax^2+Bx+C| = (4AC-B^2)/(4A)
and - as in case (1) - a<=A and the result.

[TS](12/8): [pdf]

[Putnam 2003:A5]  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

(0,0)->(1,1)->(2,2)->(3,1)->(4,2)->(5,3)->(6,2)->(7,1)->(8,0)->(9,1)->(10,0)

has two returns, of lengths 3 and 1 respectively. Show that there is a one-to-one correspondence between the Dyck n-paths with no return of even length and Dyck (n-1)-paths.

[LZ](12/8): [pdf]

[Putnam 2003:A6] 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, s_2 are distinct elements of S 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?

[SCL] (12/6):  A = 0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33,34, 36, 39, 40, 43, 45, 46, 48, 51, 53, 54, 57, 58, 60, 63, ...

B = 1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32,35, 37, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 59, 61, 62,...

pattern so far is:  abba baab baab abba . baab abba abba baab . baab abba abba baab .abba baab baab abba
It shouldn't be too hard to continue the pattern and prove that it works.
The pattern seems to be, with 0 in set A, and 1 in set B: after dealing out the first 2^k entries, the next entry goes in B. Then the pattern is either the reverse of the pattern for the first 2^k (read from right to left) or the reverse of the complement of the first pattern (read from right to left and interchange a's and b's), which ever of these two patterns would start with a b.
Now, proof should be easy, but I may not work on it for a while.

[JPE](12/8): The sets A and B appear in the Encyclopedia of Integer Sequences http://www.research.att.com/~njas/sequences/  as  A000069 and A001969.

Bibliography.