SIXTY-THIRD ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 7, 2002 Examination A

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

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

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.

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?

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}, ⋯\} .

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?

SIXTY-THIRD ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 7, 2002 Examination B

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 that she hits exactly 50 of her first 100 shots?

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.

B3. Show that, for all integers n > 1,

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

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.

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 0, 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.

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