The 69th William Lowell Putnam Mathematical Competition
Saturday, December 6, 2008
A1 Let f : R2 → R be a function such that f (x, y)+ f (y, z)+ (The elements of G in the sequence are not required to
f (z, x) = 0 for all real numbers x, y, and z. Prove that be distinct. A subsequence of a sequence is obtained
there exists a function g : R → R such that f (x, y) = by selecting some of the terms, not necessarily consec-
g(x) − g(y) for all real numbers x and y. utive, without reordering them; for example, 4, 4, 2 is a
subsequence of 2, 4, 6, 4, 2, but 2, 2, 4 is not.)
A2 Alan and Barbara play a game in which they take turns
filling entries of an initially empty 2008 × 2008 array. B1 What is the maximum number of rational points that can
Alan plays first. At each turn, a player chooses a real lie on a circle in R2 whose center is not a rational point?
number and places it in a vacant entry. The game ends (A rational point is a point both of whose coordinates
when all the entries are filled. Alan wins if the determi- are rational numbers.)
nant of the resulting matrix is nonzero; Barbara wins if
it is zero. Which player has a winning strategy? B2 RLet F0 (x) = ln x. For n ≥ 0 and x > 0, let Fn+1 (x) =
x
0 Fn (t) dt. Evaluate
A3 Start with a finite sequence a1 , a2 , . . . , an of positive in-
tegers. If possible, choose two indices j < k such that a j n!Fn (1)
lim .
does not divide ak , and replace a j and ak by gcd(a j , ak ) n→∞ ln n
and lcm(a j , ak ), respectively. Prove that if this process B3 What is the largest possible radius of a circle contained
is repeated, it must eventually stop and the final se- in a 4-dimensional hypercube of side length 1?
quence does not depend on the choices made. (Note: B4 Let p be a prime number. Let h(x) be a polynomial with
gcd means greatest common divisor and lcm means integer coefficients such that h(0), h(1), . . . , h(p2 − 1)
least common multiple.) are distinct modulo p2 . Show that h(0), h(1), . . . , h(p3 −
A4 Define f : R → R by 1) are distinct modulo p3 .
( B5 Find all continuously differentiable functions f : R → R
x if x ≤ e such that for every rational number q, the number f (q)
f (x) =
x f (ln x) if x > e. is rational and has the same denominator as q. (The
denominator of a rational number q is the unique posi-
1
Does ∑∞
n=1 f (n) converge? tive integer b such that q = a/b for some integer a with
gcd(a, b) = 1.) (Note: gcd means greatest common di-
A5 Let n ≥ 3 be an integer. Let f (x) and g(x) be poly- visor.)
nomials with real coefficients such that the points
( f (1), g(1)), ( f (2), g(2)), . . . , ( f (n), g(n)) in R2 are the B6 Let n and k be positive integers. Say that a permutation
vertices of a regular n-gon in counterclockwise order. σ of {1, 2, . . . , n} is k-limited if |σ (i) − i| ≤ k for all
Prove that at least one of f (x) and g(x) has degree i. Prove that the number of k-limited permutations of
greater than or equal to n − 1. {1, 2, . . . , n} is odd if and only if n ≡ 0 or 1 (mod 2k +1).
A6 Prove that there exists a constant c > 0 such that in ev-
ery nontrivial finite group G there exists a sequence of
length at most c log |G| with the property that each el-
ement of G equals the product of some subsequence.
, Solutions to the 69th William Lowell Putnam Mathematical Competition
Saturday, December 6, 2008
Kiran Kedlaya and Lenny Ng
A–1 The function g(x) = f (x, 0) works. Substituting a01 , . . . , a0h are not. Repeating this argument for each pair
(x, y, z) = (0, 0, 0) into the given functional equa- (p, m) such that pm divides the initial product a1 , . . . , an ,
tion yields f (0, 0) = 0, whence substituting (x, y, z) = we can determine the exact prime factorization of each
(x, 0, 0) yields f (x, 0) + f (0, x) = 0. Finally, substi- of a01 , . . . , a0n . This proves that the final sequence is
tuting (x, y, z) = (x, y, 0) yields f (x, y) = − f (y, 0) − unique.
f (0, x) = g(x) − g(y). Remark: (by David Savitt and Noam Elkies) Here are
Remark: A similar argument shows that the possible two other ways to prove the termination. One is to ob-
functions g are precisely those of the form f (x, 0) + c serve that ∏ j a jj is strictly increasing at each step, and
for some c. bounded above by (a1 · · · an )n . The other is to notice
that a1 is nonincreasing but always positive, so even-
A–2 Barbara wins using one of the following strategies.
tually becomes constant; then a2 is nonincreasing but
First solution: Pair each entry of the first row with the always positive, and so on.
entry directly below it in the second row. If Alan ever
Reinterpretation: For each p, consider the sequence
writes a number in one of the first two rows, Barbara
consisting of the exponents of p in the prime factoriza-
writes the same number in the other entry in the pair. If
tions of a1 , . . . , an . At each step, we pick two positions
Alan writes a number anywhere other than the first two
i and j such that the exponents of some prime p are in
rows, Barbara does likewise. At the end, the resulting
the wrong order at positions i and j. We then sort these
matrix will have two identical rows, so its determinant
two position into the correct order for every prime p
will be zero.
simultaneously.
Second solution: (by Manjul Bhargava) Whenever
It is clear that this can only terminate with all se-
Alan writes a number x in an entry in some row, Bar-
quences being sorted into the correct order. We must
bara writes −x in some other entry in the same row. At
still check that the process terminates; however, since
the end, the resulting matrix will have all rows summing
all but finitely many of the exponent sequences consist
to zero, so it cannot have full rank.
of all zeroes, and each step makes a nontrivial switch
A–3 We first prove that the process stops. Note first that in at least one of the other exponent sequences, it is
the product a1 · · · an remains constant, because a j ak = enough to check the case of a single exponent sequence.
gcd(a j , ak ) lcm(a j , ak ). Moreover, the last number in This can be done as in the first solution.
the sequence can never decrease, because it is always Remark: Abhinav Kumar suggests the following proof
replaced by its least common multiple with another that the process always terminates in at most n2 steps.
number. Since it is bounded above (by the product of (This is a variant of the worst-case analysis of the bub-
all of the numbers), the last number must eventually ble sort algorithm.)
reach its maximum value, after which it remains con-
Consider the number of pairs (k, l) with 1 ≤ k < l ≤ n
stant throughout. After this happens, the next-to-last
such that ak does not divide al (call these bad pairs).
number will never decrease, so it eventually becomes
At each step, we find one bad pair (i, j) and eliminate
constant, and so on. After finitely many steps, all of the
it, and we do not touch any pairs that do not involve
numbers will achieve their final values, so no more steps
either i or j. If i < k < j, then neither of the pairs (i, k)
will be possible. This only happens when a j divides ak
and (k, j) can become bad, because ai is replaced by a
for all pairs j < k.
divisor of itself, while a j is replaced by a multiple of
We next check that there is only one possible final se- itself. If k < i, then (k, i) can only become a bad pair if
quence. For p a prime and m a nonnegative integer, we ak divided ai but not a j , in which case (k, j) stops being
claim that the number of integers in the list divisible bad. Similarly, if k > j, then (i, k) and ( j, k) either stay
by pm never changes. To see this, suppose we replace the same or switch status. Hence the number of bad
a j , ak by gcd(a j , ak ), lcm(a j , ak ). If neither of a j , ak is pairs goes
down by at least 1 each time; since it is at
divisible by pm , then neither of gcd(a j , ak ), lcm(a j , ak ) most n2 to begin with, this is an upper bound for the
is either. If exactly one a j , ak is divisible by pm , then number of steps.
lcm(a j , ak ) is divisible by pm but gcd(a j , ak ) is not.
Remark: This problem is closely related to the clas-
gcd(a j , ak ), lcm(a j , ak ) are as well. sification theorem for finite abelian groups. Namely,
If we started out with exactly h numbers not divisible if a1 , . . . , an and a01 , . . . , a0n are the sequences obtained
by pm , then in the final sequence a01 , . . . , a0n , the num- at two different steps in the process, then the abelian
bers a0h+1 , . . . , a0n are divisible by pm while the numbers
