POLYA033:  (2002 Putnam A-Problems, 12/7/02).

[Putnam 2002:A1] Let k be a fixed positive integer. The n-th derivative of   1/(x^k-1) has the form P_n(x)/(x^k-1)^{n+1} where P_n(x) is a polynomial. Find P_n(1).
[Putnam 2002:A2] Given any five points on  a sphere, show that some four of them must lie on a closed hemisphere.
[Putnam 2002:A3] Let n>= 2 be an integer and T_n be the number of nonempty subsets of S = {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.
[Putnam 2002:A4]  In Determinant Tic-Tac-Toe, Player 1 enters a 1 in an empty 3 by 3 matrix. Player 0 counters with a 0 in a vacant position, and play continues in turn until the 3 by 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?
[Putnam 2002: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  {a_{n-1}/a_n: n >= 1 } = {1/1, 1/2, 2/1, 1/3, 3/2, ... }.
[Putnam 2002:A6] Fix an integer b >= 2. Let  f(1) = 1, f(2) = 2, and for each n >= 3, define f(n) = n f(d), where d is the number of base-b digits of n. For which values of b does  
Sum_{n=1,...  infty} 1/f(n) converge?

[TS, 12/14/02]:  [ps] [pdf]

**********************************************************************************************************
Discussion. [Problem A1]  Let k be a fixed positive integer. The n-th derivative of   1/(x^k-1) has the form 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.

[SCL, 12/8/02]: Take the great circle C through any two points. (If all five points are identical, we are obviously done.) C divides the surface of the sphere, S, into two regions R and T. There are (at most) three points in R union T, and thus, without loss of generality, T has at most one point. Therefore, R union C is a closed hemisphere containing at least four of the points.

[JPE, 12/8/02]: If P is a plane through the center of the sphere and two of the given points, obviously, two at least of the three other points lie on one of the closed hemispheres limited by P.

***********************************************************************************************
[Problem A3] Let n>= 2 be an integer and T_n be the number of nonempty subsets of S = {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.

[JPE, 12/8/02]: Let E be the set of the subsets S of {1,2,..n} such that
    - S has at least 2 elements
    - the average m(S) of the elements of S is an integer.
Let E1 (resp E2) be the set of the elements S of E such that  m(S) is (resp is not) an element of S.
The mapping  u| S -> S union {m(S)} is a bijection from E2 to E1 ( with reciprocal bijection S -> S-{m(S)}).
As E = E1 union E2 has T_n - n elements, the result follows.

***********************************************************************************************
[Problem A4]  In Determinant Tic-Tac-Toe, Player 1 enters a 1 in an empty 3 by 3 matrix. Player 0 counters with a 0 in a vacant position, and play continues in turn until the 3 by 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?

[SCL, 12/7/02]: If Player 2 can get 3 zeroes in a row, horizontally or vertically, he will win. He will also win if he can get some $2\times 2$ submatrix of zeroes, since then there is either a row or all zeroes, or two identical rows. There is one more way to get two identical rows (or columns), and that is if each has exactly one zero and that is in the same column (row) for both rows (columns).
 Since we are only interested in whether or not the determinant the determinant is zero, we can rearrange rows and columns and take transposes as needed without changing this property. Thus, without loss of generality, Player 1 moves into cell (1,1). Player 2 has, up to rearrangements, two possible responses: He can move to cell (1,2) or to cell (2,2).
Let us analyze the case in which Player 2 takes the cell (2,2) (since this is sufficient). There are now, up to symmetries, four possibilities for Player 1: cells (1,2),(1,3),(2,3),(3,3). We will assume that Player 1, whenever possible will move to block if Player 2 has a row with two zeroes, and that Player 2 will move to win if he already has a row with two zeroes. With these caveats, here are the responses for Player 2 in each of the remaining four situations. As can now be seen, Player 2 can force a win by creating a $2\times 2$ submatrix of zeroes.
Responses to (1,2): Player 2 now takes (2,3), (3,3), (3,2) in this order.
Responses to (1,3): Player 2 now takes (2,3), (3,2), (3,3) in this order.
Responses to (2,3): Player 2 now takes (3,2), then (3,1), then (2,1).
Responses to (3,3): Player 2 now takes (1,2), then (2,3), then (1,3).

[ND, 12/10/02] (with minor corrections on 12/11/02):  We''ll prove that the second player wins.
Interchanging rows and columns we can call the element the first player selects A1. The rows now are Ai, Bi, Ci, i = 1, 2, 3 and the expansion of the determinant is
D = A1B2C3-A1B3C2͠看A2B1C3Ͱ甋A3B2C1.
The second player selects C3 = 0 and again one of its neighbors say C2 = 0. Now the only terms in D that are not zero are
T1 = A2B3C1 and T2 = -A3B2C1 and the best case for the first player is to be C1 = 1.
Hence whatever the first player selects, the second player can make zero both terms T1, T2 in his third and fourth selection.

***********************************************************************************************
[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
{a_{n-1}/a_n: n >= 1 } = {1/1, 1/2, 2/1, 1/3, 3/2, ... }.

[SCL, 12/8/02]:  I think I have seen something like this problem before (Donald Knuth, Monthly Problem10906, November 2001). The function was different, but the conclusion the same: every positive rational shows up exactly once.
In that problem, p(k) is the power of 2 in k: that is 2^s divides k and 2^{s+1} does not means p(k)=s. Then the sequence generated is x_0=0, x_n=1/(1+2p(n)-x_{n-1}).
The rationals appear to be generated in exactly the same sequence for both problems (with the exception of the term x_0). thus, a reasonable conjecture is that x(n)=a(n-1)/a(n) for n>=1. This may help in getting a proof.

***********************************************************************************************
[Problem A6]  Fix an integer b >= 2. Let  f(1) = 1, f(2) = 2, and for each n >= 3, define f(n) = n f(d), where d is the number of base-b digits of n. For which values of b does  Sum_{n=1,...  infty} 1/f(n) converge?

 ***********************************************************************************************

Bibliography.
 
 
 

Return to [ Polya Home Page ] [Members ] [The Problems ] [Inventory ] [Reserve Area ]