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).
**********************************************************************************************************
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.*****************************************************************************************************
[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.***********************************************************************************************
Bibliography.
Return to [
Polya Home Page ] [Members ] [The Problems
] [Inventory
] [Reserve
Area ]