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.
Return to [ Polya
Home Page ] [Members ] [The Problems
] [Inventory
] [Reserve Area
]