Solutions to the Problems of the 1994 William Lowell Putnam
Mathematical Competition
by Kiran Kedlaya (kedlaya@math.harvard.edu)
Disclaimer: These are mostly the solutions I submitted, with occasional
replacements when I found out about something prettier.
I've used TeX-style notation, but the file isn't TeX-ready. (A lot of
dollar signs are missing, for one thing.)
A1:
Let s_1 = a_1, s_2 = a_2 + a_3, s_3 = a_4 + a_5 + a_6 + a_7, etc.
Since all terms are positive, the sum a_1 + a_2 + ... can be rewritten as
s_1 + s_2 + .... But for any n,
s_n = a_{2^{n-1}} + ... + a_{2^n - 1}
<= (a_{2^n} + a_{2^n + 1}) + ... + (a_{2^{n+1} - 2} + a_{2^{n+1}-1}
= s_{n+1}.
Since s_1 = a_1 > 0, the terms of s_n aren't going to 0, so the sum diverges.
A2:
Remember that area ratios are preserved by affine projection. In
particular, let x' = x/3, y' = y. Then the problem is to find m such that
the area of the region in the first quadrant bounded by the line y' = 3x'/2,
the x'-axis, and the circle x'^2 + y'^2 = 1 is the same as the area of the
region in the first quadrant bounded by the line y' = 3mx', the y'-axis,
and the circle x'^2 + y'^2 = 1. By the symmetry of the diagram, it's
clear that the slopes should be reciprocal; i.e. 3m = 2/3, so m = 2/9.
A3:
Suppose such a coloring exists; let A be the right-angle vertex and
B, C the other two vertices. Choose D on side AB so that BD = x, where
hereafter x = 2 - \sqrt 2; choose E on side AC so CE = x. You can easily
check that also DE = x. It follows that any two of B,C,D,E are at
distance at least x, so they are of four different colors, say 1,2,3,4,
respectively. A must be one of these colors; but AB = AC = 1 > x, so A is
colored 3 or 4. Without loss of generality say A is colored 3. Put F on
side BC so that BF = x; then BDEF is a parallelogram, so EF = x, and
clearly CF > x. Thus C can't be colored 1, 2 or 4, so C is colored 3. But
A and C have the same color and AC is at least the altitude from A, which
is \sqrt{2} / 2 > x. Contradiction.
Aside: this coloring can be completed so that no two points of the same
color are at distance strictly greater than x. Draw a disk of radius x
around B; use color 1 for its intersection with the triangle. Do the same
around C in color 2. Color triangle ADE (minus points D and E) in 3, and
the rest in 4.
A4:
First recall that an integer matrix A has an integer inverse if and
only if det A = +- 1. Proof: clearly if A^{-1} has integer entries, then
1 = det AA^{-1} = det A det A^{-1} so det A divides 1. Conversely, if det
A = +- 1, A^{-1} equals 1/det A times the signed cofactor matrix of A,
which has integer entries.
So let f(n) = det A + nB. Clearly f is a quadratic polynomial in n with
integer coefficients (just write it out in terms of the entries); our
claim is that if f(i) \in {1, -1} for i = 0, 1, 2, 3, 4, then f(n) = +- 1
for all n.
Note that since f has integer coefficients, x - y divides f(x) - f(y) for
any integers x and y. (If f(x) = a_nx^n + ... + a_0, then f(x) - f(y) =
a_n(x^n - y^n) + a_{n-1}(x^{n-1} - y^{n-1}) + ... and each term is
divisible by x - y.) But if x and y both belong to {0, 1, 2, 3, 4} and
|x-y| > 3, then |f(x) - f(y)| \leq |f(x)| + |f(y)| = 2, so f(x) - f(y)
must be 0. Using this, we conclude f(3) = f(0) = f(4) = f(1) (apply what
I just said to the two sides of each equality). Thus the quadratic
polynomial f(n) - f(1) has four zeroes; that's too many, so it must be
the zero polynomial, and f(n) = f(1) = +- 1 for all x.
Aside: A, ..., A+3B is not enough: put A = -1 1 and B = 1 0
1 -2 0 1.
A5:
Let A be the set of all numbers representable as a sum of 1994 OR
FEWER distinct elements of the sequence. I claim A is the closure of S.
Proof: Given a sequence of tuples (i_1, ..., i_1994) such that
r_{i_1} + ... + r_{i_{1994}} converges, either the sequence of values of
i_1 takes some value infinitely often, or each value only occurs finitely
often, so the sequence of r_{i_1} values converges to 0. In the former
case, pass to a subsequence for which i_1 is constant, in the latter case
keep the same sequence. Repeat this operation for i_2, ..., i_{1994}. The
result is a sequence with r_{i_1} + ... + r_{i_{1994}} converging to the
same limit, but each term either is constant or goes to 0. So the limit
is clearly the sum of the constant r_{i_k} terms, so belongs to A.
(Conversely, every element of A is the limit of terms of S, but I don't
need that.)
But A is a countable set, and (a, b) is uncountable. Thus some point c in
(a, b) is not in A; that means that some small interval around c contains
no points of S. Take d > c inside that interval; then (c, d) is what we want.
A6:
Let F_i = the "set" of functions f_i^{e_i} \circ ... \circ f_10^{e_10}.
Assume more than half of F = F_1 fixes some set A. We shall prove the
following statements simultaneously by induction:
P_i: f_i maps A to A.
Q_i: More than half of F_i fixes A.
The implication will be Q_1 -> P_1 -> Q_2 -> ... -> P_10, where Q_1 holds
by assumption.
So first we assume Q_i. By the pigeonhole principle, there are
two functions in F_i that differ only in their value of e_i. Call them g
and f_i \circ g. Then f_i(A) = (f_i \circ g)(g^{-1}(A)) = (f_i \circ
g)(A) = A, so P_i holds.
Now assume P_i and Q_i. Since f_i(A) = A, if f_i^{e_i} ... f_{10}^{e_{10}}
maps A to A, so does f_{i+1}^{e_{i+1}} ... f_{10}^{e_{10}}. Since every
function of the latter form comes from exactly two functions of the
former form, and more than half of F_i fixes A, more than half of
F_{i+1} fixes A also.
Hence all the f_i fix A. But then if 0 is in A, no composition of the f_i
will map it to anything not in A, and vice versa. Contradiction.
Aside: A does not have to be finite as long as it is not all integers.
Equality occurs for f_1(n) = n+1, f_2(n) = n-1, and the rest are the
identity function. (Or f_1 maps 0 -> 1 -> -1 -> 2 -> -2 ... and the rest
are the identity map.)
B1:
What a mess! First note that if m >= 11, then (m + 14)^2 - m^2 = 28m
+ 196 >= 308 + 196 > 500. So no number can be within 250 of 15 squares if the
smallest one is 11^2 or greater. Hence all "good" numbers are at most
10^2 + 250 = 350. Now just count:
0 <= n <= 250: within 250 of 0^2, ..., 15^2 and maybe more. No good.
251 <= n <= 299: within 250 of 7^2, ..., 22^2 and maybe more. No good.
299 <= n <= 314: within 250 of 8^2, ..., 23^2. No good.
315 <= n <= 325: within 250 of 9^2, ..., 23^2. Good.
326 <= n <= 331: within 250 of 9^2, ..., 24^2. No good.
331 <= n <= 350: within 250 of 10^2, ..., 24^2. Good.
So the good n are 315, ..., 325, 332, ..., 350.
B2:
The desired c are all those less than 243/8. First note that a
necessary condition is that the second derivative is not everywhere
nonnegative, or else the graph is convex and any line meets it at most twice.
So the polynomial 12x^2 + 54x + 2c has negative discriminant, i.e. 54^2 >
4(24 c), which reduces to c < 243/4.
In that case the second derivative has two distinct zeroes, corresponding
to inflection points of the curve. Draw the line through these two
points. Note that the slope decreases between the two points (since the
curve is concave there) and equals the slope of the line somewhere in the
middle (by the Mean Value Theorem). Hence the slope of the curve is greater
than that of the line at the first point, and less at the
second. This means the curve lies below the line just before the first
point and just after the second; by continuity, the curve must
intersect the line again before the first point and after the second.
B3:
The desired k are those less than 1.
First we show that k < 1 all work. We have f'(x)/f(x) > 1 for all x.
Integrating from 0 to 1 gives log f(x) - log f(0) > x, so log f(x) > x +
log f(0). Clearly this eventually exceeds kx for fixed k < 1, so for
large x, f(x) > e^{kx}.
Now we show that k = 1 (and hence anything larger) does not work. Let
f(x) = exp (x - g(x)), where g(x) is everywhere positive and decreasing.
(I used g(x) = e^{-x}.) Then f'(x) = (1 - g'(x)) exp (x - g(x)). Since
g'(x) < 0 for all x, f'(x) > exp (x - g(x)) = f(x). However, since g(x) >
0 for all x, f(x) < e^x for all x.
B4:
By induction one easily shows that A has the form a_n b_n
2b_n a_n
for all n, where a_n is odd. And a_n^2 - 2b_n^2 = det A^n = (det A)^n = 1.
Thus (a_n + 1)(a_n - 1) = 2b_n^2. The greatest common divisor of the
terms on the left divides their difference, namely 2. For the same
reason, one of the terms on the left is divisible by 2 but not by 4.
Dividing that term by 2 leaves two relatively prime integers
whose product is b_n^2, a perfect square. Hence each of the two is a
perfect square. That means either \sqrt{a_n - 1} or \sqrt{(a_n - 1)/2}
(depending on which term the 2 came out of) is an integer and a divisor
of b_n. So d_n >= \sqrt{(a_n - 1)/2} -> infinity.
Aside: one can show (as I did) that a_{2n}-1 and b_{2n} are divisible by b_n,
and that a_{2n-1}-1 and b_{2n-1} are divisible by 2 b_n - a_n. I do this by
solving a recurrence relation for a_n and b_n.
In fact, a_n + b_n \sqrt{2} = (3 + \sqrt{2})^n.
B5:
Notation: [a] denotes the greatest integer less than or equal to a.
It turns out alpha = 1 - 1/(n^2) works. One checks that for k = 1, ...,n^2,
[k alpha] = [k - k/n^2] = k-1, so f^k (n^2) = n^2 - k, as desired.
We also want to show that [alpha^k n^2] = n^2 - k, i.e.
n^2 - k <= (1 - 1/n^2)^k n^2 and (1 - 1/n^2)^k n^2 < n^2 - k + 1, or
1 - k/n^2 <= (1 - 1/n^2)^k and (1 - 1/n^2)^k < 1 - (k-1)/n^2
for k= 1, ..., n.
The first inequality follows from Bernoulli's inequality: if x > -1 and k
> 1, then (1 + x)^k >= 1 + kx. This is because (1 + x)^k is a convex
function and y = 1 + kx is the tangent to the curve at x=0. Apply
Bernoulli to x = -1/n^2 to get what we need.
The second inequality follows from a sort of reversed Bernoulli's
inequality: if 0 < x < 1 and k > 1, then (1 - x)^k < 1 - kx + k(k-1)x^2/2.
(All I did was pull out the first three terms of the power series.)
I have no better proof of this than calculus: define
f(x) = 1 - kx + k(k-1)x/2 - (1-x)^k;
then f'(x) = k(k-1)x - k + k(1 - x)^{k-1}
f''(x) = k(k-1) - k(k-1)(1-x)^{k-2} > 0 since 1 - x < 1.
Moreover f(0) = f'(0) = 0. Since f''(x) > 0, f'(x) is increasing. It
starts at 0, so it must be positive. Thus f(0) is increasing, and it too
starts at 0, so it must be positive.
Putting in x = 1/n^2 gives
(1 - 1/n^2)^k < 1 - k/n^2 + k(k-1)x/(2 n^4)
< 1 - k/n^2 + k^2 /n^4
<= 1 - k/n^2 + 1/n^2 = 1 - (k-1)/n^2,
as desired.
B6:
Notation: a = b (c) means a is congruent to b modulo c, i.e. c divides a-b.
Lemma: 2 is a primitive root mod 101 (which is prime). That means
that every number not divisible by 101 is congruent to some power of 2
mod 101. Equivalently, 2^n = 1 (101) if and only if 100 | n.
Proof of Lemma: 100 | n implies 2^n = 1 (101) by Fermat's Little Theorem.
Conversely, define d as the order of 2 mod 101, the smallest positive
integer such that 2^d = 1 (101). Then if 2^n = 1 (101), write n = qd + r
where 0 <= d < r (simple division). Then 2^r = 1 (101) also, but r is
smaller than the smallest positive integer such that 2^d = 1 (101). So r
is not positive, it's zero, and d divides n.
In particular, we know d | 100 since 2^100 = 1 (101). So to find d we
compute 2^d (101) for d = 1, 2, 4, 5, 10, 20, 25, 50, 100. It turns out
only the last is 1; we'll need that 2^50 = -1 (101) later. Thus 2^n = 1
(101) implies 100 | d. (Actually not a hard computation: for example,
2^10 = 1024 = 14 (101) so 2^20 = 14^2 = 196 = -6 (101), and 2^25 = 2^5
2^20 = -6(32) etc.)
Now suppose n_a + n_b = n_c + n_d (10100). Since 100 and 101 divide
10100, this also holds mod 100 and 101, giving
[1] a + b = c + d (100)
[2] 2^a + 2^b = 2^c + 2^d (101).
Define polynomials f(x) = (x - 2^a)(x - 2^b) = x^2 - (2^a + 2^b)x +
2^{a+b} and g(x) = (x - 2^c)(x - 2^d) = x^2 - (2^c + 2^d)x + 2^{c+d}. By
Little Fermat again, [1] implies 2^{a+b} = 2^{c+d} (101), so f(x) = g(x)
(101) for all integers x. In particular, 0 = f(2^c) = (2^c - 2^a)(2^c -
2^b) (101), and the product of two integers is divisible by the prime 101
only if one of them is. Suppose 2^a - 2^c = 0 (101). Then 2^{a-c} = 1
(101), and by the lemma, a = c (100), which implies b = d (100).
(Similarly, if 2^c - 2^b = 0 (101), then b = c (100) and a = d (100).)
But since a,b,c,d are all between 0 and 99, these last congruences are
equalities so {a,b} = {c,d}.
