textfiles/science/putnam.92

From: brnstnd@ocf.berkeley.edu (Dan Bernstein)
Newsgroups: sci.math
Subject: 1992 Putnam problems and unofficial solutions
Date: 7 Dec 1992 20:20:44 GMT
Message-ID: <1g0bmsINNh22@agate.berkeley.edu>
Organization: IR
Lines: 513

As usual, first come the problems, then the problems with solutions.
Send any followup remarks to the USENET newsgroup sci.math.


Problem A1

Prove that f(n) = 1 - n is the only integer-valued function defined on
the integers that satisfies the following conditions.
(i) f(f(n)) = n, for all integers n;
(ii) f(f(n + 2) + 2) = n for all integers n;
(iii) f(0) = 1.


Problem A2

Define C(alpha) to be the coefficient of x^1992 in the power series
expansion about x = 0 of (1 + x)^alpha. Evaluate

\int_0^1  C(-y-1) ( 1/(y+1) + 1/(y+2) + 1/(y+3) + ... + 1/(y+1992) )  dy.


Problem A3

For a given positive integer m, find all triples (n,x,y) of positive
integers, with n relatively prime to m, which satisfy (x^2 + y^2)^m = (xy)^n.


Problem A4

Let f be an infinitely differentiable real-valued function defined on
the real numbers. If

f(1/n) = n^2/(n^2 + 1), n = 1,2,3,...,

compute the values of the derivatives f^(k)(0), k = 1,2,3,... .


Problem A5

For each positive integer n, let

a_n = {  0 if the number of 1's in the binary representation of n is even,
         1 if the number of 1's in the binary representation of n is odd.

Show that there do not exist positive integers k and m such that

a_{k+j} = a_{k+m+j} = a_{k+2m+j},  for 0 <= j <= m - 1.


Problem A6

Four points are chosen at random on the surface of a sphere. What is the
probability that the center of the sphere lies inside the tetrahedron
whose vertices are at the four points? (It is understood that each point
is independently chosen relative to a uniform distribution on the sphere.)


Problem B1

Let S be a set of n distinct real numbers. Let A_S be the set of numbers
that occur as averages of two distinct elements of S. For a given n >= 2,
what is the smallest possible number of distinct elements in A_S?


Problem B2

For nonnegative integers n and k, define Q(n,k) to be the coefficient of
x^k in the expansion of (1+x+x^2+x^3)^n. Prove that

Q(n,k) = \sum_{j=0}^n {n \choose j} {n \choose k - 2j},

where {a \choose b} is the standard binomial coefficient. (Reminder: For
integers a and b with a >= 0, {a \choose b} = a!/b!(a-b)! for 0 <= b <= a,
and {a \choose b} = 0 otherwise.)


Problem B3

For any pair (x,y) of real numbers, a sequence (a_n(x,y))_{n>=0} is
defined as follows:

a_0(x,y) = x
a_{n+1}(x,y) = ( (a_n(x,y))^2 + y^2 ) / 2, for all n >= 0.

Find the area of the region  { (x,y) | (a_n(x,y))_{n>=0} converges }.


Problem B4

Let p(x) be a nonzero polynomial of degree less than 1992 having no
nonconstant factor in common with x^3 - x. Let

( d^1992 / dx^1992 ) ( p(x) / x^3 - x )  =  f(x) / g(x)

for polynomials f(x) and g(x). Find the smallest possible degree of f(x).


Problem B5

Let D_n denote the value of the (n-1) by (n-1) determinant

| 3 1 1 1 ...  1  |
| 1 4 1 1 ...  1  |
| 1 1 5 1 ...  1  |
| 1 1 1 6 ...  1  |
| . . . . ...  .  |
| 1 1 1 1 ... n+1 |

Is the set {D_n/n!}_{n >= 2} bounded?


Problem B6

Let M be a set of real n by n matrices such that
(i) I \in M, where I is the n by n identity matrix;
(ii) if A \in M and B \in M, then either AB \in M or -AB \in M, but not both;
(iii) if A \in M and B \in M, then either AB = BA or AB = -BA;
(iv) if A \in M and A \noteq I, there is at least one B \in M such that
     AB = -BA.

Prove that M contains at most n^2 matrices.
 
Now the unofficial solutions. Thanks to Noam Elkies for the B6 solution;
thanks also to Peter Akemann, Greg John, and Peter Montgomery.

The Putnam exam deserves criticism this year for an exceptional number
of typos and poorly worded problems. How can someone taking the Putnam
be sure that his solutions will be graded carefully, if the exam itself
shows sloppy typography, grammar, and style?


Problem A1

Prove that f(n) = 1 - n is the only integer-valued function defined on
the integers that satisfies the following conditions.
(i) f(f(n)) = n, for all integers n;
(ii) f(f(n + 2) + 2) = n for all integers n;
(iii) f(0) = 1.

(The comma in (i) is wrong. Either ``conditions.'' should be
``conditions:'' or the semicolons should be periods. Little things...)

Solution: Certainly if f(n) = 1 - n then (i), (ii), and (iii) hold.
Conversely, say (i), (ii), and (iii) hold. We show that f(k) = 1 - k
and f(1 - k) = k for every k >= 0. For k = 0 and 1 we have f(0) = 1 and
f(1) = f(f(0)) = 0. For k >= 2, by induction we have f(k - 2) = 3 - k
and f(3 - k) = k - 2. Note that f(n + 2) + 2 = f(f(f(n + 2) + 2)) = f(n).
So f(k) = f(k - 2) - 2 = 1 - k and f(1 - k) = f(3 - k) + 2 = k as desired.
As k and 1 - k for k >= 1 cover the integers, we are done.


Problem A2

Define C(alpha) to be the coefficient of x^1992 in the power series
expansion about x = 0 of (1 + x)^alpha. Evaluate

\int_0^1  C(-y-1) ( 1/(y+1) + 1/(y+2) + 1/(y+3) + ... + 1/(y+1992) )  dy.

Solution: C(alpha) is given by the usual binomial coefficient formula
{alpha \choose 1992} = \alpha (\alpha - 1) ... (\alpha - 1991) / 1992!.
Hence C(-y-1) = (-y-1)(-y-2)...(-y-1992)/1992! = (y+1)...(y+1992)/1992!.
Set f(y) = (y+1)(y+2)...(y+1992). Now f has logarithmic derivative
f'/f = ( 1/(y+1) + 1/(y+2) + ... + 1/(y+1992) ). Hence our integral
equals \int_0^1 f(y)/1992! f'(y)/f(y) dy = \int_0^1 f'(y) dy/1992! =
(f(1) - f(0))/1992! = (1993! - 1992!)/1992! = 1993 - 1 = 1992.


Problem A3

For a given positive integer m, find all triples (n,x,y) of positive
integers, with n relatively prime to m, which satisfy (x^2 + y^2)^m = (xy)^n.

Solution: Certainly xy < x^2 + y^2 so m < n. Put n = m + k, k > 0.
Let d be the greatest common divisor of x and y. Say x = ds, y = dt.
Now d^{2m}(s^2 + t^2)^m = d^{2n}(st)^n, so (s^2 + t^2)^m = d^{2k}(st)^n.
If a prime p divides s then p divides d^{2k}(st)^n = (s^2 + t^2)^m,
so p must divide t. But s and t are relatively prime. Hence s = 1.
Similarly t = 1. So d^{2k} = 2^m. Hence d is a power of 2, say d = 2^j,
and m = 2jk. As n = m + k = 2jk + k we see that k is a common factor of
m and n. Thus k = 1. So m = 2j, n = 2j + 1, x = y = d = 2^j. If m is odd
then there are no solutions; if m is even then the only possible solution
is (m + 1,2^{m/2},2^{m/2}). This does satisfy the given conditions.


Problem A4

Let f be an infinitely differentiable real-valued function defined on
the real numbers. If

f(1/n) = n^2/(n^2 + 1), n = 1,2,3,...,

compute the values of the derivatives f^(k)(0), k = 1,2,3,... .

(``Let f be a foo. If bar, compute blah.'' Does this mean that one need
only answer the question if ``bar'' happens to be true? May one choose
his favorite f, such as f(x) = x, observe that it does not satisfy ``bar'',
and [successfully] answer the question without computing anything?
``If ..., compute'' should be ``Assume ... . Compute''.)

Solution: We first observe that the function g(x) = 1/(1 + x^2) satisfies
all the known properties of f: it is infinitely differentiable, and
g(1/n) = n^2/(n^2 + 1). From the Taylor expansion of g around 0,
g(x) = 1 - x^2 + x^4 - x^6 + ..., we see that g^(k)(0) is 0 for k odd,
(-1)^{k/2}k! for k even.

Can f differ from g in its derivatives at 0? The difference h = f - g
is an infinitely differentiable function with roots at 1/n for every
positive n. We show that any such function has all derivatives 0 at 0.
Suppose not. Take the least k >= 0 for which h^(k)(0) is nonzero.
Without loss of generality say it is positive. By continuity h^(k) is
positive in an open interval U around 0. Let S be the set of positive
elements of U. Now h^(k-1) is increasing on S, and by minimality of k
we have h^(k-1)(0) = 0, so h^(k-1) is positive on S. Then h^(k-2) is
increasing on S, and h^(k-2)(0) = 0, so h^(k-2) is positive on S. In
general h^j is positive on S for j down from k to 0 by induction. In
particular h is positive on S, but this is impossible, as 1/n is in S
for n sufficiently large.

Thus f has all the same derivatives as g: f^(k)(0) is 0 for k odd,
(-1)^{k/2}k! for k even.


Problem A5

For each positive integer n, let

a_n = {  0 if the number of 1's in the binary representation of n is even,
         1 if the number of 1's in the binary representation of n is odd.

Show that there do not exist positive integers k and m such that

a_{k+j} = a_{k+m+j} = a_{k+2m+j},  for 0 <= j <= m - 1.

(Is every student supposed to know what the writer means by ``the binary
representation of n''? Anyway, this problem is well known in some circles.
I don't think Putnam writers should copy problems.)

Solution: Let us suppose the opposite. Pick m minimal such that, for
some k, a_{k+j} = a_{k+m+j} for every 0 <= j <= 2m - 1. The minimality
guarantees that m is odd. (Indeed, say m = 2m'. If k = 2k' is even,
then put j = 2j' for 0 <= j' <= m - 1 = 2m' - 1. Now a_n = a_{2n} so
a_{k'+j'} = a_{k+j} = a_{k+m+j} = a_{k'+m'+j'} as desired. If on the
other hand k = 2k' - 1 is odd, then put j = 2j' + 1 for 0 <= j' <= 2m' - 1.
Now a_{k'+j'} = a_{k+j} = a_{k+m+j} = a_{k'+m'+j'} as desired.)

We cannot have m = 1. Indeed, if a_k = a_{k+1} = a_{k+2}, then we have
a_{2n} = a_{2n+1} for n = k/2 if k is even or n = (k+1)/2 if k is odd.
But a_{2n} + a_{2n+1} = 1 always. Hence m is an odd number greater than 1.

Define b_n = (a_n + a_{n-1}) mod 2. For 1 <= j <= 2m - 1 we have
b_{k+j} = b_{k+m+j}. This range of j covers at least 5 values; we can
certainly choose j so as to make k+j equal to 2 mod 4. Then k+m+j is
odd. But b_n is 0 when n is 2 mod 4, and b_n is 1 when n is odd, so we
have a contradiction.


Problem A6

Four points are chosen at random on the surface of a sphere. What is the
probability that the center of the sphere lies inside the tetrahedron
whose vertices are at the four points? (It is understood that each point
is independently chosen relative to a uniform distribution on the sphere.)

Solution: Pick three points A, B, C, and consider the spherical triangle
T defined by those points. The center of the sphere lies in the convex
hull of A, B, C, and another point P if and only if it lies in the convex
hull of T and P. This happens if and only if P is antipodal to T. So the
desired probability is the expected fraction of the sphere's surface area
which is covered by T.

Denote the antipode to a point P by P'. We consider the eight spherical
triangles ABC, A'BC, AB'C, A'B'C, ABC', A'BC', AB'C', A'B'C'. Denote
these by T_0, T_1, T_2, T_3, T_4, T_5, T_6, T_7; we regard each T_i
as a function of the random variables A, B, C. There is an automorphism
of our probability space defined by (A,B,C) -> (A,B,C'). Hence T_0 and
T_4 have the same distribution, and similarly T_1 and T_5, T_2 and T_6,
and T_3 and T_7. Of course the same applies to B, so that T_0 and T_2,
T_1 and T_3, T_4 and T_6, and T_5 and T_7 all have the same distribution.
Finally T_0 and T_1, T_2 and T_3, T_4 and T_5, and T_6 and T_7 all have
the same distribution. We conclude that all the T_i have exactly the
same distribution. In particular the fractional area A_i of T_i has the
same distribution for all i.

On the other hand the total fractional area of all the T_i is exactly
1: the eight triangles cover the sphere exactly once. Hence each T_i
has expected fractional area 1/8. In particular, T_0, the probability we
wanted, has expected value 1/8.

Note that this proof does not require the full strength of uniform
distribution in the usual measure; nor does it require independence
between all the variables. It requires only certain automorphisms of
the probability space.


Problem B1

Let S be a set of n distinct real numbers. Let A_S be the set of numbers
that occur as averages of two distinct elements of S. For a given n >= 2,
what is the smallest possible number of distinct elements in A_S?

(``Smallest possible number of distinct elements in A_S''? Who talks
about ``the number of _distinct_ elements'' of a set? How about just
``the number of elements''? Or ``the size''? Aargh. The quantifiers
here are completely out of whack: n has to be fixed [not ``given'']
before anything else, and it's not immediately clear that ``smallest
possible'' refers to ``the minimum over all S''. Proposed rewrite:
``Fix n >= 2. For any set S of n real numbers, let A_S be the set of
averages of two distinct elements of S. What is the minimum, over all
S, of the size of A_S?'')

Solution: We put the elements of S in order: s_1 < s_2 < ... < s_n.
We have s_1 + s_2 < s_1 + s_3 < ... < s_1 + s_{n-1} < s_1 + s_n <
s_2 + s_n < s_3 + s_n < ... < s_{n-1} + s_n. Hence the 2n - 3 averages
(s_i + s_j)/2, i < j, with i = 1 or j = n, are all distinct. So A_S
has size at least 2n - 3. This is achieved if, for instance,
S = {1,2,...,n}.


Problem B2

For nonnegative integers n and k, define Q(n,k) to be the coefficient of
x^k in the expansion of (1+x+x^2+x^3)^n. Prove that

Q(n,k) = \sum_{j=0}^n {n \choose j} {n \choose k - 2j},

where {a \choose b} is the standard binomial coefficient. (Reminder: For
integers a and b with a >= 0, {a \choose b} = a!/b!(a-b)! for 0 <= b <= a,
and {a \choose b} = 0 otherwise.)

Solution: (1+x^2)(1+x) = 1+x+x^2+x^3, so (1+x^2)^n(1+x)^n = (1+x+x^2+x^3)^n,
so (\sum {n\choose j} x^{2j}) (\sum {n\choose m} x^m) = \sum Q(n,k)x^k.
The coefficient of x^k on the left is the sum of {n\choose j}{n\choose m}
over all j,m with m + 2j = k, i.e., \sum_j {n\choose j}{n\choose k-2j}.


Problem B3

For any pair (x,y) of real numbers, a sequence (a_n(x,y))_{n>=0} is
defined as follows:

a_0(x,y) = x
a_{n+1}(x,y) = ( (a_n(x,y))^2 + y^2 ) / 2, for all n >= 0.

Find the area of the region  { (x,y) | (a_n(x,y))_{n>=0} converges }.

(The parentheses in (a_n(x,y))^2 are confusing, as the writer also
uses parentheses to denote the entire sequence of a_n.)

Solution: Note that (x,y) and (x,-y) produce the same sequence, and
(-x,y) and (x,y) produce the same sequence after the first step. So
we will restrict attention to nonnegative x and y and quadruple our
final answer.

Fix x and y. Set f(z) = ( z^2 + y^2 ) / 2, so that a_n(x,y) =
f(a_{n-1}(x,y)). Now f'(z) = z, so f is increasing on the positive reals.
So (a_n(x,y))_n is monotone---either increasing, decreasing, or constant.
We consider several (non-exclusive) possibilities.

Case 1. Say y > 1. Then f(z) > (1 + z^2)/2 + (y - 1) >= z + (y - 1), so
a_n(x,y) increases by at least y - 1 at each step.

Case 2. Say f(x) < x. Then we have 0 < a_n(x,y) < a_{n-1}(x,y) <= x for
every n. (Indeed, for n = 1 we have 0 < f(x) < x. For n >= 2 we have
a_{n-1}(x,y) < a_{n-2}(x,y) by induction. So a_n(x,y) < a_{n-1}(x,y),
as f is increasing.) As (a_n(x,y))_n is decreasing and bounded below,
it converges.

Case 3. Say f(x) > x > 1. Define g(z) = f(z) - z, so that g(x) > 0.
We have g'(z) = z - 1, so g is increasing past 1. Now a_n(x,y) >=
x + ng(x). (Indeed, for n = 1 we have a_1(x,y) = f(x) = x + g(x).
For n >= 2 set a = a_{n-1}(x,y). We have a >= x + (n-1)g(x) > x by
induction. So g(a) > g(x), and a_n(x,y) = f(a) = a + g(a) > a + g(x) >=
x + ng(x) as desired.) So a_n increases without bound.

Case 4. Say x < 1, y < 1. Then f(x) < f(1) < (1 + 1)/2 = 1. Similarly
a_n(x,y) < 1 for every n. As (a_n(x,y))_n is bounded and monotone, it
converges.

Let's put this all together. For y > 1 the sequence diverges. For y < 1
and x < 1 the sequence does converge. For y < 1 and x > 1, the sequence
converges if f(x) < x, and diverges if f(x) > x. The points we miss in
this tally---y = 1, x = 1, f(x) = x---have zero total area.

The condition f(x) < x is equivalent to (x-1)^2 + y^2 < 1, which
describes a quarter-circle of radius 1 in the region y > 0, x > 1. Thus
the total area for positive x and y is 1 (for the square y < 1, x < 1)
plus pi/4 (for the quarter-circle). The final answer is quadruple this,
or 4 + pi.


Problem B4

Let p(x) be a nonzero polynomial of degree less than 1992 having no
nonconstant factor in common with x^3 - x. Let

( d^1992 / dx^1992 ) ( p(x) / (x^3 - x) )  =  f(x) / g(x)

for polynomials f(x) and g(x). Find the smallest possible degree of f(x).

(The second sentence is backwards---``let'' should be followed
immediately by the variable being introduced. Would you say ``Let
2 equal x + y for integers x and y''?)

Solution: First divide p(x) by x^3 - x: p(x) = (x^3 - x)q(x) + r(x),
with r of degree at most 2. Now f(x)/g(x) = D^1992 (q(x) + r(x)/(x^3-x))
= D^1992 (r(x)/(x^3-x)), as q has degree less than 1992; here we write
D for d/dx. We expand r(x)/(x^3-x) in partial fractions as -r(0)/x +
r(1)/2(x-1) + r(-1)/2(x+1). Now the 1992nd derivative of this is
Cr(0)/x^1993 + Cr(1)/(x-1)^1993 + Cr(-1)/(x+1)^1993 for a certain
nonzero constant C which we don't care about. This then equals
(Cr(0)(x^2-1)^1993 + Cr(1)(x^2+x)^1993 + Cr(-1)(x^2-x)^1993)/(x^3-x)^1993.

The numerator and denominator here are coprime, for none of x, x-1, x+1
divide the numerator. (If, for instance, x divided the numerator, then
r(0) would have to be 0, but then p(x) would have a factor of x in
common with x^3-x, contrary to hypothesis.) So f(x) is a multiple of
the numerator and g(x) is a multiple of the denominator. Our question
is thus ``What is the smallest possible degree of the polynomial P =
U(x^2-1)^1993 + V(x^2+x)^1993 + W(x^2-x)^1993, over all U, V, W which
can arise as U=Cr(0), V=Cr(1), W=Cr(-1)?''

P has degree at most 2.1993. Its 2.1993 coefficient is U + V + W. Its
2.1993-1 coefficient is 1993V - 1993W. Its 2.1993-2 coefficient is
-1993U + 1993.(1992/2)V + 1993.(1992/2)W. If all three of these are
zero then by linear algebra all of U, V, W are zero, which is not
possible. Hence P, and thus also f, has degree at least 2.1993-2, or
double 1992. This is achieved if, for instance, p(x) = r(x) = 3x^2 - 2,
so that r(0)+r(1)+r(-1)=-2+1+1=0 and r(1)=r(-1).

(The degree restriction on p in this problem seems somewhat strange,
though it simplifies the solution slightly. Noam Elkies notes that
the ``nonzero constant C'' above will be zero---so that f will be 0---
if we're working over a field with characteristic dividing 1992!.
Should the problem have explicitly identified the ground field as
the reals?)


Problem B5

Let D_n denote the value of the (n-1) by (n-1) determinant

| 3 1 1 1 ...  1  |
| 1 4 1 1 ...  1  |
| 1 1 5 1 ...  1  |
| 1 1 1 6 ...  1  |
| . . . . ...  .  |
| 1 1 1 1 ... n+1 |

Is the set {D_n/n!}_{n >= 2} bounded?

(``The value of the determinant''? Why not just ``the determinant''?
Why talk about ``the set'' when it's much more common to talk about
``the sequence''? And where's the period on the first sentence?)

Solution: No, it is the harmonic series.

We subtract the first row from each of the other rows, to get a matrix
3 1 1 1 ... 1, -2 3 0 0 ... 0, -2 0 4 0 ... 0, ..., -2 0 0 0 ... n.
Then we subtract 1/3 of the new second row from the first, 1/4 of the
new third row from the first, and so on, to kill all the 1's along the
top. We are left with a triangular matrix, with diagonal X 3 4 ... n,
where X equals 3 - (-2)/3 - (-2)/4 - ... - (-2)/n =
3 + 2/3 + 2/4 + ... + 2/n = 2(1 + 1/2 + 1/3 + 1/4 + ... + 1/n). Thus
the determinant is n! times 1 + 1/2 + 1/3 + ... + 1/n. Q. E. D.


Problem B6

Let M be a set of real n by n matrices such that
(i) I \in M, where I is the n by n identity matrix;
(ii) if A \in M and B \in M, then either AB \in M or -AB \in M, but not both;
(iii) if A \in M and B \in M, then either AB = BA or AB = -BA;
(iv) if A \in M and A \noteq I, there is at least one B \in M such that
     AB = -BA.

Prove that M contains at most n^2 matrices.

Solution (courtesy Noam Elkies): Fix A in M. By (iii) AB = eBA, where e
is either +1 or -1, for any B in M. Then AAB = AeBA = eABA = e^2BAA = BAA.
So A^2 commutes with any B in M. Of course the same is true of -A^2. On
the other hand by (ii) A^2 or -A^2 is in M. Pick C = A^2 or C = -A^2 so
that C is in M.

If C is not I, then by (iv) we can find a B in M such that CB = -BC. But
we know CB = BC for any B in M. Thus CB = 0, which is impossible, as by
(ii) no two elements of M can multiply to 0.

We conclude that C must be I. In other words, for any A in M, either A^2
or -A^2 must be I.

Now suppose M has more than n^2 matrices. The space of real n by n
matrices has dimension n^2, so we can find a nontrivial linear relation
\sum_{D in M} x_D D = 0. Pick such a relation with the smallest possible
number of nonzero x_D. We will construct a smaller relation, obtaining a
contradiction and finishing the proof.

Pick an A with x_A nonzero, and multiply by it: \sum_{D in M} x_D DA = 0.
In light of (ii) the matrices DA run over M modulo sign. Hence we have a
new relation \sum_{E in M} y_E E = 0. The point of this transformation is
that now the coefficient y_I of I is +- x_A, which is nonzero.

Pick any C other than I such that y_C is nonzero. By (iv) pick B in M
such that CB = -BC. Multiply \sum_{E in M} y_E E = 0 by B on both the left
and the right, and add: \sum_{E in M} y_E (BE + EB) = 0. Now by (iii) we
have BE + EB = (1 + e_{BE})BE, where e_{BE} is either +1 or -1. In
particular e_{BI} = 1 (clear) and e_{BC} = -1 (by construction of B).
So we get \sum_{E in M} y_E (1 + e_{BE}) BE = 0, where at least one term
does not disappear and at least one term does disappear. As before the
matrices BE run over M modulo sign. So we have a relation with fewer
terms as desired.


---Dan Bernstein, brnstnd@ocf.berkeley.edu, 7 December 1992