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

POLYA034:  (2002 Putnam B-Problems, 12/7/02).

[Putnam 2002: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 the shots she has hit so far. What is the probability she hits exactly 50 of her first 100 shots?
[Putnam 2002: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.
[Putnam 2002:B3] Show that for all integers n>1,
1/(2ne)  <  1/e - (1-1/n)^n  <  1/(ne).
[Putnam 2002:B4]
An integer n, unknown to you, has been randomly chosen in the interval [1, 2002] with uniformly 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.
[Putnam 2002: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.
[Putnam 2002:B6]
Let p be a prime number. Prove that the determinant of the matrix

x              y             z
x^p         y^p         z^p
x^(p^2)  y^(p^2)  z^(p^2)

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

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

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

Discussion.  [Putnam 2002: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 the shots she has hit so far. What is the probability she hits exactly 50 of her first 100 shots?

[SCL, 12/8/02]: Let P(n,k) denote the probability that the player has exactly k baskets after n throws. Once one notices that P(n,k)=1/(n-1) for 1<=k<=n-1, the rest is a trivial proof by induction.

[JPE, 12/9/02]: Suppose that the probability to have k hits after n shots (where 0<k<n) is 1/(n-1). This is true for n =2.
Then the probality to have k hits after n+1 shots will be (1-k/n)/(n-1) + (k-1)/n/(n-1) = 1/n. Hence the answer is 1/99.

[FvL, 12/9/02]: To calculate the we start by calculating the probability per shot.
For  each seperate shot, from the third shot, the probability
* for a hit is the number of preceding hits divided by the number of  preceding shots
* for a miss is the number of preceding misses divided by the number of  preceding shots.
Of course the first two shots are left out. So for each string of 49 misses and 49 hits the probability is (49!)^2/99!.
The number of possible strings of 49 misses and 49 hits is of course 98 nCr 49 = 98!/(49!)^2
We conclude that the requested probability is (49!)^2/99! * 98!/(49!)^2 = 1/99.

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

[Putnam 2002: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.

[SCL, 12/8/02]:  If there is a face with at least four edges, Player 1 should take such a face F0, with edges e1,e2,...,k,  with corresponding neighbours F1, F2, ...., Fl. If Player 2 takes a face adjacent to F0, then, we may assume this F1 (relabelling the edges and faces, if necessary). Now, Player 1 takes F3, and Player 2 cannot prevent Player 1 from taking one of F2 or F4 on his next turn.
(The same strategy works if Player 2 does not take a face adjacent to F0. Player 1 can still take F3, although any other face would do as well.)
If the polyhedron has no faces of degree four or more, then every face is a triangle, and since the vertices all have degree three, we know that the polyhedron is the tetrahedron, which was forbidden, since there must be at least five faces.
If one feels it is necessary to prove that the polyhedron is the tetrahedron, one can haul out Euler's formula. v-e+f=2, where v is the number of vertices, f the number of faces, and e the number of edges.
Since 2e=3f if every face is a triangle and 2e=3v if every vertex has degree three, we therefore have v=f=2e/3, and 2=v-e+f=e/3. hence, e=6, v=4, and f=4.

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

[Putnam 2002:B3] Show that for all integers n>1,  1/(2ne)  <  1/e - (1-1/n)^n  <  1/(ne).

[JPE, 12/9/02]:  For x>1 let f(x) = ln(1-1/x)+1/(x-1) and g(x) = x ln(1-1/x)-ln(1-1/2/x)+1
f'(x) = -1/x/(x-1)^2; as limit(f(x),x=infi) = 0, it follows that f(x)>0 and 1/e-(1-1/n)^n < 1/n/e
g'(x) = ln(1-1/x)+(2x^2-2x+1)/x/(x-1)/(2x-1)
g''(x) = -(5x^2-5x+1)/x^2/(x-1)^2/(2x-1)^2 <0
As limit(g'(x),x=infi) = 0, we have g'(x)>0.
As limit(g(x),x=infi) = 0, we have g(x)<0 and
1/e-(1-1/n)^n>1/2/n/e.

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

[Putnam 2002:B4]  An integer n, unknown to you, has been randomly chosen in the interval [1, 2002] with uniformly 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.

[JPE, 12/9/02]: I hope that I've well understood the statement : I mean that, if I discover n in an even number of steps, I lose.
In this case, it is quite easy : for p>0, I propose 3p-2 at step 2p-1 and 3p at step 2p, ie 1,3,4,6,7,9,10,12,...until my guess is equal or greater than n.
This way, n will be discovered in an odd number of steps except if 3 divides n.
Hence, the chance of winning is 2/3+1/6006.

[SCL,12/9/02]: I don't have a solution yet, but I can see something like the following, which might lead to a solution with an appropriate adjustment of step sizes.

One can prove fairly easily that when there are three elements left, taking the minimum or the maximum gives a 2/3 chance of taking an odd number of moves, and taking the middle gives a 2/3 chance of taking an even number of moves.

Thus, one could attack the larger list of 2002, by taking the fourth element (or the (n-3)rd). If the target is in the short list, we can finish with a probability of 2/3 to get the parity correct. If it is in the larger list, we will repeat the process. Just doing this will not quite get us the 2/3 probability overall. You can do slightly  better if an even number of moves are required at the point you are making a guess. Take a guess which separates 4 elements from the list (choose element five or n-4). If you are forced into the  short list of four elements, there is a 3/4 probability of getting it in an odd number of moves from that point.

Perhaps somebody diligent could work out the probability that best play for a list of length n gets the solution in an odd  number of moves, and the probability that best play (necessarily different from the strategy for using an odd number of moves) for a list of length n gets the solution in an off number of moves. Perhaps there is a better size to break off than 3 for both cases.

[JPE, 12/9/02]: Here is a quite similar exercise, but with a quite different conclusion (I hope that the statement is correct).

An integer n, unknown to you, has been randomly chosen in the interval [1,2002] with uniformly probability. Your objective is to select n in an EVEN 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, for every strategy, the chance of winning is < 2/3.

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

[Putnam 2002: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.

[JPE, 12/9/02]: d,n are integers with n>5 and 1<=d<=n.
If b = n!/d-1, we have
n!^2 = d^2(1+b)^2 = d^2 + 2d^2b + d^2b^2;
as n(2n^2+1)<n!, we have 2d^2<b; hence n!^2 is a 3-digit palindrom in n different bases.

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

[Putnam 2002:B6] Let p be a prime number. Prove that the determinant of the matrix

x              y             z
x^p         y^p         z^p
x^(p^2)  y^(p^2)  z^(p^2)

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

[SCL, 12/7/02]: I admit to a bit of confusion reading this one at first. Since w^p is congruent to w mod p, for any integer w, the determinant is identically zero modulo p. Thus, it would seem that an answer of the form "the determinant is 0x+0y+0z" would seem to be in order. However, I expect that what the proposers wanted was that one expand the determinant as polynomial d(x,y,z) and show a product q(x,y,z) of linear polynomials with degree(q)=degree(d) and q-d = 0  modulo p.
Another way to write something which is identically zero modulo p, is to take the product of all of the polynomial of the form ax+by+cz (think of these as hyperplanes), and then to realize that one only needs the planes where (a,b,c) is of the form (1,b,c), (0,1,b) or (0,0,1). This leaves a product q(x,y,z) of p^2+p+1 trinomials (some degenerate) which is exactly the number needed since the terms of the expansion of the determinant are all of combined power p^2+p+1.
The only remaining step is to adjust the constant, since the product of the specified trinomials is of the correct degree and has the same zeroes as the determinant. Our polynomial q(x,y,z) has coefficient +1 on the term x^{p^2}y^{p}z, while this term in d(x,y,z) is negative. We need to multiply by negative one.

[JPE, 12/9/02]:  Let D(x,y,z) be the given determinant and P(x,y,z) be the product of the p^2
+ p + 1 following linear polynomials
z - a x -b y for 0<=a<p-1 and 0<=b<p-1
y - c x for 0<=c<p-1
x
If we substitute z = a x + b y or y = c x or x = 0 in D, the result will be
0 mod p.
Hence P divides D modulo p.
But the degree of the determinant is p^2 + p + 1 and the coefficient of x y^p z^(p^2) is 1 in both D and P.
Hence D and P are congruent modulo p.

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

Bibliography.

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