SIXTY-SEVENTH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 2, 2006 Examination A

A1. Find the volume of the region of points (x, y, z) such that

(x^{2} + y^{2} + z^{2} + 8)^{2} ≤ 36(x^{2} + y^{2}).

A2. Alice and Bob play a game in which they take turns removing stones from a heap that initially has n stones. The number of stones removed at each turn must be one less than a prime number. The winner is the player who takes the last stone. Alice plays first. Prove that there are infinitely many n such that Bob has a winning strategy. (For example, if n = 17, then Alice might take 6 leaving 11; then Bob might take 1 leaving 10; then Alice can take the remaining stones to win.)

A3. Let 1, 2, 3, …, 2005, 2006, 2007, 2009, 2012, 2016, … be a sequence defined by x_{k} = k for k = 1, 2, …, 2006 and x_{k+1} = x_{k} + x_{k−2005} for k ≥ 2006. Show that the sequence has 2005 consecutive terms each divisible by 2006.

A4. Let S = {1, 2, …, n} for some integer n > 1. Say a permutation π of S has a local maximum at k ∈ S if

(i) π(k) > π(k + 1) for k = 1;

(ii) π(k − 1) < π(k) and π(k) > π(k + 1) for 1 < k < n;
(iii) π(k − 1) < π(k) for k = n.

(For example, if n = 5 and π takes values at 1, 2, 3, 4, 5 of 2, 1, 4, 5, 3, then π has a local maximum of 2 at k = 1, and a local maximum of 5 at k = 4.) What is the average number of local maxima of a permutation of S, averaging over all permutations of S?

A5. Let n be a positive odd integer and let θ be a real number such that θ/π is irrational. Set a_{k} = tan(θ + kπ/n), k = 1, 2, …, n. Prove that

\frac{a_{1} + a_{2} + ⋯ + a_{n}}{a_{1}a_{2} ⋯ a_{n}}

is an integer, and determine its value.

A6. Four points are chosen uniformly and independently at random in the interior of a given circle. Find the probability that they are the vertices of a convex quadrilateral.

SIXTY-SEVENTH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 2, 2006 Examination B

B1. Show that the curve x^{3} + 3xy + y^{3} = 1 contains only one set of three distinct points, A, B, and C, which are vertices of an equilateral triangle, and find its area.

B2. Prove that, for every set X = {x_{1}, x_{2}, …, x_{n}} of n real numbers, there exists a non-empty subset S of X and an integer m such that

|m + ∑_{s∈S} s| ≤ \frac{1}{n + 1}.

B3. Let S be a finite set of points in the plane. A linear partition of S is an unordered pair {A, B} of subsets of S such that A ∪ B = S, A ∩ B = ∅, and A and B lie on opposite sides of some straight line disjoint from S (A or B may be empty). Let L_{S} be the number of linear partitions of S. For each positive integer n, find the maximum of L_{S} over all sets S of n points.

B4. Let Z denote the set of points in R^{n} whose coordinates are 0 or 1. (Thus Z has 2^{n} elements, which are the vertices of a unit hypercube in R^{n}.) Given a vector subspace V of R^{n}, let Z(V) denote the number of members of Z that lie in V. Let k be given, 0 ≤ k ≤ n. Find the maximum, over all vector subspaces V ⊆ R^{n} of dimension k, of the number of points in V ∩ Z.

B5. For each continuous function f : [0, 1] → R, let I(f) = ∫_{0}^{1} x^{2}f(x) dx and J(f) = ∫_{0}^{1} x (f(x))^{2} dx. Find the maximum value of I(f) − J(f) over all such functions f.

B6. Let k be an integer greater than 1. Suppose a_{0} > 0, and define

a_{n+1} = a_{n} + \frac{1}{\sqrt[k]{a_{n}}}

for n ≥ 0. Evaluate

lim_{n→∞} \frac{a_{n}^{k+1}}{n^{k}} .