POLYA017:  (2001 Putnam A-Problems, 12/1/01).
[Putnam 2001:A1] Consider a set S and a binary operation * on S (that is, for each a, b in S, a*b is in S).  Assume that (a*b)*a = b for all a, b in S. Prove that a*(b*a) = b for all a, b in S.
[Putnam 2001:A2] You have coins C_1, C_2, ..., C_n. For each k, coin C_k is biased so that when tossed, it has probability 1/(2k+1) of  falling heads. If the n coins are tossed, what is the probability that the number of heads is odd? Express the answer as a rational function of n.
[Putnam 2001:A3] For each integer m, consider the polynomial P_m(x) = x^4 - (2m+4)x^2 + (m-2)^2. For what values of m is P_m(x) the product of two nonconstant polynomials with integer  coefficients?
[Putnam 2001:A4]  Triangle ABC has area 1. Points E, F, G lie, respectively, on sides BC, CA, AB such that AE bisects BF at point R,  BF bisects CG at point S, and CG bisects AE at point T. Find the area of triangle RST.
[Putnam 2001:A5] Prove that there are unique positive integers a and n such that  a^(n+1) - (a+1)^n = 2001.
[Putnam 2001:A6] Can an arc of a parabola inside a circle of radius 1 have length greater than 4?

**********************************************************************************************************
Discussion. [Problem A1] Consider a set S and a binary operation * on S (that is, for each a, b in S, a*b is in S).  Assume that (a*b)*a = b for all a, b in S. Prove that a*(b*a) = b for all a, b in S.

[SCL]: a*(b*a)=((b*a)*b)*(b*a)=b.
[LZ]:  For any a, b in S, b=[(b*a)*b]*(b*a)=a*(b*a).
[PY]:  a*(b*a) = [((b*a)*a)*(b*a)]*(b*a) = a*(b*a) = b.

***********************************************************************************************
[Problem A2] You have coins C_1, C_2, ..., C_n. For each k, coin C_k is biased so that when tossed, it has probability 1/(2k+1) of  falling heads. If the n coins are tossed, what is the probability that the number of heads is odd? Express the answer as a rational function of n.

[SCL]: Let f(k) denote the probability that an odd number of the first k coins are tails. Then, f(1)=2/3,  and f(n) = f(n-1)/(2n+1) + 2n(1-f(n-1))/(2n+1).
Calculating a few values, we see that f(n) appears to be (n+1)/(2n+1) if n is odd and n/(2n+1) if n is even. It is now a simple matter of writing out a proof by induction.
If n is even,  f(n) = f(n-1)/(2n+1) + 2n(1-f(n-1))/(2n+1) = n/((2n-1)(2n+1)) + 2n(n-1)/((2n-1)(2n+1)) = (2n^2-n)/((2n-1)(2n+1)) =n/(2n+1).
If n is odd,  f(n) = f(n-1)/(2n+1) + 2n(1-f(n-1))/(2n+1) = (n-1)/((2n-1)(2n_1)) + 2n(n)/((2n-1)(2n+1)) = (2n^2+n-1)/((2n-1)(2n+1)) = (n+1)/(2n+1).

[LZ]:  The problem suggests recursion. Let P_n be the desired probability. Then P_1 = 1/3, and P_n = [1/(2n+1)]*(1-P_{n-1})+[2n/(2n+1)]*P_{n-1} for n>1.
The solution to this recursion is P_n = n/(2n+1).  I solved it using a generating function. But in hindsight, it can be easily guessed too.

[PY]: We make use generating function: For k = 1, 2, ..., n, we consider the linear function t/(2k+1) + (2k)/(2k+1) = (t+2k)/(2k+1).
The probability of tossing an odd number of heads is the sum of the coefficients of odd powers of t in the expansion of
f(t) = ((t+2)/3)((t+4)/5)(t+6)/7)...((t+2n)/(2n+1).
If we put t = 1, we obtain f(1) as the sum of all coefficients. Clearly, f(1) = 1.
If we put t = -1, we obtain f(-1) as the alternating sum of coefficients. Now, f(-1) = (1/3)(3/5)(5/7)...((2n-1)/(2n+1)) = 1/(2n+1).
The sum of coefficients of odd powers of t is therefore  (f(1) - f(-1))/2 =  (1-1/(2n+1))/2 = n/(2n+1).

***********************************************************************************************
[Problem A3] For each integer m, consider the polynomial P_m(x) = x^4 - (2m+4)x^2 + (m-2)^2. For what values of m is P_m(x) the product of two nonconstant polynomials with integer  coefficients?

[SCL]: We can easily find the zeroes of P_m. These are \pm\sqrt{m}\pm\sqrt{2}.
Thus, the question asks for which m can we combine two of the polynomials (x\pm\sqrt{m}\pm\sqrt{2}) to get integer coefficients. We might as well assume that (x+\sqrt{m}+\sqrt{2}) is one of the two polynomials.
(x+\sqrt{m}+\sqrt{2})*(x+\sqrt{m}-\sqrt{2}) = x^2+2x\sqrt{m}+m-2. This is okay if m is a square.
(x+\sqrt{m}+\sqrt{2})*(x-\sqrt{m}+\sqrt{2}) = x^2+2x\sqrt{2}-m+2. This one doesn't work.
(x+\sqrt{m}+\sqrt{2})*(x-\sqrt{m}-\sqrt{2}) =x^2-2\sqrt{2m}-m-2. This is okay if 2m is a square.
Thus, P_m will factor iff m is a square or twice a square.

[LZ]:  If a is a zero, so is -a. So it can be factored as (x^2-a^2)(x^2-b^2), where a^2 = m+2+2sqrt(2m) and b^2=m+2-2sqrt(2m). Notice that a^2 and b^2 are integers iff m = 2^(2k+1) for k ge 0, and in this case {a^2, b^2} = {2(2^k +or- 1)^2}. So a and b can never be integers. Hence the two factors must be of degree 2. The other possibility is (x-a)(x-b) as one degree-2 factor. Since (a +or- b)^2 = (a^2+b^2) +or- 2ab = (2m+4) +or- 2(m-2) = 4m or 8. So m must be a perfect square. In conclusion, m = 2^(2k+1) or k^2. Actually, the four zeros are sqrt(m)+sqrt(2), sqrt(m)-sqrt(2), -sqrt(m)+sqrt(2), and -sqrt(m)-sqrt(2). From these, it's easier to obtain the answers.

***********************************************************************************************
[Problem A4] Triangle ABC has area 1. Points E, F, G lie, respectively, on sides BC, CA, AB such that AE bisects BF at point R,  BF bisects CG at point S, and CG bisects AE at point T. Find the area of triangle RST.

[PY]: By symmetry, the points E, F, G divide the sides BC, CA, AB in the same  ratio, say,  BE : EC = CF : FA = AG : GB = 1:r. Applying Menelaus's theorem to the transversal ARE of triangle BCF, we have  -1 = (BE/EC)(CA/AF)(FR/RB) = (1/r)((1+r)/(-r))(1/1) = -(1+r)/r^2. It follows that r^2 = r+1, and r = the golden ratio phi = (sqrt 5 +1)/2. Now, it is clear that each of triangle CAT, ABR, and BCS has area  r/(2(1+r)). The area of triangle RST = 1 - 3r/(2(1+r)) = (7-3sqrt 5)/4.

***********************************************************************************************
[Problem A5] Prove that there are unique positive integers a and n such that  a^(n+1) - (a+1)^n = 2001.

[SCL]: First observations: (I can get a, and prove that there are a limited possible number of n.)
Note that a^{n+1}-(a+1)^n=2001 can be expanded to a^{n+1}-sum( (n choose i)*a^i, i=1..n) = 2002.
Since a divides the left hand side, a divides 2002.  This somewhat narrows down the search for a.
That is a is in the set F_{2002}={1,2,7,11,13,14,22,26,77,91,143,154,182,286,1001,2002}.
We could try the same trick expanding ((a+1)-1)^{n+1}-(a+1)^n=2001, yielding
sum( (n+1 choose i)*(a+1)^i*(-1)^{n+1-i},i=1..n+1) - (a+1)^n = 2001-(-1)^{n+1}.
Thus, a+1 divides 2000 or 2002. Thus, a+1 is in the set
F_{2000}={1,2,4,5,8,10,16,20,25,40,50,80,100,125,200,250,400,500,1000,2000} or in the set F_{2002}, and a is in the set
{0,1,3,4,7,9,15,19,24,39,49,79,99,124,199,249,399,499,999,1999} or in the set
{0,1,6,10,12,13,21,25,76,90,142,153,181,285,1000,2001}.
Examining the two restrictions on a, we see that a=13 is the only possibility.
(There is probably an easier way to solve the problem a divides 2002, a+1 divides 2000 or 2002 than I have made it by looking at the sets.)
We must now solve the equation 13^{n+1}-14^n=2001. It is obvious that n>1, since otherwise 13^{n+1}-14^n<13^{n+1}<13^2<2001.
n=2 is a possibility, and we find that 13^3=2197, 14^2=196, 13^3-14^2=2001.
*** We have one solution now ***  We need to show there are no others ***
This is where the solution is not so nice. We need to show that n>2 is impossible. It is obvious that some value of n is too large, since 13^{n+1}-14^n=13^n*(13-(14/13)^n)<0 if (14/13)^n>13. [If you're really interested, this happens at n=35, but the students do not have calculators on the Putnam.]
Let's write 13^{n+1}=2001+14^n. Now, it is obvious that n is not odd, since then 2001+14^n is a multiple of 5. Let's write out what happens mod 10:

n     13^{n+1}             14^n     2001+14^n

1      9                    4         5
2      7                    6         7       possible
3      1                    4         5
4      3                    6         7
5      9                    4         5
6      7                    6         7       possible?

We could prove that n is 2 mod 4 this way, but modular arguments like this won't knowck out all n past a certain point.
One could look at the two curves 13^{x+1} and 2001+14^x and convince oneself that they can cross only twice. But then, one needs to show that the other crossing is not integral.

[ML1]:    Following Stephen's observation we know that   a|2002 ,  a+1|2002  or  a+1|2000.
1) First,let a+1|2002.
  (a,a+1)=1   so  a*(a+1)|2002 = 11*13*14
In the factorization of 2002 we see that the only  consecutive integers are 13 and 14.Hence, a = 13.
2) Now,let a+1|2000. Then,    a*(a+1)|2000*2002 = 4*5*7*8*11*13*25.
Consecutive factors are 4,5 and 7,8 .
 a cannot be 4, for 4 is not divisor of 2002.
But there is no problem with a = 7
  7|2002   and   8|2000
We have another Diophantine equation
    7^(n+1) - 8^n = 2001            (1)
How to show that solution doesn't exist? A possible common method applied to both equations could be that their left hand sides grow as n is growing.
 For n >= 4 LHS of (1) is > 2001   and the same happens with    13^(n+1) - 14^n = 2001  for n >= 3.
Is there some lower bound for    a^(n+1) - (a+1)^n   in terms of a and n ?

[FvL]: Following Stephen's approach: It is not difficult to see that 13^(n+1)-14^n \le 0 is equivalent to (1 + 1/13)^n \ge 13, and we find a rough estimation with n \ge 12*13=156.
Now suppose there is a second solution to 13^(n+1) - 14^n = 2001 with n>2. Then we have 13^3 - 13^(n+1) = 14^2 - 14^n. So 14^(n-2) = 1 (mod
13^3=2197). It is not difficult to check that 14^13 \neq 1 (mod 2197), and it seems that thus the first solution is 14^169 = 1 (mod 2197), which would bring n=171 > 156.
 

***********************************************************************************************
[Problem A6] Can an arc of a parabola inside a circle of radius 1 have length greater than 4?

[SCL]: An idea for A-6 is to assume that you put the arc so that the vertex is at the bottom of the circle and the parabola opens up. If you do this, and if the parabola is very thin, you get very close to 4 as the length.

[PY]: I put a unit circle tangent to the x-axis at the origin and consider the parabola through (0,0,) (2sin t.cos t, 2cos^2 t), and (-2sin t.cos t, 2cos^2 t). The length of the parabolic arc is (2/sin^2 t).Integral_{x=0}^{x=2sin t.cos t} sqrt(sin^4 t + x^2) dx. Is there an easy way of seeing that this exceeds 4 for small positive values of t? Or is this true?

[SCL]: I'd set the circle as x^2+y^2=1, and the parabola as y=ax^2-1. Then the curves intersect at y=-1 and at y=(a-1)/a.
The arclength integral is \int_{x= -b}^{b} \sqrt{1+4a^2x^2} dx, which is easily handled by setting 2ax=\tan(\theta). The value of b is obtained by setting ab^2-1=(a-1)/a and solving for b=\sqrt(2a-1)/a.
Not particularly pretty, but one can evaluate the integral. Then, the question is, is the function we get ever more than 4? (And, it turns out that at a=40, the integral is 4.0008, again, with a bit of cheating, since the students don't have a calculator.)

[LZ]: I used TI-92 to do a numerical integration. For x close to 0, the answer exceeds 4 very slightly. But I'm not sure whether it's the rounding errors.

[SCL]: Maybe things are simpler if we uniformly scale the plane so that the parabola is y=x^2, and the circle is tangent to the parabola at the origin. This might make the calculations slightly easier (not much) to find the arc length from x=-f to x=f, but then you need to fit the circle through the three points (0,0), (f,f^2), (-f,f^2) [not a hard task]. Then, perhaps the limit as f goes to infinity of the arclength over the circle radius is all that is needed. Don't know yet it this is easy.

[XDZ]: If we use the circle x^2+(y-1)^2=1 and the perabola y=ax^2, then we get three intersections (0,0), (sqrt{1/a (2-1/a)}, 2-1/a), (-sqrt{1/a (2-1/a)}, 2-1/a) for a>1/2. So the arc of the parabola inside the circle is L(a)=2*int_0^(sqrt{1/a (2-1/a)}) sqrt(1+(2ax)^2)dx.
On using the substitution u=2ax, we obtain L(a)=1/a*int_0^(2*sqrt{2a-1}) sqrt{1+u^2}du. By direction calculation using the anti-derivative of
f(u)=sqrt{1+u^2}, we get L(a)=1/a*(sqrt{16a^2-14a+3}+1/2*ln(2sqrt{2a-1}+sqrt{8a-3}))>4 when a is large enough since 1/2*ln(2sqrt{2a-1}+sqrt{8a-3})>4a-sqrt{16a^2-14a+3}, where the right-hand-side of the inequality tends to a finite limit 14/8, while the left hand side tends to infinity as a tends to infinity. The proof is complete.

[JPE]: I come back to PY's first idea. L(t) = 2/sin^2 t int(sqrt(x^2+sin^4 t),x=0...2 sin t cos t). Putting x=z sin^2 t, we get
L(t) = 2 sin^2 t int(sqrt(z^2+1), z=0...2 cot t).
If I(t) = int(sqrt(z^2+1) - z), z = 0..2 cot(t)), we haveI(t) -> + infi when t->0, because z(sqrt(z^2+1) - z) ->1/2 when z->infi.
Now, L(t) - 4 = 2 sin^2 t (I(t) - 2) > 0 for t close from 0.

[LZ]: As the parabola gets thinner, the extra length is gained near the vertex. Using this observation, I evaluated the integral up to a convenient height (I used: from the vertex (0,-1) to the x-intercept)and estimated the upper part by vertical linear height. The integration is similar to XDZ's.
 
 

Bibliography.
 
 
 

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