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
This stronger result holds in particular for all groups of odd order and all commutative groups.
What is the maximum number of rational points that can lie on a circle in R2 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
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).
Let F0(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
, Euler's constant.
What is the largest possible radius of a circle contained in a 4-dimensional hypercube of side length
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 2r2 ≤ 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.
Let p be a prime number. Let h(x) be a polynomial with integer coefficients such that h(0), h(1),... ,
h(p2 - 1) are distinct modulo p2. Show that h(0), h(1),... , h(p3 - 1) are distinct modulo p3.
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 - kt for all nonnegative integers t.
Suppose k and l are integers 0 ≤ k ≤ l < p3 such that p3 divides h(k)-h(l). Write
and , where . Since p2 divides
h(k) - h(rk) and , it follows that p2 divides . But this means , and
so, since , we must have l = k + mp2, where . We wish to show m = 0,
which is equivalent to showing that p divides m.
Now p3 divides h(k + mp2) - 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 p2 divides h(k +mp)-h(k). Now choose u
and v such that 0 ≤ u < p2, 0 ≤ v < p2, and p2
divides both k + mp - u and k - v. It then follows that p2 divides h(u) - h(v), so that u = v. But
then p2 divides k + mp - u - (k - v) = mp. That is, p divides m, as we wished to show.