1992 Putnam problems and unofficial solutions

 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