Problems from the 1994 Putnam exam (December 3, 1994).

Problem A1

The hypothesis guarantees the sum a_{2^n} + ... + a_{2^{n+1} - 1} is no
larger than the sum a_{2^{n+1}}  + ... + a_{2^{n+2} -1}.

Thus the sum reduces to a sum of a non-decreasing sequence of positive
numbers.

-- Robert Stimets <rstimets@silver.ucs.indiana.edu>

Problem B1

25^2 - 11^2 = 504 > 500, so clearly no square n^2 larger than 100 can be the
smallest of the 15 "nearby" squares.  On the other hand, it is easy to
see that if n is the smallest of the nearby squares, then n must be at
least 9.  By process of elimination or some other magic, the numbers in
question are
314 < x < 326  or  331 < x < 351

that is,
64 + 250 < x < 576 - 250 [Editor: "276 - 250" in the original;
24^2 = 576]   or   81 + 250 < x < 100 + 251

-- Robert Stimets

Problem B2

The second derivative has 0, 1 (repeated) or 2 real roots.
This number is unaffected by subtracting a polynomial of the form
mx+b.  y=mx+b intersects x^4 + 9 x^3 + c x^2 + 9 x + 4 at four distinct
points iff x^4 + 9 x^3 + c x^2 + (9-m) x + (4-b) [Editor: "(4-c)" in the
original] has four distinct real roots which can only happen if its
first derivative has three distinct real roots which can happen only if
its second derivative has two distinct real roots.

So we assume the second derivative has two real roots. These are inflection
points since otherwise the second derivative would have higher degree than
2.
 Claim the line
connecting them passes through four points of the graph.  The graph is
concave up (or down) on both sides of the two points and is concave
down (up) between them.  The graph lies completely above (below) the
line between the points, on the left side of the points the second derivative
becomes arbitrarily large in the positive (negative) direction so the
graph has a turning point on the left and similarly it has a turning point
on the right. (done with claim)

Thus we only need to find all c such that the second derivative of
y= x^4 + 9 x^3 + c x^2 + 9 x + 4     has two real roots, which happens iff

54^2 - 4*24*(2c) > 0  iff
2916/192 > c

[ Editor: the second derivative is 12x^2 + 54x + 2c, so the condition is
54^2 - 4*12*(2c) = 2916 - 96c > 0, i.e. c < 2916/96 = 243/8. ]

-- Robert Stimets

[ Editor: comments on the solutions posted by Dave Rusin
<rusin@washington.math.niu.edu>, which are not in the collected
material beyond the quoted lines. ]

In article <3brpgb$lfd@mp.cs.niu.edu>
rusin@washington.math.niu.edu (Dave Rusin) writes:
>Spoilers to the Putnam '94 exam follow. Last year I commented that the
>questions were harder than usual; this year I think the reverse is true.

That seems to be the feeling around here too.

>I note in particular a paucity of geometry (questions which tend to
>be elementary but difficult) and of advanced undergraduate course
>questions (which tend to be easy if you've taken the right course).

The only problem of the latter type seemed to be the one involving
nowhere-dense sets, though perhaps the last problem (requiring
the fact that 2 is a primitive root mod 101) counts too.

>A1. Let S_n = a_{2^n}+...+a_{2^(n+1)-1}.  [...]

NB This is a generalization of one standard proof of the divergence
of the harmonic series  1/1+1/2+1/3+1/4+1/5+...

>A2. Apply a linear transformation which transforms the ellipse to a circle:

Simpler yet: apply the linear transformation g(x,y)=(3y,x/3).
This preserves areas, preserves (x^2)/9+y^2 and thus the ellipse,
switches the x and y axes, and takes y=3x/2 to the desired line
all in one step.

>A3. Suppose not.  [...]

NB The bound 2-sqrt(2) is sharp: it is possible to divide the triangle
into 4 parts each of diameter 2-sqrt(2).

>A4. Let  f(r)=det(A+rB). This is a quadratic polynomial in r.  [...]

Furthermore:
0) B need not be the zero matrix!
1) There exist A,B such that A,A+B,A+2B, and A+3B are invertible
over the integers without A+4B having an integral inverse.
2) For k-by-k matrices, if A,A+B,A+2B,...,A+2kB are invertible
over the integers then so is A+rB for all integers r.
3) A harder generalization: even for k>2 the invertibility of
only the 5 consecutive matrices A,A+B,A+2B,A+3B,A+4B suffices.

>A5. [...]

The key is to use that a finite union of nowhere-dense sets in R
is nowhere dense to prove that if A is nowhere dense and r_n->0 then
A+{r_n} is nowhere dense.  In particular it follows by induction
that B+B+B+...+B (1994 times) is nowhere dense where B={r_n}.

>B3. The k's in question are the  k<1.  [...]

A simple argument is to observe that f'>f if and only if g=f/e^x
is increasing.

-- Noam D. Elkies <elkies@zariski.harvard.edu>

In article <3c8f0p$cvk@decaxp.harvard.edu>
elkies@ramanujan.harvard.edu (Noam Elkies) writes:
>[re: problem on invertible matrices A,A+B,...A+4B]
>
>[...]  [To get an n*n matrix with prescribed
>characteristic polynomial let the k-th row be the (k+1)st unit vector
>for 0<k<n, and an arbitrary vector for k=n; the coordinates of that
>n-th row will be the coefficient of the char.poly., at least up to sign.]

ie, the matrix of multiplication by  X  in the algebra Q[X]/(f(X)).
This type of "tautological" construction was useful on another Putnam
problem a few years ago, which asked for matrices  A and B  such that
ABAB=0 but BABA != 0  -- just consider the algebra generated by  A and B
and the relation ABAB=0, truncate it to get something finite dimensional,
and represent A and B by matrices.

>It can be shown, however, that this is the only way to get counterexamples:
>if f is in Z(x) and each of f(0),f(1),f(2),f(3),f(4) is +-1 then they are
>all equal.  It follows that once k>3 the invertibility of A,A+B,...,A+kB
>over Z guarantees the Z-invertibility of A+rB for all integers r.

Slightly more generally, Z-invertibility of any (k+1)   A+tB's suffices.
If   f   sends 3 distict integers to 1, it sends at most one other to -1;
if it sends 4 integers to 1, it sends none to -1.   (Sketch of proof:
if f(x)-1 = (x-a)(x-b)(x-c)g(x) = -2,  {x-a,x-b,x-c} is setwise equal to
{-1,1,+/-2}, which happens at most once; similarly, a product of 4 integers
can't divide -2.)

-- Tal Kubo <kubo@math.harvard.edu>