# THE SIXTY-NINTH ANNUAL WILLIAM LOWELL PUTNAM EXAMINATION

**Remark: **For all solvable groups G, the constant 6 can be reduced to 3. We
already saw this

above, with the cyclic group H. Now let G be a solvable group. Either G is a
simple group and

hence cyclic, or it has a non-trivial normal subgroup H, with
. The first case having been

dealt with, we turn to the second. The subgroup H is also a solvable group.
Since the groups of

order 2 and 3 are cyclic, what has already been shown applies to them. By
induction on , we

can represent all the elements of H as products of subsequences of a sequence of
at most

elements. The same is true of the quotient group
, which also has fewer elements than G and is

solvable. Choosing one representative from the right coset of each element in a
suitable sequence

of at most elements of the quotient group,
and adjoining these to the previous sequence,

we can then represent all the elements in the group as products of subsequences
of a sequence of

at most

elements.

This stronger result holds in particular for all groups of odd order and all
commutative groups.

**Problem B1**

What is the maximum number of rational points that can lie on a circle in R^{2}
whose center is not

a rational point? (A rational point is a point both of whose coordinates are
rational numbers.)

**Solution: **The maximum number is 2. If
and
are any three points on a

circle, the coordinates of the center of that circle are rational functions of
the six coordinates of

these three points. Hence if there are three rational points on a circle, its
center is also a rational

point.

There can be two rational points on a circle whose center is not a rational
point. For example,

the circle about of radius,
whose equation is

passes through (1, 0) and (0, 1).

**Problem B2**

Let F_{0}(x) = ln x. For n ≥ 0 and x > 0, let .
Evaluate
.

**Solution:** The limit is -1. It is easy to prove by induction that

(For , and as x 0.) Hence,

where tends to the
finite limit
, Euler's constant.

**Problem B3**

What is the largest possible radius of a circle contained in a 4-dimensional
hypercube of side length

1?

**Solution: **The maximum radius is .

Let
and
be any two points lying on a given circle of

radius r contained in a hypercube of side 1 with a 90° arc between them. Let

be the center of the circle.

Then the circle can be represented parametrically as

The projection of this circle on the jth axis is parameterized as the locus of all points

This locus is the interval
. Since the

length of this interval is at most 1, we must have
, that is

But the radius r is given by

It follows that 2r^{2} ≤ 1, or
.

To see that this bound can be attained, let us take the hypercube to be.
The circle

of radius with center at (0, 0, 0, 0) in the
hyperplane spanned by the mutually perpendicular

unit vectors and
(which are not themselves contained in the

hypercube) is given by the parametric mapping

and is obviously contained in the hypercube.

**Problem B4
**

Let p be a prime number. Let h(x) be a polynomial with integer coefficients such that h(0), h(1),... ,

h(p

^{2}- 1) are distinct modulo p

^{2}. Show that h(0), h(1),... , h(p

^{3}- 1) are distinct modulo p

^{3}.

**Solution:**Let , where are integers.

Let r be any nonzero integer. We observe that r divides h(k + r) - h(k), since it divides

(k + r)

^{t}- k

^{t}for all nonnegative integers t.

Suppose k and l are integers 0 ≤ k ≤ l < p

^{3}such that p

^{3}divides h(k)-h(l). Write

and , where . Since p

^{2 }divides

h(k) - h(r

_{k}) and , it follows that p

^{2}divides . But this means , and

so, since , we must have l = k + mp

^{2}, where . We wish to show m = 0,

which is equivalent to showing that p divides m.

Now p

^{3}divides h(k + mp

^{2}) - h(k). Observe that for some integer N we have

It follows that p divides

In the latter case, we find that for some integer M,

and so p^{2} divides h(k +mp)-h(k). Now choose u
and v such that 0 ≤ u < p^{2}, 0 ≤ v < p^{2}, and p^{2}

divides both k + mp - u and k - v. It then follows that p^{2} divides
h(u) - h(v), so that u = v. But

then p^{2} divides k + mp - u - (k - v) = mp. That is, p divides m, as
we wished to show.