Putnam Mathematical Competition, 7 December 2002

Problem A1 Let k be a fixed positive integer. The nth derivative of \frac{1}{x^{k} − 1} has the form \frac{P_{n}(x)}{(x^{k} − 1)^{n+1}} where P_{n}(x) is a polynomial. Find P_{n}(1). Problem A2 Given any five points on a sphere, show that some four of them must lie on a closed hemisphere. Problem A3 Let n ≥ 2 be an integer and T_{n} be the number of non-empty subsets S of {1, 2, 3, …, n} with the property that the average of the elements of S is an integer. Prove that T_{n} − n is always even. Problem A4 In Determinant Tic-Tac-Toe, Player 1 enters a 1 in an empty 3 × 3 matrix. Player 0 counters with a 0 in a vacant position, and play continues in turn until the 3 × 3 matrix is completed with five 1’s and four 0’s. Player 0 wins if the determinant is 0 and player 1 wins otherwise. Assuming both players pursue optimal strategies, who will win and how? Problem A5 Define a sequence by a_{0} = 1, together with the rules a_{2n+1} = a_{n} and a_{2n+2} = a_{n} + a_{n+1} for each integer n ≥ 0. Prove that every positive rational number appears in the set

\{\frac{a_{n−1}}{a_{n}} : n ≥ 1\} = \{\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, …\} .

Problem A6 Fix an integer b ≥ 2. Let f(1) = 1, f(2) = 2, and for each n ≥ 3, define f(n) = nf(d), where d is the number of base-b digits of n. For which values of b does

∑_{n=1}^{∞} \frac{1}{f(n)}

converge?

Problem B1

Shanille O’Keal shoots free throws on a basketball court. She hits the first and misses the second, and thereafter the probability that she hits the next shot is equal to the proportion of shots she has hit so far. What is the probability she hits exactly 50 of her first 100 shots?

Problem B2

Consider a polyhedron with at least five faces such that exactly three edges emerge from each of its vertices. Two players play the following game:

Each player, in turn, signs his or her name on a previously unsigned face. The winner is the player who first succeeds in signing three faces that share a common vertex.

Show that the player who signs first will always win by playing as well as possible.

Problem B3

Show that, for all integers n > 1,

\frac{1}{2ne} < \frac{1}{e} − (1 − \frac{1}{n})^{n} < \frac{1}{ne}.

Problem B4

An integer n, unknown to you, has been randomly chosen in the interval [1, 2002] with uniform probability. Your objective is to select n in an odd number of guesses. After each incorrect guess, you are informed whether n is higher or lower, and you must guess an integer on your next turn among the numbers that are still feasibly correct. Show that you have a strategy so that the chance of winning is greater than 2/3.

Problem B5

A palindrome in base b is a positive integer whose base-b digits read the same backwards and forwards; for example, 2002 is a 4-digit palindrome in base 10. Note that 200 is not a palindrome in base 10, but it is the 3-digit palindrome 242 in base 9, and 404 in base 7. Prove that there is an integer which is a 3-digit palindrome in base b for at least 2002 different values of b.

Problem B6

Let p be a prime number. Prove that the determinant of the matrix

( \begin{matrix}x & y & z \\ x^{p} & y^{p} & z^{p} \\ x^{p^{2}} & y^{p^{2}} & z^{p^{2}} \end{matrix} )

is congruent modulo p to a product of polynomials of the form ax + by + cz, where a, b, c are integers. (We say two integer polynomials are congruent modulo p if corresponding coefficients are congruent modulo p.)

Solutions

D. J. Bernstein, 8 December 2002

Problem A1

Let k be a fixed positive integer. The nth derivative of \frac{1}{x^{k} − 1} has the form \frac{P_{n}(x)}{(x^{k} − 1)^{n+1}}

where P_{n}(x) is a polynomial. Find P_{n}(1).

Solution: If n ≥ 1 then (x^{k} − 1)^{−n−1}P_{n}(x) is the derivative of (x^{k} − 1)^{−n}P_{n−1}(x), namely (x^{k} − 1)^{−n}P′_{n−1}(x) − n(x^{k} − 1)^{−n−1}kx^{k−1}P_{n−1}(x). Multiply by (x^{k} − 1)^{n+1} to see that P_{n}(x) = (x^{k} − 1)P′_{n−1}(x) − nkx^{k−1}P_{n−1}(x). Substitute x = 1 to see that P_{n}(1) = −nkP_{n−1}(1). By induction P_{n}(1) = n!(−k)^{n}P_{0}(1) = n!(−k)^{n}.

Problem A2

Given any five points on a sphere, show that some four of them must lie on a closed hemisphere.

Solution: More generally, consider any n + 2 points in an n-ball. There must be n + 1 points in a closed half n-ball.

Indeed, for n = 1, consider 3 points in the 1-ball, i.e., the interval [−1, 1]. There must be 2 points in [−1, 0], or 2 points in [0, 1].

For n ≥ 2, select one point p, and select an axis of the n-ball through p. (Any axis works if p is at the center; otherwise the axis is determined by p.) Project the n-ball along that axis onto an (n − 1)-ball. By induction, out of the other n + 1 points, there are n whose projections are in a closed half (n − 1)-ball. The inverse image of that closed half (n − 1)-ball under the projection is a closed half n-ball containing those n points and containing p.

Problem A3

Let n ≥ 2 be an integer and T_{n} be the number of non-empty subsets S of {1, 2, 3, …, n} with the property that the average of the elements of S is an integer. Prove that T_{n} − n is always even.

Solution: One solution is to count each set S together with its transpose n + 1 − S = {n + 1 − k : k ∈ S}. If n is even then there are no qualifying sets equal to their transpose. If n is odd then the qualifying sets equal to their transpose correspond to nonempty subsets of {1, 2, …, (n + 1)/2}; there are an odd number of these subsets.

Simpler solution from Fred Galvin: Pair each set S not containing its average m with the set S ∪ {m}. This covers all qualifying sets other than the n sets {1} , {2} , …, {n}.

Problem A4

In Determinant Tic-Tac-Toe, Player 1 enters a 1 in an empty 3 × 3 matrix. Player 0 counters with a 0 in a vacant position, and play continues in turn until the 3 × 3 matrix is completed with five 1’s and four 0’s. Player 0 wins if the determinant is 0 and player 1 wins otherwise. Assuming both players pursue optimal strategies, who will win and how?

Solution: Player 0 wins.

Assume without loss of generality that player 1 starts with position 11; otherwise permute the rows and columns. Player 0 counters with 22.

Player 1 must now respond with 12, 13, 21 (analogous to 12 and not discussed further), 23, 31 (analogous to 13), 32 (analogous to 23), or 33. Player 0 counters, as described below, by threatening an all-zero row or column of the matrix; player 1 is forced to immediately occupy the third position in the row or column, exactly as in usual Tic-Tac-Toe, or else player 0 will occupy that position and win.

First case: 12. Player 0 counters with 23, forcing player 1 to respond with 21. Player 0 then plays 33, forcing player 1 to respond with 13. Player 0 finishes with 32, and player 1 finishes with 31.

Second case: 13. Player 0 counters with 32, forcing player 1 to respond with 12. Player 0 then plays 23, forcing player 1 to respond with 21. Player 0 finishes with 33, and player 1 finishes with 31.

Third case: 23. Player 0 counters with 32, forcing player 1 to respond with 12. Player 0 then plays 31, forcing player 1 to respond with 33. Player 0 finishes with 21, and player 1 finishes with 13.

Fourth case: 33. Player 0 counters with 32, forcing player 1 to respond with 12. Player 0 then plays 21, forcing player 1 to respond with 23. Player 0 finishes with 31, and player 1 finishes with 13.

In every case, the final matrix has two equal columns, and therefore has determinant 0.

Problem A5

Define a sequence by a_{0} = 1, together with the rules a_{2n+1} = a_{n} and a_{2n+2} = a_{n} + a_{n+1} for each integer n ≥ 0. Prove that every positive rational number appears in the set

\{\frac{a_{n−1}}{a_{n}} : n ≥ 1\} = \{\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, …\} .

Solution: Write S for this set. I will show by induction on u + v that v/u ∈ S for all positive integers u, v.

If v = u then v/u = 1 = a_{0}/a_{1} ∈ S. If v > u then u+v −u is smaller than u+v so by the inductive hypothesis (v −u)/u ∈ S, i.e., (v − u)/u = a_{n−1}/a_{n} for some n ≥ 1. Then v/u = (a_{n−1} + a_{n})/a_{n} = a_{2n}/a_{2n+1} ∈ S. If v < u then u−v +v is smaller than u+v so by the inductive hypothesis v/(u−v) ∈ S, i.e., v/(u − v) = a_{n−1}/a_{n} for some n ≥ 1. Then v/u = a_{n−1}/(a_{n−1} + a_{n}) = a_{2n−1}/a_{2n} ∈ S.

Problem A6 Fix an integer b ≥ 2. Let f(1) = 1, f(2) = 2, and for each n ≥ 3, define f(n) = nf(d), where d is the number of base-b digits of n. For which values of b does

∑_{n=1}^{∞} \frac{1}{f(n)}

converge? Solution: The sum converges for b = 2 and diverges for b ≥ 3. Observe first that the integral of 1/n for n ∈ [b^{d−1}, b^{d}] is log b. Thus the sum of 1/n for b^{d−1} ≤ n < b^{d} is between log b and log b + b^{1−d}. Case 1: b ≥ 3. Suppose that ∑_{n≥1} 1/f(n) converges. If d ≥ 2 and b^{d−1} ≤ n < b^{d} then n ≥ 3 and n has d base-b digits, so ∑_{b^{d−1}≤n<b^{d}} 1/f(n) = ∑_{b^{d−1}≤n<b^{d}} 1/nf(d) > (log b)/f(d) > 1/f(d) since log b > 1. Thus ∑_{n≥b} 1/f(n) = ∑_{d≥2} ∑_{b^{d−1}≤n<b^{d}} 1/f(n) > ∑_{d≥2} 1/f(d) > ∑_{n≥b} 1/f(n). Contradiction.

Case 2: b = 2. Then ∑_{2^{d−1}≤n<2^{d}} 1/f(n) = ∑_{2^{d−1}≤n<2^{d}} 1/nf(d) < (log 2+2^{1−d})/f(d) < 0.9/f(d) for d ≥ 10. Thus ∑_{2^{9}≤n<2^{d}} 1/f(n) < 0.9 ∑_{10≤n≤d} 1/f(n). By induction ∑_{2^{9}≤n<2^{d}} 1/f(n) < (0.9 + 0.9^{2} + 0.9^{3} + ⋯) ∑_{10≤n<2^{9}} 1/f(n) for all d, so ∑_{2^{9}≤n} 1/f(n) converges.

Problem B1

Shanille O’Keal shoots free throws on a basketball court. She hits the first and misses the second, and thereafter the probability that she hits the next shot is equal to the proportion of shots she has hit so far. What is the probability she hits exactly 50 of her first 100 shots?

Solution: The probability is 1/99. More generally, for each n ≥ 2, the number of shots hit out of the first n is uniformly distributed in {1, 2, …, n − 1}.

Proof by induction on n: For n = 2, the number of shots hit is 1. For n ≥ 3, and for each k ∈ {1, 2, …, n − 1}, the number of shots hit can be k in two disjoint ways:

1. There were k − 1 shots hit out of the first n − 1—probability 1/(n − 2) by the inductive hypothesis, except 0 if k = 1—and the nth shot was hit—conditional probability (k − 1)/(n − 1), and thus probability (k − 1)/(n − 1)(n − 2), even for k = 1.

2. There were k shots hit out of the first n−1—probability 1/(n−2) by the inductive hypothesis, except 0 if k = n − 1—and the nth shot was missed—conditional probability (n − k − 1)/(n − 1), and thus probability (n − k − 1)/(n − 1)(n − 2), even for k = n − 1.

The overall probability is (k − 1 + n − k − 1)/(n − 1)(n − 2) = 1/(n − 1) as claimed.

Problem B2

Consider a polyhedron with at least five faces such that exactly three edges emerge from each of its vertices. Two players play the following game:

Each player, in turn, signs his or her name on a previously unsigned face. The winner is the player who first succeeds in signing three faces that share a common vertex.

Show that the player who signs first will always win by playing as well as possible.

Solution: The first player wins in three moves as follows. (The second player has only two moves, hence cannot win.)

First, sign a face x that has at least 4 edges. (Write V, E, F for the number of vertices, edges, and faces respectively. If every face has 3 edges then E = (3/2)F; but also E = (3/2)V; thus F = 2V − 2E + 2F = 4 by Euler’s formula, contradiction.)

Second, sign a face y adjacent to x, with the following restriction: if the second player signed a face z adjacent to x, choose y so that x, y, z do not share a vertex. (By definition of polyhedron, x and z share only one edge e and no other vertices. Because x has at least 4 edges, it has an edge sharing no vertices with e. Choose y as the other face with that edge.)

Third, sign an unsigned face sharing a vertex with x and y. (There are two vertices shared by x and y, so there are two other faces sharing a vertex with x and y. By construction of y, neither of these two faces is z. At most one of these faces was signed on the second player’s second move.)

In this problem, like most geometry problems, it is unclear what the contestant is required to do. For example, does the contestant have to prove that two faces of a polyhedron adjacent to a single edge cannot share any other vertices? Contestants should not have to guess how their solutions will be graded.

Problem B3

Show that, for all integers n > 1,

\frac{1}{2ne} < \frac{1}{e} − (1 − \frac{1}{n})^{n} < \frac{1}{ne}.

Solution: Define f(x) = x + log(1 − x) − x log(1 − x) for 0 ≤ x < 1. Then f(0) = 0, and f′(x) = − log(1 − x) > 0 for 0 < x < 1, so f(x) > 0 for 0 < x < 1.

Define g(x) = log(1−x/2)+x/(1−x)(2−x). Then g(0) = 0, and ((1−x)(2−x))^{2}g′(x) = x(x^{2} + 5(1 − x)) > 0 for 0 < x < 1, so g(x) > 0 for 0 < x < 1.

Define h(x) = x log(1 − x/2) − x − log(1 − x) for 0 ≤ x < 1. Then h(0) = 0, and h′(x) = g(x) > 0 for 0 < x < 1, so h(x) > 0 for 0 < x < 1.

Thus x log(1 − x) < x + log(1 − x) < x log(1 − x/2) for 0 < x < 1. Substitute x = 1/n, multiply by n, and exponentiate to obtain the desired inequalities.

Another way to prove that x log(1 − x) < x + log(1 − x) < x log(1 − x/2) is to observe that ∑_{n≥1} −x^{n+1}/n < ∑_{n≥2} −x^{n}/n < ∑_{n≥1} −x^{n+1}/n2^{n} termwise.

Problem B4

An integer n, unknown to you, has been randomly chosen in the interval [1, 2002] with uniform probability. Your objective is to select n in an odd number of guesses. After each incorrect guess, you are informed whether n is higher or lower, and you must guess an integer on your next turn among the numbers that are still feasibly correct. Show that you have a strategy so that the chance of winning is greater than 2/3.

Solution: Here is a general strategy to find n in the interval [1, 3k + 1] for k ≥ 0. First guess 3k + 1. If 3k + 1 was too large, guess 3k − 1. If 3k − 1 was too small, guess 3k. If 3k − 1 was too large, recursively find n in the interval [1, 3k − 2].

This strategy finds 2k + 1 integers n, namely the integers congruent to 0 or 1 modulo 3, with an odd number of guesses. Indeed, the strategy finds n = 3k + 1 in 1 guess; for k ≥ 1, it finds n = 3k in 3 guesses; and, for k ≥ 1, it finds 2k − 1 integers in [1, 3k − 2] in an odd number of guesses.

Hence the strategy has a (2k + 1)/(3k + 1) > 2/3 chance of winning. In particular, for k = 667, the strategy wins for the interval [1, 2002] with chance 1335/2002 > 2/3.

Problem B5

A palindrome in base b is a positive integer whose base-b digits read the same backwards and forwards; for example, 2002 is a 4-digit palindrome in base 10. Note that 200 is not a palindrome in base 10, but it is the 3-digit palindrome 242 in base 9, and 404 in base 7. Prove that there is an integer which is a 3-digit palindrome in base b for at least 2002 different values of b.

Solution: One answer is (2002!)^{2}.

The integer (u(b + 1))^{2} = u^{2}b^{2} + 2u^{2}b + u^{2} is a 3-digit palindrome u^{2}, 2u^{2}, u^{2} in base b if 2u^{2} < b. It thus suffices to find an integer that can be factored as u(b + 1) for 2002 different values of b with 2u^{2} < b. For example, the integer 2002! can be factored as u(b + 1) for any u ∈ {1, 2, …, 2002} with b = 2002!/u − 1; obviously 2u^{2} < b.

There are many solutions to this problem. What makes the problem difficult, as with problem B6 in 1998, is the weakness of its conclusion.

Problem B6

Let p be a prime number. Prove that the determinant of the matrix

( \begin{matrix}x & y & z \\ x^{p} & y^{p} & z^{p} \\ x^{p^{2}} & y^{p^{2}} & z^{p^{2}} \end{matrix} )

is congruent modulo p to a product of polynomials of the form ax + by + cz, where a, b, c are integers. (We say two integer polynomials are congruent modulo p if corresponding coefficients are congruent modulo p.)

Solution: Recall that ∏_{0≤a<p}(ax + y) ≡ y^{p} − yx^{p−1} (mod p). Thus

∏_{0≤a<p,0≤b<p}(ax + by + z) ≡ ∏_{b}((by + z)^{p} − (by + z)x^{p−1})

≡ ∏_{b}(b(y^{p} − yx^{p−1}) + z^{p} − zx^{p−1})

≡ (z^{p} − zx^{p−1})^{p} − (z^{p} − zx^{p−1})(y^{p} − yx^{p−1})^{p−1}.

Multiply:

x ∏_{a}(ax + y) ∏_{a,b}(ax + by + z)

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

≡ x(y^{p} − yx^{p−1})(z^{p^{2}} − z^{p}x^{p^{2}−p}) − x(z^{p} − zx^{p−1})(y^{p^{2}} − y^{p}x^{p^{2}−p})

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

= det ( \begin{matrix}x & y & z \\ x^{p} & y^{p} & z^{p} \\ x^{p^{2}} & y^{p^{2}} & z^{p^{2}} \end{matrix} )

as desired.