# Putnam exam 2004

 Questions to the 65rd annual Putnam exam: Source: http://www.math.niu.edu/~rusin/problems-math/ A-1. Basketball star Shanille O'Keal's team statistician keeps track of the number, S(N), of successful free throws she has made in her first N attempts of the season. Early in the season, S(N) was less than 80% of N, but by the end of the season, S(N) was more than 80% of N. Was there necessarily a moment in between when S(N) was exactly 80% of N ? A-2. For i = 1,2 let T_i be a triangle with side lengths a_i, b_i, c_i, and area A_i. Suppose that a_1 <= a_2, b_1 <= b_2, c_1 <= c_2, and that T_2 is an acute triangle. Does it follow that A_1 <= A_2 ? A-3. Define a sequence { u_n } by u_0 = u_1 = u_2 = 1, and thereafter by the condition that ( u_n u_{n+1} ) det( ) = n! ( u_{n+2} u_{n+3} ) for all n >= 0. Show that u_n is an integer for all n. (By convention, 0! = 1.) A-4. Show that for any positive integer n there is an integer N such that the product x_1 x_2 ... x_n can be expressed identically in the form x_1 x_2 ... x_n = \sum_{i=1}^N c_i ( a_{i1} x_1 + a_{i2} x_2 + ... + a_{in} x_n )^n where the c_i are rational numbers and each a_{ij} is one of the numbers, -1, 0, 1 . A-5. An m x n checkerboard is colored randomly: each square is independently assigned red or black with probability 1/2 . We say that two squares, p and q, are in the same connected monochromatic component if there is a sequence of squares, all of the same color, starting at p and ending at q, in which successive squares in the sequence share a common side. Show that the expected number of connected monochromatic regions is greater than m n / 8 . A-6. Suppose that f(x,y) is a continuous real-valued function on the unit square 0 <= x <= 1, 0 <= y <= 1. Show that \int_0^1 ( \int_0^1 f(x,y) dx )^2 dy + \int_0^1 ( \int_0^1 f(x,y) dy )^2 dx is less than or equal to ( \int_0^1 \int_0^1 f(x,y) dx dy )^2 + \int_0^1 \int_0^1 ( f(x,y) )^2 dx dy . B-1. Let P(x) = c_n x^n + c_{n-1} x^{n-1} + ... + c_0 be a polynomial with integer coefficients. Suppose that r is a rational number such that P(r) = 0. Show that the n numbers c_n r , c_n r^2 + c_{n-1}, c_n r^3 + c_{n-1} r^2 + c_{n-2} r, ..., c_n r^n + c_{n-1} r^{n-1} + ... + c_1 r are integers. B-2. Let m and n be positive integers. Show that (m+n)! m! n! ----------- < ----- ----- (m+n)^{m+n} m^m n^n B-3. Determine all real numbers a > 0 for which there exists a nonnegative continuous function f(x) defined on [0,a] with the property that the region R = { (x,y) ; 0 <= x <= a, 0 <= y <= f(x) } has perimeter k units and area k square units for some real number k. B-4. Let n be a positive integer, n >= 2, and put theta = 2 pi / n. Define points P_k = (k,0) in the xy-plane, for k = 1, 2, ..., n. Let R_k be the map that rotates the plane counterclockwise by the angle theta about the point P_k. Let R denote the map obtained by applying, in order, R_1, then R_2, ..., then R_n. For an arbitrary point (x,y), find, and then simplify, the coordinates of R(x,y). B-5. Evaluate infty 1 + x^{n+1} {x^n} lim \prod (--------------) x->1^- n=0 1 + x^n [That's \lim_{x\to 1^{-}} \prod_{n=0}^{\infty} \left( {{1+x^{n+1}}\over{1+x^n}} \right)^{x^n} in TeX -- djr] B-6. Let A be a non-empty set of positive integers, and let N(x) denote the number of elements of A not exceeding x. Let B denote the set of positive integers b that can be written in the form b = a - a' with a \in A and a' \in A. Let b_1 < b_2 < ... be the members of B, listed in increasing order. Show that if the sequence b_{i+1} - b_i is unbounded, then lim_{x \to\infty} N(x)/x = 0.