**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]**