# THE SIXTY-NINTH ANNUAL WILLIAM LOWELL PUTNAM EXAMINATION

**Problem A5**

Let n ≥ 3 be an integer. Let f(x) and g(x) be polynomials with real coefficients
such that the

points in R^{2} are the vertices of
a regular n-gon in

counterclockwise order. Prove that at least one of f(x) and g(x) has degree
greater than or equal

to n - 1.

**Solution:** Consider the polynomial p(x) = f(x) + ig(x), whose degree is
the maximum of the

degrees of f and g and which maps { 1, 2, ... , n} onto the vertices of this
polygon. With a suitable

choice of a complex constant (equal to the
center of the polygon), and a nonzero complex number

, we can replace this polynomial with the
polynomial
, whose degree is the

same as that of p(x), that is, equal to the maximum of the degrees of f(x) and
g(x), and which

maps to ,
in that order, where
. We need to show that

the degree of q(x) is at least n - 1.

Suppose not, that is, suppose . The
coefficients

satisfy the following linear system of n - 1
equations:

Now this system has a Vandermonde matrix, and can
therefore be solved for the coefficients

, which are uniquely determined. (The
determinant of the Vandermonde

matrix is The point of this analysis
is that there is one and only one

polynomial of degree at most n - 2 that maps
onto in that order.

But that polynomial is obviously

What we need to show is that q(1) cannot be 1. But that is obvious, since

**Problem A6**

Prove that there exists a constant c > 0 such that in every nontrivial finite
group G there exists

a sequence of length at most with the
property that each element of G equals the product

of some subsequence. (The elements of G in the sequence are not required to be
distinct. A

subsequence of a sequence is obtained by selecting some of the terms, not
necessarily consecutive,

without reordering them, for example, 4, 4, 2 is a subsequence of 2, 4, 6, 4, 2,
but 2, 2, 4 is not.)

**Solution:** If we make the convention that the identity element e can be
represented as an empty

product, the constant c can be taken equal to 6. With this convention, the
restriction to non-trivial

groups can be removed also, since a string of 0 elements will represent the only
element in the

trivial group feg, and we'll certainly have 0 ≤ 6 ln(1) = 0.

Let G be any finite group, and let a any element of G different from the
identity. Since G is

finite, a has finite order, say k ≥ 2, that is, a^{k} = e. Let r be the
unique positive integer such that

. Then each of the elements a^{ j} ,
0 ≤ j < k (where a^{0} = e) has a unique representation

as a product of the elements , since each
integer j with 1 ≤ j < k has a unique

binary representation as a sum of powers 2^{i} with 0 ≤ i ≤ r - 1. Thus
we can now represent the

k distinct elements a^{ j} , 0 ≤ j < k, as products of the r elements
, 0 ≤ j ≤ r - 1. Notice that

. Thus, at this stage, we can represent k
elements of the

group using a string of at most elements,
taken from the sequence

If G consists only of the cyclic group H generated by a,
we are done, and indeed c = 3 > 2/ ln(2)

will suffice in this case. If H ≠ G, let b be an element not in H, and let l ≥ 2
be the smallest

positive integer such that . Just as above,
we know that any power b^{
j} , 0 ≤ j < l, can be

represented as a product of the s powers ,
where
. We now form the

sequence

which contains
elements. The set K of products of subsequences of

T consists of the elements for which 0 ≤ h <
l, 0 ≤ i < k, and 0 ≤ j < l. At least kl

of these are distinct, namely the elements .
For if
with ,
then

for some v with 0 ≤ v < k. Since
, this means
and

hence

If G = K, we are now done, since that means
≥ kl, and we have
represented every element

of the group by a product taken from the sequence T, which consists of at most

) elements.

If G ≠ K, let d ∈ G\K, and let m ≥ 2 be the smallest positive integer such that
. We

then form the sequence

where , so that
.

The products of subsequences of the sequence U form a set L of elements
containing all products

of the form

where 0 ≤ f < m, 0 ≤ g < l, 0 ≤ h < k, 0 ≤ i < l, and 0 ≤
j < m. At least klm of these are

distinct, namely the products . For if
, with ,
then

for some w with 0 ≤ w < k. Since
, it follows

that , and then, by what was proved about the
set K above, that
and .

If L = G, we are now done, having represented every element of G as a product
taken from

a sequence containing fewer than

6 ln() elements.

It is now clear that this process can be continued until the group G is entirely
exhausted.