1996 Putnam problems and unofficial solutions, revised

As usual, first come the problems, then the problems with solutions. Comments and criticism at the end. Send any followup remarks to the USENET newsgroup sci.math.

Problems

Problem A1 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 into that rectangle (without the interiors of the squares overlapping). You may assume that the sides of the squares will be parallel to the sides of the rectangle. Problem A2 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 exist points X on C_{1} and Y on C_{2} such that M is the midpoint of the line segment XY. Problem A3 Suppose that each of twenty students has made a choice of anywhere from zero to six courses from a total of six courses offered. Prove or disprove: There are five students and two courses such that all five have chosen both courses or all five have chosen neither. Problem A4 Let S be a 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 : A → R such that g(a) < g(b) < g(c) implies (a, b, c) ∈ S. [Note: R is the set of real numbers.] Problem A5 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}. (For example, \binom{7}{1} + \binom{7}{2} + \binom{7}{3} + \binom{7}{4} = 7 + 21 + 35 + 35 = 2 · 7^{2}.) Problem A6 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: R is the set of real numbers.] Problem B1 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. Problem B2 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}} .

Problem B3 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}.

Problem B4 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} ) .

Problem B5 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.

Problem B6

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).

Unofficial solutions

Problem A1

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 into that rectangle (without the interiors of the squares overlapping). You may assume that the sides of the squares will be parallel to the sides of the rectangle.

Solution: Define x as the minimum of the side lengths and y as the maximum of the side lengths. The smallest rectangle containing both squares has width x + y and height y. The problem thus asks for the supremum of (x+y)y subject to the constraints 0 ≤ x ≤ y and x^{2} + y^{2} = 1.

The answer is (1 + \sqrt{2})/2. This is achieved when x = \sqrt{2 − \sqrt{2}}/2 and y = \sqrt{2 + \sqrt{2}}/2.

Indeed, 4x^{2} + 4y^{2} = (2 − \sqrt{2}) + (2 + \sqrt{2}) = 4, and 4xy + 4y^{2} = \sqrt{2^{2} − \sqrt{2}^{2}} + (2 + \sqrt{2}) = 2 + 2\sqrt{2}.

Proof without calculus that 2(x + y)y ≤ 1 + \sqrt{2} when x^{2} + y^{2} = 1: Define a = \sqrt{\sqrt{2} + 1} and b = \sqrt{\sqrt{2} − 1}. Then b^{2} −a^{2} = −2 and ab = 1, so (ax−by)^{2} = a^{2}x^{2} +b^{2}y^{2} −2axby = a^{2} − 2y^{2} − 2xy. Hence 2xy + 2y^{2} ≤ a^{2} = 1 + \sqrt{2}.

Problem A2

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 exist points X on C_{1} and Y on C_{2} such that M is the midpoint of the line segment XY.

Solution: Let P be the center of the small circle. The points on the circle are P + v where v is a vector of length 1. Let Q be the center of the large circle. The points on the circle are Q + w where w is a vector of length 3. Let O be the midpoint of P Q.

The midpoint of the line segment joining P + v and Q + w is O + (v + w)/2. By the triangle inequality, v/2 + w/2 has length between 1 and 2 inclusive.

Conversely, let A be any point whose distance from O is between 1 and 2 inclusive. Consider the circle around O of radius 3/2. There is a point on this circle within 1/2 of A, namely the closest point; there is a point on the circle at least 1/2 away from A, namely the farthest point; thus there is a point on the circle exactly 1/2 away from A. Define v as double the vector from that point to A, and w as double the vector from O to that point. Then A is the midpoint of P + v and Q + w.

The set of midpoints is therefore the set of points whose distance from O is between 1 and 2 inclusive.

Problem A3

Suppose that each of twenty students has made a choice of anywhere from zero to six courses from a total of six courses offered. Prove or disprove: There are five students and two courses such that all five have chosen both courses or all five have chosen neither.

Solution: Counterexample: Enumerate the \binom{6}{3} = 20 selections of 3 courses out of 6. Assign each selection to one student. For any pair of courses, there are exactly \binom{4}{1} = 4 students taking both courses, and \binom{4}{3} = 4 students taking neither course.

Problem A4

Let S be a 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 : A → R such that g(a) < g(b) < g(c) implies (a, b, c) ∈ S. [Note: R is the set of real numbers.]

Solution: If A is empty, let g be the empty function. Otherwise, select x ∈ A. I define an order on A − {x}: if a, b are distinct elements of A − {x}, I define “a < b” to mean “(b, x, a) ∈ S.”

This order is antisymmetric: if a < b then (a, x, b) ∉ S so b ≮ a. It has trichotomy: if a ≮ b then (b, x, a) ∉ S so (a, x, b) ∈ S so b < a. It is reflexive: if a < b and b < c then S contains both (x, a, b) and (b, c, x), hence (c, x, a); thus a < c.

Therefore it is a linear order. Select an order-preserving function g from A − {x} to R. Extend g to x by selecting a number g(x) smaller than any other g(a).

I claim that (a, b, c) ∈ S whenever g(a) < g(b) < g(c). By construction of g, b < c, so (c, x, b) ∈ S. If a = x then (c, a, b) ∈ S so (a, b, c) ∈ S. If a ≠ x then a < b so (b, x, a) ∈ S so (x, a, b) ∈ S; but (b, c, x) ∈ S, so (a, b, c) ∈ S.

Problem A5

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}. (For example, \binom{7}{1} + \binom{7}{2} + \binom{7}{3} + \binom{7}{4} = 7 + 21 + 35 + 35 = 2 · 7^{2}.)

Solution: Write S = ∑_{1≤j≤k} \binom{p}{j}/p. I will work in the p-adics modulo p.

First, (p − 1)(p − 2) … (p − j + 1) ≡ (−1)^{j−1}(j − 1)!, so \binom{p−1}{j−1} ≡ (−1)^{j−1} whenever 1 ≤ j ≤ p − 1. Thus \binom{p}{j}/p = \binom{p−1}{j−1}/j ≡ (−1)^{j−1}/j.

Hence S ≡ ∑_{1≤j≤k}(−1)^{j−1}/j. If j is even, say j = 2i, then −1/i ≡ 1/(p − i) (mod p), so −1/j ≡ 1/j + 1/(p − i) (mod p). Thus

S ≡ ∑_{1≤j≤k} \frac{1}{j} + ∑_{1≤2i≤k} \frac{1}{p − i} = ∑_{1≤j≤k} \frac{1}{j} + ∑_{p−⌊k/2⌋≤j≤p−1} \frac{1}{j}.

If p ≡ 1 (mod 3) then k = 2(p−1)/3 so p−⌊k/2⌋ = p−(p−1)/3 = k+1. If p ≡ 2 (mod 3) then k = 2(p − 2)/3 + 1 so p − ⌊k/2⌋ = p − (p − 2)/3 = 2 + 2(p − 2)/3 = k + 1. Either way S ≡ ∑_{1≤j≤p−1} 1/j. But 1/j runs over 1, 2, …, p − 1 modulo p as j runs over 1, 2, …, p − 1; so S ≡ 1 + 2 + … + (p − 1) = p(p − 1)/2 ≡ 0.

Problem A6

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: R is the set of real numbers.]

Solution: Case 1: c ≤ 1/4. In this case the only such functions are constants.

Define a = (1 − \sqrt{1 − 4c})/2 and b = (1 + \sqrt{1 − 4c})/2. Assume that f satisfies f(x) = f(x^{2} + c). If x ≥ b then the sequence x, \sqrt{x − c}, \sqrt{\sqrt{x − c} − c}, … converges to b. (It is decreasing, and bounded below by \sqrt{b − c} = b, so it converges to a solution y ≥ b of y = \sqrt{y − c}. The only solution is b.) Thus f(x), f(\sqrt{x − c}), … converges to f(b); but f(x) = f(\sqrt{x − c}) = ⋯, so f(x) = f(b).

If 0 ≤ x < b then the sequence x, x^{2} + c, (x^{2} + c)^{2} + c, … converges to a, so f(x) = f(a) as above. Thus, by continuity again, f(a) = f(b), so f(x) = f(b) for all x ≥ 0. Finally, for x < 0, f(x) = f(x^{2} + c) = f(−x) = f(b).

Case 2: c > 1/4. In this case any function of the following form will work. Let g be a continuous function on [0, c] such that g(c) = g(0). Define f(x) = g(x) for 0 ≤ x < c; define f(x) = g(\sqrt{x − c}) for c ≤ x < c^{2} + c; define f(x) = g(\sqrt{\sqrt{x − c} − c}) for c^{2} + c ≤ x < (c^{2} + c)^{2} + c; and so on. This construction covers all x ≥ 0, since y^{2} + c is at least c − 1/4 larger than y for every real number y. For x < 0 define f(x) = f(−x). Then f is continuous and satisfies f(x) = f(x^{2} + c).

These are the only such functions. Indeed, given f satisfying f(x) = f(x^{2} + c), define g(x) = f(x) for 0 ≤ x ≤ c. Then g is continuous, and g(c) = f(c) = f(0) = g(0). Furthermore, f(x) = f(\sqrt{x − c}) = g(\sqrt{x − c}) for c ≤ x < c^{2} + c, f(x) = f(\sqrt{x − c}) = g(\sqrt{\sqrt{x − c} − c}) for c^{2} + c ≤ x < (c^{2} + c)^{2} + c, and so on. For x < 0, f(x) = f(x^{2} + c) = f(−x). Thus f is recovered by the construction above.

Problem B1

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.

Solution: The answer is the nth Fibonacci number.

Write #S for the number of elements in S. Note that a set S is a minimal selfish set if and only if #S is the smallest element of S.

Induct on n. For n = 1 or n = 2, there is one minimal selfish set, namely {1}.

Fix n ≥ 2. Assume that there are a minimal selfish subsets of {1, 2, …, n} and b minimal selfish subsets of {1, 2, …, n − 1}. I will construct exactly a + b minimal selfish subsets of {1, 2, …, n + 1}.

Construction A: Let S be a minimal selfish subset of {1, 2, …, n}. Then S is a minimal selfish subset of {1, 2, …, n + 1}. This construction produces a minimal selfish subsets.

Every minimal selfish subset T of {1, 2, …, n + 1} not containing n + 1 is obtained from Construction A. Proof: T is a subset of {1, 2, …, n}.

Construction B: Let S be a minimal selfish subset of {1, 2, …, n − 1}. Define T = {n + 1}∪{x + 1 : x ∈ S}. Then T is a minimal selfish set: its smallest element is #S+1 = #T. This construction produces exactly b minimal selfish subsets, all different from the subsets in Construction A since they all contain n + 1.

Every minimal selfish subset T of {1, 2, …, n + 1} containing n + 1 is obtained from Construction B. Proof: 1 ∉ T since otherwise min T = 1 < 2 ≤ #T. Consider the set S = {x − 1 : x ∈ T, x ≠ n + 1}. Then #S = #T − 1 is the smallest element of S, so S is a minimal selfish set. Finally T = {n + 1} ∪ {x + 1 : x ∈ S}.

Problem B2 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}} .

Solution: Induct on n. For n = 1, (1/e)^{1/2} < 1 < (3/e)^{3/2} since 1 < e < 3.

For the inductive step, write s = 2n−1, t = 2n+1, u = 2n+3, and p = 1·3·5 ⋯ (2n−1). Given that (s/e)^{s/2} < p < (t/e)^{t/2}, I will show that (t/e)^{t/2} < pt < (u/e)^{u/2}.

If x is a nonzero real number then e^{x} > 1 + x. Plug in x = 2/s: e^{2/s} > t/s, so e > (t/s)^{s/2}, so (s/e)^{s/2} > (t/e)^{s/2}/e, so pt > (s/e)^{s/2}t > (t/e)^{s/2+1} = (t/e)^{t/2}. Plug in x = −2/u: e^{−2/u} > t/u, so 1/e > (t/u)^{u/2}, so (u/e)^{u/2} > e(t/e)^{u/2}, so pt < (t/e)^{t/2}t = e(t/e)^{t/2+1} < (u/e)^{u/2}.

Problem B3

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}.

Solution: Define c(n) = (2n^{3} + 3n^{2} − 11n + 18)/6. The answer is c(n).

For notational convenience set x_{0} = x_{n}. Define b(n) as the maximum value of x_{0}x_{1} + x_{1}x_{2} + ⋯ + x_{n−1}x_{n}. I will show for each n ≥ 2 that, first, b(n) = c(n); second, if b(n) = x_{0}x_{1} + ⋯ + x_{n−1}x_{n} then n − 1 and n are adjacent in x_{0}, x_{1}, x_{2}, …, x_{n}.

Induct on n. For n = 2, the only patterns are 1, 2 and 2, 1, each of which has sum 4 = c(2), with 1 and 2 adjacent.

Fix n ≥ 2. Any pattern for n + 1 is a pattern for n with the number n + 1 inserted somewhere. Say n + 1 is inserted between x_{i} and x_{i+1} in x_{0}, x_{1}, …, x_{n}. The sum x_{0}x_{1} + ⋯ + x_{n−1}x_{n} then increases by x_{i}(n + 1) + (n + 1)x_{i+1} − x_{i}x_{i+1}. I will show that this increase is at most n^{2} + 2n − 1. Therefore b(n + 1) ≤ b(n) + n^{2} + 2n − 1 = c(n)+n^{2} +2n−1 = c(n+1). Furthermore, c(n+1) may be achieved as follows. Consider an optimal pattern for n, with sum b(n); by induction, n − 1 and n are adjacent; insert n + 1 between n − 1 and n, increasing the sum by n^{2} + 2n − 1. Thus b(n + 1) = c(n + 1). Finally, if c(n + 1) is achieved, then the increase must be exactly n^{2} + 2n − 1; I will show that this implies {x_{i}, x_{i+1}} = {n − 1, n}, so n and n + 1 are adjacent in the pattern for n + 1.

Proof that (x + y)(n + 1) − xy ≤ n^{2} + 2n − 1 when x and y are distinct elements of {1, 2, …, n}: If x = n then y ≤ n−1 so (x+y)(n+1)−xy = n(n+1)+y ≤ n(n+1)+n−1 = n^{2} + 2n − 1. Otherwise x ≤ n − 1 so (x + y)(n + 1) − xy = x(n + 1 − y) + y(n + 1) ≤ (n − 1)(n + 1 − y) + y(n + 1) = n^{2} − 1 + 2y ≤ n^{2} + 2n − 1. Equality is achieved only when {x, y} = {n − 1, n}.

Problem B4

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} ) .

Solution: Suppose sin A = ( \begin{matrix}1 & 1996 \\ 0 & 1 \end{matrix} ). The set \{xA + yI : x ∈ R, y ∈ R\} is closed

under multiplication by A (since A is a root of its characteristic polynomial) and under formation of limits, so it contains sin A. Find x and y such that sin A = xA + yI. Then x ≠ 0 since sin A is not a multiple of I. Thus A = (sin A − yI)/x. Write t = (1 − y)/x

and u = 1996/x, so that A = ( \begin{matrix}t & u \\ 0 & t \end{matrix} ). Then sin A = ( \begin{matrix}sin t & u cos t \\ 0 & sin t \end{matrix} ), so sin t = 1 and

u cos t = 1996; but if sin t = 1 then cos t = 0. Contradiction.

Problem B5

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.

Solution: (The following solution, modulo notation, is stolen from a solution published by Manjul Bhargava and Kiran S. Kedlaya.)

Given a string S, I define S_{i} as 1 if the ith symbol of S is X, −1 if it is O. Thus Δ(S) = ∑_{i} S_{i}. Write S′_{i} = S_{i+1}/S_{i}.

If S′_{i} = −1 for all even i, or S′_{i} = −1 for all odd i, then S is balanced. Proof: S′_{i} = −1 means that S_{i} + S_{i+1} = 0. Thus pairs cancel in any sum S_{j} + S_{j+1} + ⋯ + S_{k}, leaving at most two terms.

Conversely, if S is balanced, then S′_{i} = −1 for all even i or S′_{i} = −1 for all odd i. Proof: I claim that, in the sequence S′_{1}, S′_{2}, …, the distance between any two 1’s is even. Thus, if S′_{j} = 1 for some even j, then S′_{i} = −1 for all odd i. Proof of the claim: It is enough to show that the distance between any two adjacent 1’s is even. So consider l < r such that S′_{l} = 1 = S′_{r} but S′_{i} = −1 for l < i < r. If r − l is odd then S_{r} = S_{l} so S_{l} + ⋯ + S_{r+1} = S_{l} + S_{r} + S_{r+1} = 3S_{l}.

Say n ≥ 1. Every choice of S_{1} and S′_{1}, S′_{2}, …, S′_{n−1} determines a unique string. Thus there are 2 · 2^{⌊(n−1)/2⌋} strings for which S′_{i} = −1 for all odd i and 2 · 2^{⌊n/2⌋} strings for which S′_{i} = −1 for all even i. The overlap is 2 strings for which S′_{i} = −1 for all i. Hence the total number of balanced strings is 2^{⌊(n+1)/2⌋} + 2^{⌊(n+2)/2⌋} − 2. This formula also works for n = 0, where there is 1 balanced string.

Problem B6

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).

Solution: Define f(u, v) = ∑_{i} e^{a_{i}u+b_{i}v}. I will construct a number R such that f(u, v) > f(0, 0) when u^{2} + v^{2} ≥ R. Since f is continuous, it has a minimum value on the compact set D = {(u, v) : u^{2} + v^{2} ≤ R}, say at a point P = (log x, log y). P is an interior point of D since otherwise f(P) > f(0, 0) by construction of R. Thus f’s partial derivatives at P, namely ∑_{i} a_{i}x^{a_{i}}y^{b_{i}} and ∑_{i} b_{i}x^{a_{i}}y^{b_{i}}, must both be 0.

I construct R as follows. Consider an edge E of the polygon. Let θ_{E} be the angle spanned by E from the point of view of the origin; then θ_{E} < π. For each endpoint (a, b) of E, the quantity \sqrt{a^{2} + b^{2}} cos(θ_{E}/2) is positive. Let m be the minimum value of \sqrt{a^{2} + b^{2}} cos(θ_{E}/2) over all edges E and endpoints (a, b). Finally I define R = (n/m)^{2}.

Here is why R works. Consider any (u, v) with u^{2} + v^{2} ≥ R. Consider the ray from (0, 0) in the direction (u, v). This ray intersects some edge E of the polygon. The ray from (0, 0) to (u, v) is within θ_{E}/2 < π/2 of the ray from (0, 0) to one of E’s endpoints, say (a, b). Thus au + bv ≥ \sqrt{u^{2} + v^{2}}\sqrt{a^{2} + b^{2}} cos(θ_{E}/2) ≥ m\sqrt{u^{2} + v^{2}} ≥ m\sqrt{R} = n so f(u, v) ≥ e^{au+bv} ≥ e^{n} > n = f(0, 0) as claimed.

Comments

A5 is an old problem. I didn’t recognize it at first, but I’m sure some contestants did.

As usual, several exam questions were poorly worded. In A1, is the contestant obliged to prove that any rectangle containing a 3/5 square and a 4/5 square must have sides at least 4/5 and 7/5? The problem singled out one geometrically obvious fact, telling contestants to assume that fact; does this mean that other such facts must be proven? In A3, what is the order of quantifiers? The problem could be read as “there is a number c between 0 and 6, and each student chooses c courses”; a contestant could waste a great deal of time trying to figure out what the problem means, even though the answer turns out to be the same. Rewrite: “There are twenty students. There are six courses. Is there necessarily a pair of courses, and a set of five students, such that either (1) all five students are taking both courses or (2) all five students are taking neither course?” In A5, the floor notation is not defined. In B3, what is the point of saying “as a function of n”? In B5, “thus” should have been “for example.”

The explicit formula for sin ( \begin{matrix}t & u \\ 0 & t \end{matrix} ) in B4, involving the derivative of sin, is a special

case of a general formula for functions of Jordan blocks. Thanks to A. O. L. Atkin for pointing out the reduction to this case; my first reduction, with the Jordan canonical form, used substantially more background knowledge.

This revised solution set corrects a few typos and gives a much simpler proof of B5. I’m satisfied that these solutions are all reasonably close to what the question writers had in mind.

—Daniel J. Bernstein, djb@pobox.com, 11 December 1996