Solutions to the 63rd William Lowell Putnam Mathematical Competition Saturday, December 7, 2002

Kiran Kedlaya and Lenny Ng

A1 By differentiating P_{n}(x)/(x^{k} − 1)^{n+1}, we find that P_{n+1}(x) = (x^{k} −1)P′_{n}(x)−(n+1)kx^{k−1}P_{n}(x); substituting x = 1 yields P_{n+1}(1) = −(n + 1)kP_{n}(1). Since P_{0}(1) = 1, an easy induction gives P_{n}(1) = (−k)^{n}n! for all n ≥ 0.

Note: one can also argue by expanding in Taylor series around 1. Namely, we have

\frac{1}{x^{k} − 1} = \frac{1}{k(x − 1) + ⋯} = \frac{1}{k} (x − 1)^{−1} + ⋯,

so

\frac{d^{n}}{dx^{n}} \frac{1}{x^{k} − 1} = \frac{(−1)^{n}n!}{k(x − 1)^{−n−1}}

and

P_{n}(x) = (x^{k} − 1)^{n+1} \frac{d^{n}}{dx^{n}} \frac{1}{x^{k} − 1}

= (k(x − 1) + ⋯)^{n+1}

(\frac{(−1)^{n}n!}{k}(x − 1)^{−n−1} + ⋯)

= (−k)^{n}n! + · · · .

A2 Draw a great circle through two of the points. There are two closed hemispheres with this great circle as boundary, and each of the other three points lies in one of them. By the pigeonhole principle, two of those three points lie in the same hemisphere, and that hemisphere thus contains four of the five given points.

Note: by a similar argument, one can prove that among any n+3 points on an n-dimensional sphere, some n+1 of them lie on a closed hemisphere. (One cannot get by with only n+2 points: put them at the vertices of a regular simplex.) Namely, any n of the points lie on a great sphere, which forms the boundary of two hemispheres; of the remaining three points, some two lie in the same hemisphere.

A3 Note that each of the sets {1}, {2}, …, {n} has the desired property. Moreover, for each set S with integer average m that does not contain m, S ∪ {m} also has average m, while for each set T of more than one element with integer average m that contains m, T \{m} also has average m. Thus the subsets other than {1}, {2}, …, {n} can be grouped in pairs, so T_{n} − n is even.

A4 (partly due to David Savitt) Player 0 wins with optimal play. In fact, we prove that Player 1 cannot prevent Player 0 from creating a row of all zeroes, a column of all zeroes, or a 2 × 2 submatrix of all zeroes. Each of these forces the determinant of the matrix to be zero. For i, j = 1, 2, 3, let A_{ij} denote the position in row i and column j. Without loss of generality, we may assume that Player 1’s first move is at A_{11}. Player 0 then plays at A_{22}:

(\begin{matrix}1 & ∗ & ∗ \\ ∗ & 0 & ∗ \\ ∗ & ∗ & ∗ \end{matrix})

After Player 1’s second move, at least one of A_{23} and A_{32} remains vacant. Without loss of generality, assume A_{23} remains vacant; Player 0 then plays there. After Player 1’s third move, Player 0 wins by playing at A_{21} if that position is unoccupied. So assume instead that Player 1 has played there. Thus of Player 1’s three moves so far, two are at A_{11} and A_{21}. Hence for i equal to one of 1 or 3, and for j equal to one of 2 or 3, the following are both true:

(a) The 2 × 2 submatrix formed by rows 2 and i and by columns 2 and 3 contains two zeroes and two empty positions.

(b) Column j contains one zero and two empty positions.

Player 0 next plays at A_{ij}. To prevent a zero column, Player 1 must play in column j, upon which Player 0 completes the 2 × 2 submatrix in (a) for the win. Note: one can also solve this problem directly by making a tree of possible play sequences. This tree can be considerably collapsed using symmetries: the symmetry between rows and columns, the invariance of the outcome under reordering of rows or columns, and the fact that the scenario after a sequence of moves does not depend on the order of the moves (sometimes called “transposition invariance”). Note (communicated by Richard Stanley): one can reduce Determinant Tic-Tac-Toe to ordinary tic-tac-toe! Namely, consider a tic-tac-toe grid labeled as follows:

\begin{matrix}A_{11} & A_{22} & A_{33} \\ A_{23} & A_{31} & A_{12} \\ A_{32} & A_{13} & A_{21} \end{matrix}

Then each term in the expansion of the determinant occurs in a row or column of the grid. Since tic-tac-toe is known to be a draw, Player 0 can prevent any row or column in the tic-tac-toe grid from containing three 1s, and so force the determinant to be zero. Observe that this gives a winning strategy for Player 0 different from the one given above.

A5 It suffices to prove that for any relatively prime positive integers r, s, there exists an integer n with a_{n} = r and a_{n+1} = s. We prove this by induction on r +s, the case r + s = 2 following from the fact that a_{0} = a_{1} = 1. Given r and s not both 1 with gcd(r, s) = 1, we must have r ≠ s. If r > s, then by the induction hypothesis we have a_{n} = r − s and a_{n+1} = s for some n; then a_{2n+2} = r and a_{2n+3} = s. If r < s, then we have a_{n} = r and a_{n+1} = s − r for some n; then a_{2n+1} = r and a_{2n+2} = s.

Note: a related problem is as follows. Starting with the sequence

\frac{0}{1}, \frac{1}{0},

repeat the following operation: insert between each pair \frac{a}{b} and \frac{c}{d} the pair \frac{a+c}{b+d}. Prove that each positive rational number eventually appears.

Observe that by induction, if \frac{a}{b} and \frac{c}{d} are consecutive terms in the sequence, then bc − ad = 1. The same holds for consecutive terms of the n-th Farey sequence, the sequence of rational numbers in [0, 1] with denominator (in lowest terms) at most n.

A6 The sum converges for b = 2 and diverges for b ≥ 3. We first consider b ≥ 3. Suppose the sum converges; then the fact that f(n) = nf(d) whenever b^{d−1} ≤ n ≤ b^{d} − 1 yields

∑_{n=1}^{∞} \frac{1}{f(n)} = ∑_{d=1}^{∞} \frac{1}{f(d)} ∑_{n=b^{d−1}}^{b^{d}−1} \frac{1}{n}.  (1)

However, by comparing the integral of 1/x with a Riemann sum, we see that

∑_{n=b^{d−1}}^{b^{d}−1} \frac{1}{n} > ∫_{b^{d−1}}^{b^{d}} \frac{dx}{x}
= log(b^{d}) − log(b^{d−1}) = log b,

where log denotes the natural logarithm. Thus (1)yields

∑_{n=1}^{∞} \frac{1}{f(n)} > (log b) ∑_{n=1}^{∞} \frac{1}{f(n)},

a contradiction since log b > 1 for b ≥ 3. Therefore the sum diverges.

For b = 2, we have a slightly different identity because f(2) ≠ 2f(2). Instead, for any positive integer i, we have

∑_{n=1}^{2^{i}−1} \frac{1}{f(n)} = 1 + \frac{1}{2} + \frac{1}{6} + ∑_{d=3}^{i} \frac{1}{f(d)} ∑_{n=2^{d−1}}^{2^{d}−1} \frac{1}{n}. (2)

Again comparing an integral to a Riemann sum, we see that for d ≥ 3,

∑_{n=2^{d−1}}^{2^{d}−1} \frac{1}{n} < \frac{1}{2^{d−1}} − \frac{1}{2^{d}} + ∫_{2^{d−1}}^{2^{d}} \frac{dx}{x}

= \frac{1}{2^{d}} + log 2

≤ \frac{1}{8} + log 2 < 0.125 + 0.7 < 1.

Put c = \frac{1}{8} +log 2 and L = 1+ \frac{1}{2} + \frac{1}{6(1−c)}. Then we can

prove that ∑_{n=1}^{2^{i}−1} \frac{1}{f(n)} < L for all i ≥ 2 by induction on i. The case i = 2 is clear. For the induction, note that by (2),

∑_{n=1}^{2^{i}−1} \frac{1}{f(n)} < 1 + \frac{1}{2} + \frac{1}{6} + c ∑_{d=3}^{i} \frac{1}{f(d)}

< 1 + \frac{1}{2} + \frac{1}{6} + c\frac{1}{6(1 − c)}

= 1 + \frac{1}{2} + \frac{1}{6(1 − c)} = L,

as desired. We conclude that ∑_{n=1}^{∞} \frac{1}{f(n)} converges to a limit less than or equal to L.

Note: the above argument proves that the sum for b = 2 is at most L < 2.417. One can also obtain a lower bound by the same technique, namely 1 + \frac{1}{2} + \frac{1}{6(1−c′)} with c′ = log 2. This bound exceeds 2.043. (By contrast, summing the first 100000 terms of the series only yields a lower bound of 1.906.) Repeating the same arguments with d ≥ 4 as the cutoff yields the upper bound 2.185 and the lower bound 2.079.

B1 The probability is 1/99. In fact, we show by induction on n that after n shots, the probability of having made any number of shots from 1 to n − 1 is equal to 1/(n − 1). This is evident for n = 2. Given the result for n, we see that the probability of making i shots after n + 1 attempts is

\frac{i − 1}{n} \frac{1}{n − 1} + (1 − \frac{i}{n}) \frac{1}{n − 1} = \frac{(i − 1) + (n − i)}{n(n − 1)}

= \frac{1}{n},

as claimed.

B2 (Note: the problem statement assumes that all polyhedra are connected, so we will do likewise.) We show that in fact the first player can win on the third move. Suppose the polyhedron has a face A with at least four edges. If the first player plays there first, after the second player’s first move there will be three consecutive faces B, C, D adjacent to A which are all unoccupied. The first player wins by playing in C; after the second player’s second move, at least one of B and D remains unoccpied, and either is a winning move for the first player. It remains to show that the polyhedron has a face with at least four edges. Recall that the numbers V, E, F of vertices, edges and faces of a polyhedron satisfy the relation V − E + F = 2 − 2g by Euler’s Formula, where g is the genus (informally, the number of “holes”) of the polyhedron. Moreover, since the polyhedron is connected, g ≥ 0, so V − E + F ≤ 2. We are given that each vertex lies on three edges, so E = 3V/2. It follows that F ≤ 2 + V/2. For V ≥ 5, we have 2 + V/2 < V, so F < 3V/3. Since each vertex lies on three faces, it follows that at least one face must have more than three vertices. As noted above, this implies that the first player has a winning strategy.

B3 The desired inequalities can be rewritten as

1 − \frac{1}{n} < exp (1 + n log (1 − \frac{1}{n})) < 1 − \frac{1}{2n}.

By taking logarithms, we can rewrite the desired inequalities as

− log (1 − \frac{1}{2n}) < −1 − n log (1 − \frac{1}{n})

< − log (1 − \frac{1}{n}) .

Rewriting these in terms of the Taylor expansion of − log(1−x), we see that the desired result is also equivalent to

∑_{i=1}^{∞} \frac{1}{i2^{i}n^{i}} < ∑_{i=1}^{∞} \frac{1}{(i + 1)n^{i}} < ∑_{i=1}^{∞} \frac{1}{in^{i}} ,

which is evident because the inequalities hold term by term.

B4 Use the following strategy: guess 1, 3, 4, 6, 7, 9, … until the target number n is revealed to be equal to or lower than one of these guesses. If n ≡ 1 (mod 3), it will be guessed on an odd turn. If n ≡ 0 (mod 3), it will be guessed on an even turn. If n ≡ 2 (mod 3), then n + 1 will be guessed on an even turn, forcing a guess of n on the next turn. Thus the probability of success with this strategy is 1335/2002 > 2/3. Note: for any positive integer m, this strategy wins with probability \frac{1}{m}⌊\frac{2m+1}{3}⌋. We can prove that this is best possible as follows. Let a_{m} denote m times the probability of winning when playing optimally. Also, let b_{m} denote m times the corresponding probability of winning if the objective is to select the number in an even number of guesses instead. (For definiteness, extend the definitions to incorporate a_{0} = 0 and b_{0} = 0.) We first claim that a_{m} = 1+max_{1≤k≤m}{b_{k−1}+b_{m−k}} and b_{m} = max_{1≤k≤m}{a_{k−1} + a_{m−k}} for m ≥ 1. To establish the first recursive identity, suppose that our first guess is some integer k. We automatically win if n = k, with probability 1/m. If n < k, with probability (k − 1)/m, then we wish to guess an integer in [1, k − 1] in an even number of guesses; the probability of success when playing optimally is b_{k−1}/(k − 1), by assumption. Similarly, if n < k, with probability (m−k)/m, then the subsequent probability of winning is b_{m−k}/(m − k). In sum, the overall probability of winning if k is our first guess is (1 + b_{k−1} + b_{m−k})/m. For optimal strategy, we choose k such that this quantity is maximized. (Note that this argument still holds if k = 1 or k = m, by our definitions of a_{0} and b_{0}.) The first recursion follows, and the second recursion is established similarly. We now prove by induction that a_{m} = ⌊(2m + 1)/3⌋ and b_{m} = ⌊2m/3⌋ for m ≥ 0. The inductive step relies on the inequality ⌊x⌋ + ⌊y⌋ ≤ ⌊x + y⌋, with equality when one of x, y is an integer. Now suppose that a_{i} = ⌊(2i + 1)/3⌋ and b_{i} = ⌊2i/3⌋ for i < m. Then

1 + b_{k−1} + b_{m−k} = 1 + ⌊\frac{2(k − 1)}{3}⌋ + ⌊\frac{2(m − k)}{3}⌋

≤ ⌊\frac{2m}{3}⌋

and similarly a_{k−1} + a_{m−k} ≤ ⌊(2m + 1)/3⌋, with equality in both cases attained, e.g., when k = 1. The inductive formula for a_{m} and b_{m} follows.

B5 (due to Dan Bernstein) Put N = (2002!)^{2}. Then for d = 1, …, 2002, the number N written in base b = N/d − 1 has digits d^{2}, 2d^{2}, d^{2}. (Note that these really are digits because 2(2002)^{2} < (2002!)^{2}/2002−1.) Note: one can also produce an integer N which has base b digits 1, ∗, 1 for n different values of b, as follows. Choose c with 0 < c < 2^{1/n}. For m a large positive integer, put N = 1+(m+1) ⋯ (m+n)⌊cm⌋^{n−2}. For m sufficiently large, the bases

b = \frac{N − 1}{(m + i)m^{n−2}} = ∏_{j≠i}(m + j)

for i = 1, …, n will have the properties that N ≡ 1 (mod b) and b^{2} < N < 2b^{2} for m sufficiently large.

B6 We prove that the determinant is congruent modulo p to

x ∏_{i=0}^{p−1}(y + ix) ∏_{i,j=0}^{p−1}(z + ix + jy).  (3)

We first check that

∏_{i=0}^{p−1}(y + ix) ≡ y^{p} − x^{p−1}y (mod p). (4)

Since both sides are homogeneous as polynomials in x and y, it suffices to check (4) for x = 1, as a congruence between polynomials. Now note that the right side has 0, 1, …, p − 1 as roots modulo p, as does the left side. Moreover, both sides have the same leading coefficient. Since they both have degree only p, they must then coincide. We thus have

x ∏_{i=0}^{p−1}(y + ix) ∏_{i,j=0}^{p−1}(z + ix + jy)

≡ x(y^{p} − x^{p−1}y) ∏_{j=0}^{p−1}((z + jy)^{p} − x^{p−1}(z + jy))

≡ (xy^{p} − x^{p}y) ∏_{j=0}^{p−1}(z^{p} − x^{p−1}z + jy^{p} − jx^{p−1}y)

≡ (xy^{p} − x^{p}y)((z^{p} − x^{p−1}z)^{p}

− (y^{p} − x^{p−1}y)^{p−1}(z^{p} − x^{p−1}z))

≡ (xy^{p} − x^{p}y)(z^{p^{2}} − x^{p^{2}−p}z^{p})

− x(y^{p} − x^{p−1}y)^{p}(z^{p} − x^{p−1}z)

≡ xy^{p}z^{p^{2}} − x^{p}yz^{p^{2}} − x^{p^{2}−p+1}y^{p}z^{p} + x^{p^{2}}yz^{p}

− xy^{p^{2}}z^{p} + x^{p^{2}−p+1}y^{p}z^{p} + x^{p}y^{p^{2}}z − x^{p^{2}}y^{p}z

≡ xy^{p}z^{p^{2}} + yz^{p}x^{p^{2}} + zx^{p}y^{p^{2}}

− xz^{p}y^{p^{2}} − yx^{p}z^{p^{2}} − zy^{p}x^{p^{2}}, which is precisely the desired determinant. Note: a simpler conceptual proof is as follows. (Everything in this paragraph will be modulo p.) Note that for any integers a, b, c, the column vector [ax + by + cz, (ax + by + cz)^{p}, (ax + by + cz)^{p^{2}}] is a linear combination of the columns of the given matrix. Thus if ax + by + cz = 0, then the determinant is also zero. This means all of the factors of (3) divide the determinant; since both (3) and the determinant have degree p^{2} + p + 1, they agree up to a scalar multiple. Moreover, they have the same coefficient of z^{p^{2}}y^{p}x (since this term only appears in the expansion of (3) when you choose the first term in each factor). Thus the determinant is congruent to (3), as desired. Either argument can be used to generalize to a corresponding n × n determinant, called a Moore determinant; we leave the precise formulation to the reader. Note the similarity with the classical Vandermonde determinant: if A is the n × n matrix with A_{ij} = x_{i}^{j} for i, j = 0, …, n − 1, then

det(A) = ∏_{1≤i<j≤n}(x_{j} − x_{i}).