The Fifty-Seventh Annual William Lowell Putnam Mathematical Competition Saturday, December 7, 1996

A-1 Find the least number A such that for any two squares of combined area 1, a rectangle of area A exists such that the two squares can be packed in the rectangle (without interior overlap). You may assume that the sides of the squares are parallel to the sides of the rectangle.

A-2 Let C_{1} and C_{2} be circles whose centers are 10 units apart, and whose radii are 1 and 3. Find, with proof, the locus of all points M for which there exists points X on C_{1} and Y on C_{2} such that M is the midpoint of the line segment XY.

A-3 Suppose that each of 20 students has made a choice of anywhere from 0 to 6 courses from a total of 6 courses offered. Prove or disprove: there are 5 students and 2 courses such that all 5 have chosen both courses or all 5 have chosen neither course.

A-4 Let S be the set of ordered triples (a, b, c) of distinct elements of a finite set A. Suppose that

1. (a, b, c) ∈ S if and only if (b, c, a) ∈ S;

2. (a, b, c) ∈ S if and only if (c, b, a) ∉ S;

3. (a, b, c) and (c, d, a) are both in S if and only if (b, c, d) and (d, a, b) are both in S.

Prove that there exists a one-to-one function g from A to R such that g(a) < g(b) < g(c) implies (a, b, c) ∈ S. Note: R is the set of real numbers.

A-5 If p is a prime number greater than 3 and k = ⌊2p/3⌋, prove that the sum

\binom{p}{1} + \binom{p}{2} + ⋯ + \binom{p}{k}

of binomial coefficients is divisible by p^{2}.

A-6 Let c > 0 be a constant. Give a complete description, with proof, of the set of all continuous functions f : R → R such that f(x) = f(x^{2} + c) for all x ∈ R. Note that R denotes the set of real numbers.

B-1 Define a selfish set to be a set which has its own cardinality (number of elements) as an element. Find, with proof, the number of subsets of {1, 2, …, n} which are minimal selfish sets, that is, selfish sets none of whose proper subsets is selfish.

B-2 Show that for every positive integer n,

(\frac{2n − 1}{e})^{\frac{2n−1}{2}} < 1 · 3 · 5 ⋯ (2n − 1) < (\frac{2n + 1}{e})^{\frac{2n+1}{2}} .

B-3 Given that {x_{1}, x_{2}, …, x_{n}} = {1, 2, …, n}, find, with proof, the largest possible value, as a function of n (with n ≥ 2), of

x_{1}x_{2} + x_{2}x_{3} + ⋯ + x_{n−1}x_{n} + x_{n}x_{1}.

B-4 For any square matrix A, we can define sin A by the usual power series:

sin A = ∑_{n=0}^{∞} \frac{(−1)^{n}}{(2n + 1)!}A^{2n+1}.

Prove or disprove: there exists a 2 × 2 matrix A with real entries such that

sin A = ( \begin{matrix}1 & 1996 \\ 0 & 1 \end{matrix} ) .

B-5 Given a finite string S of symbols X and O, we write Δ(S) for the number of X’s in S minus the number of O’s. For example, Δ(XOOXOOX) = −1. We call a string S balanced if every substring T of (consecutive symbols of) S has −2 ≤ Δ(T) ≤ 2. Thus, XOOXOOX is not balanced, since it contains the substring OOXOO. Find, with proof, the number of balanced strings of length n.

B-6 Let (a_{1}, b_{1}), (a_{2}, b_{2}), …, (a_{n}, b_{n}) be the vertices of a convex polygon which contains the origin in its interior. Prove that there exist positive real numbers x and y such that

(a_{1}, b_{1})x^{a_{1}}y^{b_{1}} + (a_{2}, b_{2})x^{a_{2}}y^{b_{2}} + ⋯ + (a_{n}, b_{n})x^{a_{n}}y^{b_{n}} = (0, 0).