FIFTY-FOURTH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 4, 1993 Examination A

A-1. The horizontal line y = c intersects the curve y = 2x − 3x^{3} in the first quadrant as in the figure. Find c so that the areas of the two shaded regions are equal.

y  x y = 2x − 3x^{2} y = c

A-2. Let (x_{n})_{n≥0} be a sequence of nonzero real numbers such that

x_{n}^{2} − x_{n−1}x_{n+1} = 1, for n = 1, 2, 3, ….

Prove there exists a real number a such that x_{n+1} = ax_{n} − x_{n−1} for all n ≥ 1.

A-3. Let P_{n} be the set of subsets of {1, 2, …, n}. Let c(n, m) be the number of functions f : P_{n} → {1, 2, …, m} such that f(A ∩ B) = min{f(A), f(B)}. Prove that

c(n, m) = ∑_{j=1}^{m} j^{n}.

A-4. Let x_{1}, x_{2}, …, x_{19} be positive integers each of which is less than or equal to 93. Let y_{1}, y_{2}, …, y_{93} be positive integers each of which is less than or equal to 19. Prove that there exists a (nonempty) sum of some x_{i}’s equal to a sum of some y_{j}’s.

A-5. Show that

∫_{−100}^{−10} (\frac{x^{2} − x}{x^{3} − 3x + 1})^{2} dx + ∫ \frac{1}{11} \frac{1}{101} (\frac{x^{2} − x}{x^{3} − 3x + 1})^{2} dx + ∫ \frac{11}{10} \frac{101}{100} (\frac{x^{2} − x}{x^{3} − 3x + 1})^{2} dx

is a rational number.

A-6. The infinite sequence of 2’s and 3’s

2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 2, 3, 3, 3, 2, …

has the property that, if one forms a second sequence that records the number of 3’s between successive 2’s, the result is identical to the given sequence. Show that there exists a real number r such that, for any n, the nth term of the sequence is 2 if and only if n = 1 + ⌊rm⌋ for some nonnegative integer m. (Note: ⌊x⌋ denotes the largest integer less than or equal to x.)

FIFTY-FOURTH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 4, 1993 Examination B

B-1. Find the smallest positive integer n such that for every integer m, with 0 < m < 1993, there exists an integer k for which

\frac{m}{1993} < \frac{k}{n} < \frac{m + 1}{1994}.

B-2. Consider the following game played with a deck of 2n cards numbered from 1 to 2n. The deck is randomly shuffled and n cards are dealt to each of two players, A and B. Beginning with A, the players take turns discarding one of their remaining cards and announcing its number. The game ends as soon as the sum of the numbers on the discarded cards is divisible by 2n + 1. The last person to discard wins the game. Assuming optimal strategy by both A and B, what is the probability that A wins?

B-3. Two real numbers x and y are chosen at random in the interval (0, 1) with respect to the uniform distribution. What is the probability that the closest integer to x/y is even? Express the answer in the form r + sπ, where r and s are rational numbers.

B-4. The function K(x, y) is positive and continuous for 0 ≤ x ≤ 1, 0 ≤ y ≤ 1, and the functions f(x) and g(x) are positive and continuous for 0 ≤ x ≤ 1. Suppose that for all x, 0 ≤ x ≤ 1,

∫_{0}^{1} f(y)K(x, y) dy = g(x) and ∫_{0}^{1} g(y)K(x, y) dy = f(x).

Show that f(x) = g(x) for 0 ≤ x ≤ 1.

B-5. Show there do not exist four points in the Euclidean plane such that the pairwise distances between the points are all odd integers.

B-6. Let S be a set of three, not necessarily distinct, positive integers. Show that one can transform S into a set containing 0 by a finite number of applications of the following rule: Select two of the three integers, say x and y, where x ≤ y and replace them with 2x and y − x.