Luc TARTAR to John MACKEY, October 21, 2009

Your second problem today, that for any nine integers there is always five of them whose sum is a
multiple of 5: one puts them in five boxes modulo 5, and if each box receives at least one, one picks one in
each box and the sum is a multiple of 5, and one assumes then that at most four boxes receive an integer.
By the pigeonhole principle one box receives at least 3 integers, and by adding a constant to all the integers
one may assume that it is 0: if there are five 0 one is done, so one assumes that there are 3 or 4 zeros, and
at least 5 integers different from 0 in at most three boxes.
If there are indeed three boxes used among {1, 2, 3, 4} a sum of two add up to 5 and one completes with
3 zeros, in the other cases at most one box ∈ {1, 4} is used and at most one box ∈ {2, 3} is used.
If one box a receives 5 integers, one takes them all.
If one box a receives 4 integers and b receives 1 integer, then because a, b, and a + b are not 0, the 3
integers a + 2b, a + 3b, a + 4b cannot all give a nonzero sum since they are all different and different from a
and a + b, so that one of these sums is 0, and one completes with 2 zeros, 1 zero, or none.
Finally, if one box a receives 3 integers and b receives 2 integers, then 2a + b, and 3a + b are distinct
and different from a and a + b, so that if these sums are not 0 one must have 4a + b = 0, and since b is either
2a or 3a, either 2a + 2b = 0 (completed with 1 zero), or a + 2b = 0 (completed with 2 zeros).
Your last problem of a power of 2 beginning by 2009: it means that 2009 · 10m < 2n < 2010 · 10m ,
or m + log10 2009 < n log10 2 < m + log10 2010. Since α =  log10 2 is irrational, for each k ≥ 1 there
exists a positive integer j ≤ k and an integer i such that α − ji  ≤ j (k+1) 1 1
, or |j α − i| ≤ k+1 . One
1
chooses k large enough so that k+1 < log10 2010 − log10 2009, and then there is an integer ` ∈ Z such that
log10 2009 < ` (j α − i) < log10 2010, and one takes m = ` i and n = ` j.
[For α 6∈ Q, and ` = 1, . . . , k, let i(`) ∈ Z be the integer part of ` α, so that ` α = i(`) + θ` with 0 < θ` < 1.
1
Among the k numbers θ1 , . . . , θk either one satisfies 0 < θ` < k+1 , in which case one chooses j = ` and
1
i = i(`), or one satisfies 1 − k+1 < θ` < 1, in which case one chooses j = ` and i = i(`) + 1, or two distinct
1
satisfy |θ`1 − θ`2 | < k+1 , in which case one chooses j = `1 − `2 and i = i(`1 ) − i(`2 ).]
Your problem set 9 of October 20.
Your problem 1 (Putnam 1996-A4): Let S be a set of ordered triples (a, b, c) of distinct elements of a finite
set A. Suppose that:
1. (a, b, c) ∈ S if and only if (b, c, a) ∈ S,
2. (a, b, c) ∈ S if and only if (c, b, a) 6∈ S,
3. (a, b, c) and (c, d, a) are both in S if and only if (b, c, d) and (d, a, b) are both in S.
Prove that there exists a one-to-one function g: A 7→ R such that g(a) < g(b) < g(c) implies (a, b, c) ∈ S.
[Note: R is the set of real numbers.]
Hint: The intuition is to think about points on the oriented circle S1 and turn around, and that (a, b, c) is
in S means that if one starts from a one finds the points b, c in this order.
Choose a1 ∈ A, and let the relation R be defined on A×A by b R c if and only if either b = c or b 6= c and
(a1 , b, c) ∈ S. Then R is a total order relation. Indeed if b R c and c R d, i.e. (a1 , b, c) ∈ S and (a1 , c, d) ∈ S,
then (c, d, a1 ) ∈ S by axiom 1 and then (d, a1 , b) ∈ S by axiom 3, and therefore (a1 , b, d) ∈ S by axiom 1,
i.e. b R d, showing that the relation R is transitive. The relation is reflexive by construction, and by axiom
2, exactly one of (a1 , b, c) ∈ S and (a1 , c, b) ∈ S holds, showing that the relation is antisymmetric, and that
the order is total.
One can name the elements of A \ {a1 } in an increasing way so that a2 R a3 , . . . , an−1 R an , and therefore
ai R aj i.e. (a1 , ai , aj ) ∈ S for 1 < i < j ≤ n. If 1 < i < j < k ≤ n, then (a1 , ai , aj ) ∈ S and (a1 , aj , ak ) ∈ S,
and therefore (aj , ak , a1 ) ∈ S by axiom 1 and then (ai , aj , ak ) ∈ S by axiom 3. One function g satisfying the
desired conditions is obtained by defining g(ai ) = i for i = 1, . . . , n.
Your problem 2 (Putnam 1989-B2): Let S be non-empty set with an associative operation that is left and
right cancellative (x y = x z implies y = z, and y x = z x implies y = z). Assume that for every a in S the
set {an : n = 1, 2, 3, . . .} is finite. Must S be a group?
I had not written a solution before: For any a ∈ S, since the set of powers of a is finite, one must have
ai = aj for some i < j, and then by the cancellation property one has a = aj−i+1 ; let m + 1 be the smallest
index k ≥ 2 such that a = ak , and let ea = am , so that a ea = ea a = am+1 = a; if m = 1, one has ea = a
and a2 = ea , so that the “inverse” of a is a, and for m ≥ 2, one has am−1 a = a am−1 = am = ea , so that

1
the “inverse” of a is am−1 , and in order to show that S is a group, it remains to show that ea = eb for all
a, b ∈ S. One has (a b)n+1 = a b, so that by the cancellation property (a b)n a = a, which is ea a, showing
that (a b)n = ea ; then, since a (b a)n = (a b)n a = ea a = a = a ea , one deduces that (b a)n = ea ; exchanging
the roles of a and b gives eb = (b a)n , so that ea = eb .
Your problem 3 (Putnam 1974-A1): Call a set of positive integers “conspiratorial” if no three of them are
pairwise relatively prime. (A set of integers is “pairwise relatively prime” if no pair of them has a common
divisor greater than 1.) What is the largest number of elements in any “conspiratorial” subset of the integers
1 through 16?
Hint: One cannot take more than two integers from the list of seven primes {1, 2, 3, 5, 7, 11, 13} and as
there remains nine integers {4, 6, 8, 9, 10, 12, 14, 15, 16}, one cannot have more than eleven integers in a
conspiratorial subset of the integers from 1 to 16. One does obtain a conspiratorial subset of eleven integers
by taking 2, 3 in the first subset and all the nine integers in the second subset, the obtained subset being
conspiratorial because it contains only integers who have either 2 or 3 as a prime factor, and for any three
of them, either two are divisible by 2 or two are divisible by 3.
Your problem 4 (Putnam 1974-A3): A well known theorem asserts that a prime p > 2 can be written as the
sum of two perfect squares (p = m2 + n2 , with m and n integers) if and only if p ≡ 1 (mod 4). Assuming
this result, find which primes p > 2 can be written in each of the following forms, using (not necessarily
positive) integers x and y:
(a) x2 + 16y 2 ;
(b) 4x2 + 4x y + 5y 2 .
Hint: The main observation is that if z is odd then z 2 = 1 (mod 8), if z = 4n then z 2 = 0 (mod 8) and
if z = 4n + 2 then z 2 = 4 (mod 8); therefore the only squares modulo 8 are 0, 1 and 4.
In case (a), as p is odd and p = x2 + 16y 2 , then x must be odd, and therefore x2 = 1 (mod 8), so that
p = 1 (mod 8). Conversely, if p = 1 (mod 8), then p = 1 (mod 4), and therefore there exist a, b such
that p = a2 + b2 , but the only way to obtain 1 modulo 8 by summing two squares is to have one square equal
to 1 and the other square equal to 0, i.e. to have one odd number and the other divisible by 4, i.e. a = x
odd and b = 4y, corresponding to case (a).
In case (b), as p is odd and p = 4x2 + 4x y + 5y 2 = (2x + y)2 + 4y 2 , then 2x + y must be odd and
therefore y must be odd, so that 2y = 4n + 2 and 4y 2 = 16n2 + 16n + 4 = 4 (mod 8) and (2x + y)2 = 1
(mod 8), so that p = 5 (mod 8). Conversely, if p = 5 (mod 8), then p = 1 (mod 4), and therefore there
exist a, b such that p = a2 + b2 , but the only way to obtain 5 modulo 8 by summing two squares is to have
one square equal to 1 and the other square equal to 4, i.e. to have one odd number and the other of the
form 4n + 2, i.e. a odd and b = 2y with y odd, and therefore a − y even, i.e. a = 2x + y, corresponding to
case (b).
Your problem 5 (Putnam 1974-A6): It is well known that the value of the polynomial (x+1)(x+2) · · · (x+n)
is exactly divisible by n for every integer x. Given n, let k = k(n) be the minimal degree of any monic integral
polynomial
f (x) = xk + a1 xk−1 + · · · + ak
(with integer coefficients and leading coefficient 1) such that the value of f (x) is exactly divisible by n for
every integer x.
Find the relationship between n and k = k(n). In particular, find the value of k corresponding to
n = 1 000 000.
Hint: If f (x) = x(x − 1) . . . (x − k + 1), then f (x)/k! is an integer for every integer x: xk if x ≥ k, 0 for

0 ≤ x < k and −x+k−1

k for x < 0. One deduces that f (x) is always divisible by k!, and if one shows that
one cannot find a integer N > k! such that there exists a monic polynomial of degree k whose values are
always multiple of N , then k(n) will be the smallest k such that k! is a multiple of n. For n = 106 the
smallest value is k = 25, as 24! is only divisible by 54 .
If g is any function, then the first difference of g is the function g1 defined by g1 (x) = f (x)−f (x−1), the
second difference of g is the first difference of g1 , i.e. function g2 defined by g2 (x)
Pm = f (x)−2f (x−1)+f (x−2),
and so on, the mth difference of g being the function gm defined by gm (x) = j=0 (−1)j m


j g(x − j). If g is
k−1
a monic polynomial of degree k, then g1 is a polynomial of degree k − 1 with leading coefficient k x , and
gm is a polynomial of degree k − m with leading coefficient k(k − 1) . . . (k − m + 1)xk−m , so that the k th

2
difference of a monic polynomial of degree k is k!. If all values g(x) are multiple of N when x is an integer,
this is also true of the successive differences of g, and therefore if g is a monic polynomial of degree k, N
should divide its k th difference k!.