### 63rd Putnam 2002

 A1.  k and n are positive integers. Let f(x) = 1/(xk - 1). Let p(x) = (xk - 1)n+1 fn(x), where fn is the nth derivative. Find p(1). A2.  Given any 5 distinct points on the surface of a sphere, show that we can find a closed hemisphere which contains at least 4 of them. A3.  A subset of {1, 2, ... , n} is round if it is non-empty and the average (arithmetic mean) of its elements is an integer. Show that the number of round subsets of {1, 2, ... , n} has the same parity as n. A4.  Two players play a game on a 3 x 3 board. The first player places a 1 on an empty square and the second player places a 0 on an empty square. Play continues until all squares are occupied. The second player wins if the resulting determinant is 0 and the first player wins if it has any other value. Who wins? A5.  The sequence un is defined by u0 = 1, u2n = un + un-1, u2n+1 = un. Show that for any positive rational k we can find n such that un/un+1 = k. A6.  b > 1 is an integer. For any positive integer n, let d(n) be the number of digits in n when it is written in base b. Define the sequence f(n) by f(1) = 1, f(2) = 2, f(n) = n f( d(n) ). For which values of b does 1/f(1) + 1/f(2) + 1/f(3) + ... converge? B1.  An event is a hit or a miss. The first event is a hit, the second is a miss. Thereafter the probability of a hit equals the proportion of hits in the previous trials (so, for example, the probability of a hit in the third trial is 1/2). What is the probability of exactly 50 hits in the first 100 trials? B2.  A polyhedron has at least 5 faces, and it has exactly 3 edges at each vertex. Two players play a game. Each in turn selects a face not previously selected. The winner is the first to get three faces with a common vertex. Show that the first player can always win. B3.  Show that for any integer n > 1, we have 1/e - 1/(ne) < (1 - 1/n)n < 1/e - 1/(2ne). B4.  One of the integers in {1, 2, ... , 2002} is selected at random (with each integer having a chance 1/2002 of being selected). You wish to guess the correct integer in an odd number of guesses. After each guess you are told whether the actual integer is less than, equal to, or greater than your guess. You are not allowed to guess an integer which has already been ruled out by the earlier answers. Show that you can guess in such a way that you have a chance > 2/3 of guessing the correct integer in an odd number of guesses. B5.  A base b palindrome is an integer which is the same when read backwards in base b. For example, 200 is not a palindrome in base 10, but it is a palindrome in base 9 (242) and base 7 (404). Show that there is an integer which for at least 2002 values of b has three digits and is a palindrome. B6.  Let p be prime and q = p2. Let D be the determinant: ``` x y z xp yp zp xq yq zq ``` Show that we can find a set of linear polynomials ax + by + cz (with a, b, c integers) whose product Q equals D mod p. (In other words, after expansion the corresponding coefficients of Q and D are equal mod p.)

To avoid possible copyright problems, I have changed the wording, but not the substance, of all the problems.

Putnam home