FIFTY-FIFTH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 3, 1994 Examination A

A-1. Suppose that a sequence a_{1}, a_{2}, a_{3}, … satisfies 0 < a_{n} ≤ a_{2n} + a_{2n+1} for all n ≥ 1. Prove that the series ∑_{n=1}^{∞} a_{n} diverges.

A-2. Let A be the area of the region in the first quadrant bounded by the line y = \frac{1}{2}x, the x-axis, and the ellipse \frac{1}{9}x^{2} + y^{2} = 1. Find the positive number m such that A is equal to the area of the region in the first quadrant bounded by the line y = mx, the y-axis, and the ellipse \frac{1}{9}x^{2} + y^{2} = 1.

A-3. SHow that if the points of an isosceles right triangle of side length 1 are each colored with one of four colors, then there must be two points of the same color which are at least a distance 2 − \sqrt{2} apart.

A-4. Let A and B be 2 × 2 matrices with integer entries such that A, A + B, A + 2B, A + 3B, and A + 4B are all invertible matrices whose inverses have integer entries. Show that A + 5B is invertible and that its inverse has integer entries.

A-5. Let (r_{n}) be a sequence of positive real numbers such that lim_{n→∞} r_{n} = 0. Let S be the set of numbers representable as a sum

r_{i_{1}} + r_{i_{2}} + ⋯ + r_{i_{1994}},

with i_{1} < i_{2} < ⋯ < i_{1994}. Show that every nonempty interval (a, b) contains a nonempty subinterval (c, d) that does not intersect S.

A-6. Let f_{1}, f_{2}, …, f_{10} be bijections of the set of integers such that for each integer n, there is some composition f_{i_{1}} ∘ f_{i_{2}} ∘ ⋯ ∘ f_{i_{m}} of these functions (allowing repititions) which maps 0 to n. COnsider the set of 1024 functions

F = {f_{1}^{e_{1}} ∘ f_{2}^{e_{2}} ∘ ⋯ ∘ f_{10}^{e_{10}}},

e_{i} = 0 or 1 for 1 ≤ i ≤ 10. (f_{i}^{0} is the identity function and f_{i}^{1} = f.) Show that if A is any nonempty finite set of integers, than at most 512 of the functions in F map A to itself.

FIFTY-FIFTH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 3, 1994 Examination B

B-1. Find all positive integers that are within 250 of exactly 15 perfect squares.

B-2. For which real numbers c is there a straight line that intersects the curve

y = x^{4} + 9x^{3} + cx^{2} + 9x + 4

in four distinct points?

B-3. Find the set of all real numbers k with the following property: For any positive, differentiable function f that satisfies f′(x) > f(x) for all x, there is some number N such that f(x) > e^{kx} for all x > N.

B-4. For n ≥ 1, let d_{n} be the greatest common divisor of the entries of A^{n} − I, where

A = ( \begin{matrix}3 & 2 \\ 4 & 3 \end{matrix} ) and I = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) .

Show that lim_{n} d_{n} = ∞.

B-5. For any real number α, define the function f_{α}(x) = ⌊αx⌋. Let n be a positive integer. Show that there exists an α such that for 1 ≤ k ≤ n,

f_{α}^{k}(n^{2}) = n^{2} − k = f_{α^{k}}(n^{2}).

B-6. For any integer a, set

n_{a} = 101a − 100 · 2^{a}.

Show that for 0 ≤ a, b, c, d ≤ 99, n_{a} + n_{b} ≡ n_{c} + n_{d} (mod 10100) implies {a, b} = {c, d}.