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. 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 \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. A2 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} A3 Find the minimum value of | sin x + cos x + tan x + cot x + sec x + csc x | for real numbers x. A4 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 | . 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 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. 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 \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 ? ================================ B1 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? B2 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} . B3 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 .) B4 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. B5 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. B6 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.