Putnam Exam 2004 -- [*SPOILERS*]

From: Dave Rusin (rusin_at_vesuvius.math.niu.edu)
Date: 12/05/04 

Date: 5 Dec 2004 05:31:02 GMT

The Sixty-Fifth Annual Putnam Exam was held today. I have already
posted a copy of the questions. Here are as many answers as I have
at this moment; I have nothing to say about A-5 and B-6.

If I were the grader I wouldn't give myself full credit for some of
these answers but I think rather than nail down all the details I
will wait for someone else to provide the slickest answers, making
the drudgery unnecessary... (See Problems A-2, A-4, and problems
with detailed computations such as B-3, B-4, B-5.)

Overall I thought this was an easier exam than is typical, which
made the event much more fun for the "average" students taking the test.

I will add these answers and any other interesting responses to the
files I make available about Putnam questions; see
   http://www.math.niu.edu/~rusin/problems-math/

A-1.

Suppose that S.O.'s success count S(N) stayed strictly below 0.80 N
for all N < K, but that S(K) >= 0.80 K. This requires S(K-1) = S(K) - 1.
Then from S(K-1)/(K-1) < 4/5 and S(K)/K >= 4/5 we conclude that
0 <= 5 S(K) - 4 K < 1 ; since 5 S(K) - 4 K is an integer, it must
then equal zero, so S(K) = 4/5.

Comment: Obviously the same proof works for any percentage of the form
1 - 1/m with integer m, but for more general percentages the result
is false. This problem will make a very pretty example the next time
I teach the Intermediate Value Theorem :-)

A-2.

>From Heron's formula, the area and side lengths of a triangle satisfy
   16 A^2 = 2 (a^2b^2+a^2c^2+b^2c^2) - (a^4+b^4+c^4)
Viewed as a quadratic polynomial in X = a^2, this function is clearly
increasing as long as X < (b^2+c^2), which means that the area of a
triangle increases with the length of any side as long as the angle
opposite that side is acute (a^2 < b^2 + c^2 ).

(A student pointed out to me at lunch that this is also obvious from
A = (1/2) b h, where the height h of the triangle varies with a but
c is fixed; the maximum height occurs with sides b and c perpendicular.)

It then suffices to observe that we can transform triangle T_1 to T_2
by a sequence of operations which lengthen just one edge at a time. This
is not entirely obvious since, for example, we are not given that the
smaller triangle is acute. But it's easy to see in a sketch which I will
not attempt in ASCII, showing the portion of the positive octant in
a,b,c -space which corresponds to triangles ( a < b+c, etc. ); the acute
triangles are the ones external to three cones around the coordinate
axes ( a^2 < b^2 + c^2, etc.) If one always lengthens the shortest edge
(from among those that need to be lengthened to change T_1 into T_2),
then that will always be opposite an acute angle. (An obtuse angle will
always be opposite the _largest_ side, and that cannot the the only side
remaining to be lengthened since T_2 is acute.)

Note: I guess I had never before stopped to think about under exactly
what conditions it is true that lengthening the sides of a triangle
increases the area. Now I know!

A-3.

We prove by induction that u_n = (n-1)!! = (n-1)(n-3)(n-5)..., which
is easily checked to be valid for small n. Of course this will mean
the u_n are integral.

If the claim is true for u_n and u_{n+2} then u_{n+2} = (n+1) u_n, so
the first column of the matrix in the determinant is a multiple of u_n,
and we have simply the recurrence relation
   u_{n+3} = (n+1) u_{n+1} + n!/u_n
           = (n+1) n!! + n!!
           = (n+2) n!! = (n+2)!!,
providing the inductive step.

A-4.

This is a heavily-used formula when n = 2 : xy = (1/4)( (x+y)^2 - (x-y)^2 ).
I guess I never really thought about generalizing it before!

It suffices to arrange it so that the right side is a nonzero multiple of
every x_i ; for then it is a degree-n polynomial and also a multiple of
x_1 x_2 ... x_n, so the quotient of the two sides is a constant
(necessarily rational, as can be seen from substituting x_1 = ... = 1);
we can then divide through to make the constant be 1.

If we arrange it so that the right side is symmetric in the x_i, then
it suffices to make sure it vanishes when x_1 = 0.

For odd n this is easy: for any subset T of N = {1, 2, ..., n}, let
S(T) = the sum of the x_i with i in T. Then consider

  X = \sum (-1)^|T| ( S(T) - S(N-T) )^n ,

the sum taken over all subsets T of N. When we substitute x1=0 we
obtain an alternating sum of terms of the form ( S(U) - S(M-U) )^n
where M = N - {1}. Each such term arises exactly twice, once from
S(U union {1}) - S(M-U) and once from S(U) - S(N-U); since the cardinalities
of U and U union {1} are of opposite parity, these two summands
will cancel. Thus, X vanishes when x1=0.

On the other hand, X (apparently) doesn't vanish identically; for example,
when all x_i equal 1, we have
  c = \sum (-1)^|T| ( |T| - |N-T| )^n = \sum (-1)^k (2k-n)^n C( n,k ),
which seems to equal (-2)^n n! (I computed the first few examples but
didn't prove this formula in general.)

So whatever the value of c really is (it's obviously integral) we
can divide X by c to get a sum which is a multiple of x1, and thus
of each x_i, and thus of the product x1 x2 ... x_n, but the
quotient must be both constant and taking the value 1.

I didn't take advantage of the opportunity to use 0 as a coefficient!

A-5.

No clue. I worked out the case n=1 completely; the expected number of
components is (m+1)/2 . I suppose there might be some kind of induction
argument, but since they ask us to prove the number of components is
AT LEAST mn/8, that suggests that what we're supposed to do is to find
a lot of configurations with lots of components, so that we can bound
the expected number without doing all the grubby computations.

A-6.

Heh, heh, check this one out:
  Let F(x,y,z,w) = f(x,y) + f(z,w) - f(x,w) - f(z,y); then integrate
  F^2 over the box [0,1]^4 . Done!

(This is the distillation of about 5 pages of computations, followed by
a great big step back to look at What The Computations Really Mean.
I have learned that to understand these integral inequalities it pays
to think in terms of step functions and simple functions; writing all that
out gave me a solution but then I realized this other way to say it.
Note that it is critical that the domain of integration be the UNIT square.)

B-1.

This is really standard. Write r = p/q in lowest terms; then we have
   c_n p^n + c_{n-1} p^{n-1} q + ... + c_0 q^n = 0
and so for each j between 0 and n we see q^j divides
   c_n p^n + c_{n-1} p^{n-1} q + ... + c_{n-j+1} p^{n-j+1} q^{j-1}
 = p^{n-j}( c_n p^{j} + c_{n-1} p^{j-1} q + ... + c_{n-j+1} p^1 q^{j-1} )
Since p and q are coprime, q^j divides the other factor. Dividing
through, we may express the integer quotient as a polynomial in r.

B-2.

Another slick one: Let S = {1, 2, ..., m}, T = {m+1, ..., m+n}.
How many functions are there from S union T to S union T ? (m+n)^(m+n).
Among those are the functions that send precisely m elements of the
domain to S, and the other n elements to T. There are C(m+n,m) ways
to choose which elements go to S, and once those are chosen there are
m^m n^n such functions. So (m+n)^(m+n) >= (m+n)!/m!n! m^m n^n .

B-3.

If a > 2 we may use a constant function: a rectangle measuring a by
2a/(a-2) has perimeter and area equal.

If a<2 there is no such function. The area is a m where m is the
mean value of f over [0,a], which is certainly no larger than the
maximum value M of f on the interval. On the other hand, the perimeter
is at least the length of the line segments joining (0,0), (a,0), and
(x,M) for some x in the interval, but each of the non-horizontal segments
has length more than M, so the perimeter is more than 2M, which is
more than aM, which is more than a m, the area. The case a=2 is
similar; just use the fact that the perimeter is then at least
2 + 2 sqrt(1 + M^2).

B-4.

This is pretty standard too. One could matrices, but let's instead
view the plane as being the set of complex numbers; a rotation by
an angle theta is accomplished by multiplication by u = exp(i theta).
(The function f(z) = P + u (z - P) is the rotation around P.)
So we are composing the functions
   R_k(z) = P_k + u ( z - P_k) = u z + (1-u) k
By induction on m we find
   (R_m o ... o R_2 o R_1) (z) = u^m (z) + S_m where S_m =
(1-u) m + u S_{m-1}, i.e.
    S_m = (1-u) ( m + u (m-1) + u^2 (m-2) + ... + u^m (0) ).
        = m - u - u^2 - ... - u^m = m - (u - u^{m+1})/(1 - u)

In the problem we were given that theta = 2 pi / n , so u^n = 1,
meaning
   (R_n o ... o R_2 o R_1) (z) = u^n (z) + S_n = z + n,
a simple translation R(x,y) = (x+n, y).

This motion is easily demonstrated for low n.

B-5.

It makes more sense to deal with the logs. We need to look at

   lim_{x->1-} lim_{N->\infty} sum_{n=0}^N x^n (log(1+x^{n+1}) - log(1+x^n))

= lim_{x->1-} lim_{N->\infty}
      ( sum_{n=1}^N (x^{n-1} - x^n) log(1+x^n) ) -log(2) + x^N log(1+x^{N+1})

For any x < 1, the last term tends to 0 as N->\infty, so we have only
 - log(2) + lim_{x->1-} (1/x - 1) sum_{n=1}^\infty x^n log(1+x^n)

Now, we may estimate the infinite sum using bounds on the logarithm from
its Taylor series; for example, we have log(1+x^n) > x^n - x^{2n}/2 but
log(1+x^n) < x^n - x^{2n}/2 + x^{2n}/3 . From these we obtain inequalities
on the sum: it lies between x^2/(1-x^2) - (1/2)(x^3/(1-x^3)) and
x^2/(1-x^2) - (1/2)(x^3/(1-x^3)) + (1/3)(x^4/(1-x^4)), and we may obtain
more bounds of this type. Multiplying in the additional factor (1/x - 1)
(which is positive) gives bounds such as
   x^1/(1+x) - (1/2)(x^2/(1+x+x^2)) and
   x^1/(1+x) - (1/2)(x^2/(1+x+x^2)) + (1/3)(x^3/(1+x+x^2+x^3))
Applying these bounds to each x < 1 we find the limit to lie between
   1/2 - (1/2)(1/3) and 1/2 - (1/2)(1/3) + (1/3)(1/4)
and more generally it is alternately larger or smaller than a partial sum of
the the absolutely convergent series
   (1/1)(1/2) - (1/2)(1/3) + (1/3)(1/4) - ...
Carrying out this argument more generally to finite expansions of the
Taylor series shows that the limit must equal this infinite sum.
   
If we add 2( (1/2)(1/3) + (1/4)(1/5) + (1/6)(1/7) + ...) we obtain
the famous telescoping series, which sums to 1. But in like manner we may
recognize this addend as 2( (1/2) - (1/3) + (1/4) - (1/5) + ... ), which is
2 (1-log(2)). So the series in the last paragraph converges to 2 log(2) - 1.

So I conclude that the logarithm of the original limit is log(2) - 1,
and so the limit itself must be 2/e .

B-6.

No clue. It's a nice problem though -- sort of a teaser for the Twin Prime
conjecture or something. (Let A = set of all primes.)

For contrast, consider what happens when A = set of all squares (B = set
of (almost) all composites), or A = an arithmetic progression (B is an
ideal of Z), or A = powers of 2 (this B is indeed sparse).
I look forward to a solution of this one.

Relevant Pages

  • Re: Putnam Exam 2004 -- [*SPOILERS*]
    ... the area and side lengths of a triangle satisfy ... > the first column of the matrix in the determinant is a multiple of u_n, ... > we can then divide through to make the constant be 1. ... > can divide X by c to get a sum which is a multiple of x1, ...
    (sci.math)
  • Re: geometry problem (triangle)
    ... triangle from its angular points is less than the perimeter ... i've managed to get their sum greater than half the ... perimeter, but that's not what is required. ... it would seem that the polygonal line BPC is the ...
    (sci.math)
  • Re: geometry problem (triangle)
    ... prove that the sum of the distances of any point within a ... triangle from its angular points is less than the perimeter ... i've managed to get their sum greater than half the ... perimeter, but that's not what is required. ...
    (sci.math)
  • Re: geometry problem (triangle)
    ... triangle from its angular points is less than the perimeter ... i've managed to get their sum greater than half the ... perimeter, but that's not what is required. ...
    (sci.math)
  • Re: Dik T. Winter says: Definition: sum{i in N} i = 0
    ... A figure is called triangle* iff ... sum summs infinitely many summands. ... Induction to the infinite is valid and sound, as long as measure is preserved. ... balls naturally numbered from 1, we insert balls 10n-9 through 10n, and remove ball n at each iteration n. ...
    (sci.math)