FIFTIETH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 2, 1989 Examination A

A-1. How many primes among the positive integers, written as usual in base 10, are alternating 1’s and 0’s, beginning and ending with 1?

A-2. Evaluate ∫_{0}^{a} ∫_{0}^{b} e^{max{b^{2}x^{2},a^{2}y^{2}}} dy dx where a and b are positive.

A-3. Prove that if

11z^{10} + 10iz^{9} + 10iz − 11 = 0,

then |z| = 1. (Here z is a complex number and i^{2} = −1.)

A-4. If α is an irrational number, 0 < α < 1, is there a finite game with an honest coin such that the probability of one player winning the game is α? (An honest coin is one for which the probability of heads and the probability of tails are both \frac{1}{2}. A game is finite if with probability 1 it must end in a finite number of moves.)

A-5. Let m be a positive integer and let G be a regular (2m + 1)-gon inscribed in the unit circle. Show that there is a positive constant A, independent of m, with the following property. For any points p inside G there are two distinct vertices v_{1} and v_{2} of G such that

| |p − v_{1}| − |p − v_{2}| | < \frac{1}{m} − \frac{A}{m^{3}} .

Here |s − t| denotes the distance between the points s and t.

A-6. Let α = 1 + a_{1}x + a_{2}x^{2} + ⋯ be a formal power series with coefficients in the field of two elements. Let

a_{n} = \{ \begin{matrix}1 & if every block of zeros in the binary expansion of n \\ & has an even number of zeros in the block \\ 0 & otherwise. \end{matrix} \}

(For example, a_{36} = 1 because 36 = 100100_{2} and a_{20} = 0 because 20 = 10100_{2}.) Prove that α^{3} + xα + 1 = 0.

FIFTIETH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 2, 1989 Examination B

B-1. A dart, thrown at random, hits a square target. Assuming that any two parts of the target of equal area are equally likely to be hit, find the probability that the point hit is nearer

to the center than to any edge. Express your answer in the form \frac{a\sqrt{b} + c}{d}, where a, b, c, d are integers.

B-2. Let S be a non-empty set with an associative operation that is left and right cancellative (xy = xz implies y = z, and yx = zx implies y = z). Assume that for every a in S the set {a^{n} : n = 1, 2, 3, …} is finite. Must S be a group?

B-3. Let f be a function on [0, ∞), differentiable and satisfying

f′(x) = −3f(x) + 6f(2x)

for x > 0. Assume that |f(x)| ≤ e^{−\sqrt{x}} for x ≥ 0 (so that f(x) tends rapidly to 0 as x increases). For n a non-negative integer, define

μ_{n} = ∫_{0}^{∞} x^{n}f(x) dx

(sometimes called the nth moment of f).

a. Express μ_{n} in terms of μ_{0}.

b. Prove that the sequence \{μ_{n} \frac{3^{n}}{n!} \} always converges, and that the limit is 0 only if μ_{0} = 0.

B-4. Can a countably infinite set have an uncountable collection of non-empty subsets such that the intersection of any two of them is finite?

B-5. Label the vertices of a trapezoid T (quadrilateral with two parallel sides) inscribed in the unit circle as A, B, C, D so that AB is parallel to CD and A, B, C, D are in counterclockwise order. Let s_{1}, s_{2}, and d denote the lengths of the line segments AB, CD, and OE, where E is the point of intersection of the diagonals of T, and O is the center of the circle. Determine the least upper bound of \frac{s_{1}−s_{2}}{d} over all such T for which d ≠ 0, and describe all cases, if any, in which it is attained.

B-6. Let (x_{1}, x_{2}, … x_{n}) be a point chosen at random from the n-dimensional region defined by 0 < x_{1} < x_{2} < ⋯ < x_{n} < 1. Let f be a continuous function on [0, 1] with f(1) = 0. Set x_{0} = 0 and x_{n+1} = 1. Show that the expected value of the Riemann sum

∑_{i=0}^{n}(x_{i+1} − x_{i})f(x_{i+1})

is ∫_{0}^{1} f(t)P (t) dt, where P is a polynomial of degree n, independent of f, with 0 ≤ P (t) ≤ 1 for 0 ≤ t ≤ 1.