55th Putnam 1994

A1.  an is a sequence of positive reals satisfying an ≤ a2n + a2n+1 for all n. Prove that ∑ an diverges.
A2.  Let R be the region in the first quadrant bounded by the x-axis, the line 2y = x, and the ellipse x2/9 + y2 = 1. Let R' be the region in the first quadrant bounded by the y-axis, the line y = mx, and the ellipse. Find m such that R and R' have the same area.
A3.  X is the set of points on one or more sides of a triangle with sides length 1, 1 and √2. Show that if X is 4-colored, then there must be two points of the same color a distance 2 - √2 or more apart.
A4.  A and B are 2 x 2 matrices with integral values. A, A + B, A + 2B, A + 3B, and A + 4B all have inverses with integral values. Show that A + 5B does also.
A5.  Given a sequence of positive real numbers which tends to zero, show that every non-empty interval (a, b) contains a non-empty subinterval (c, d) that does not contain any numbers equal to a sum of 1994 distinct elements of the sequence.
A6.  Let Z be the integers. Let f1, f2, ... , f10 : Z → Z be bijections. Given any n ∈ Z we can find some composition of the fi (allowing repetitions) which maps 0 to n. Consider the set of 1024 functions S = { g1g2... g10}, where gi = the identity or fi. Show that at most half the functions in S map a finite (non-empty) subset of Z onto itself.
B1.  For a positive integer n, let f(n) be the number of perfect squares d such that |n - d| ≤ 250. Find all n such that f(n) = 15. [The perfect squares are 0, 1, 4, 9, 16, ... .]
B2.  For which real α does the curve y = x4 + 9x3 + α x2 + 9x + 4 contain four collinear points?
B3.  Let R be the reals and R+ the positive reals. f : R → R+ is differentiable and f '(x) > f(x) for all x. For what k must f(x) exceed ekx for all sufficiently large x?
B4.  A is the 2 x 2 matrix (aij) with a11 = a22 = 3, a12 = 2, a21 = 4 and I is the 2 x 2 unit matrix. Show that the greatest common divisor of the entries of An - I tends to infinity.
B5.  For any real α define fα(x) = [αx]. Let n be a positive integer. Show that there exists an α such that for 1 ≤ k ≤ n, fαk(n2) = n2 - k = fαk(n2), where fαk denotes the k-fold composition of fα.
B6.  a, b, c, d are integers in the range 0 - 99. Show that if 101a -100·2a + 101b - 100·2b = 101c - 100·2c + 101d - 100·2d (mod 10100) then {a, b} = {c, d}.

pdf version

To avoid possible copyright problems, I have changed the wording, but not the substance of all the problems. The original text of the problems and the official solutions are in American Mathematical Monthly 102 (1995) 677.  
Putnam home
© John Scholes
16 Dec 1998
Last updated/corrected 19 Oct 03