This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

FORTY EIGHTH ANNUAL Saturday, December 5, 1987

Examination A;

Problem A-1

------- ---

Curves A, B, C, and D, are defined in the plane as follows:

A = { (x,y) : x^2 - y^2 = x/(x^2 + y^2) },

B = { (x,y) : 2xy + y/(x^2 + y^2) = 3 },

C = { (x,y) : x^3 - 3xy^2 + 3y = 1 },

D = { (x,y) : 3yx^2 - 3x - y^3 = 0 }.

Prove that the intersection of A and B is equal to the intersection of

C and D.

Problem A-2

------- ---

The sequence of digits

1 2 3 4 5 6 7 8 9 1 0 1 1 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 ...

is obtained by writing the positive integers in order. If the 10^n th

digit in this sequence occurs in the part of the sequence in which the

m-digit numbers are placed, define f(n) to be m. For example f(2) = 2

because the 100th digit enters the sequence in the placement of the

two-digit integer 55. Find, with proof, f(1987).

Problem A-3

------- ---

For all real x, the real valued function y = f(x) satisfies

y'' - 2y' + y = 2e^x.

(a) If f(x) > 0 for all real x, must f'(x) > 0 for all real x? Explain.

(b) If f'(x) > 0 for all real x, must f(x) > 0 for all real x? Explain.

Problem A-4

------- ---

Let P be a polynomial, with real coefficients, in three variables and F

be a function of two variables such that

P(ux,uy,uz) = u^2*F(y-x,z-x) for all real x,y,z,u,

and such that P(1,0,0) = 4, P(0,1,0) = 5, and P(0,0,1) = 6. Also let

A,B,C be complex numbers with P(A,B,C) = 0 and |B-A| = 10. Find

|C-A|.

Problem A-5

------- ---

^ Let G(x,y) = ( -y/(x^2 + 4y^2) , x/(x^2 + 4y^2), 0 ). Prove or disprove that there is a vector-valued function

^ F(x,y,z) = ( M(x,y,z) , N(x,y,z) , P(x,y,z) )

with the following properties:

(1) M,N,P have continuous partial derivatives for all (x,y,z) <> (0,0,0) ; ^ ^ (2) Curl F = 0 for all (x,y,z) <> (0,0,0) ; ^ ^ (3) F(x,y,0) = G(x,y).

Problem A-6

------- ---

For each positive integer n, let a(n) be the number of zeros in the

base 3 representation of n. For which positive real numbers x does

the series

inf ----- \ x^a(n) > ------ / n^3 ----- n = 1

converge?

--

Examination B;

Problem B-1

------- ---

4/ (ln(9-x))^(1/2) dx Evaluate | --------------------------------- . 2/ (ln(9-x))^(1/2) + (ln(x+3))^(1/2)

Problem B-2

------- ---

Let r, s, and t be integers with 0 =< r, 0 =< s, and r+s =< t.

Prove that

( s ) ( s ) ( s ) ( s ) ( 0 ) ( 1 ) ( 2 ) ( s ) t+1 ----- + ------- + ------- + ... + ------- = ---------------- . ( t ) ( t ) ( t ) ( t ) ( t+1-s )( t-s ) ( r ) ( r+1 ) ( r+2 ) ( r+s ) ( r ) ( n ) n(n-1)...(n+1-k) ( Note: ( k ) denotes the binomial coefficient ---------------- .) k(k-1)...3*2*1

Problem B-3

------- ---

Let F be a field in which 1+1 <> 0. Show that the set of solutions to

the equation x^2 + y^2 = 1 with x and y in F is given by

(x,y) = (1,0) r^2 - 1 2r and (x,y) = ( ------- , ------- ), r^2 + 1 r^2 + 1

where r runs through the elements of F such that r^2 <> -1.

Problem B-4

------- ---

Let ( x(1), y(1) ) = (0.8,0.6) and let x(n+1) = x(n)*cos(y(n)) - y(n)*sin(y(n)) and y(n+1) = x(n)*sin(y(n)) + y(n)*cos(y(n))

for n = 1,2,3,... . For each of the limits as n --> infinity of

x(n) and y(n), prove that the limit exists and find it or prove that

the limit does not exist.

Problem B-5

------- ---

Let O(n) be the n-dimensional zero vector (0,0,...,0). Let M be a

2n x n matrix of complex numbers such that whenever

( z(1), z(2), ..., z(2n)*M = O(n), with complex z(i), not all zero,

then at least one of the z(i) is not real. Prove that for arbitrary

real number r(1), r(2), ..., r(2n), there are complex numbers w(1),

w(2), ..., w(n) such that

( ( w(1) ) ) ( r(1) ) ( ( . ) ) ( . ) Re ( M*( . ) ) = ( . ) . ( ( . ) ) ( . ) ( ( w(n) ) ) ( r(2n) )

(Note: If C is a matrix of complex numbers, Re(C) is the matrix whose

entries are the real parts of entries of C.)

Problem B-6

------- ---

Let F be the field of p^2 elements where p is an odd prime. Suppose S

is a set of (p^2-1)/2 distinct nonzero elements of F with the property

that for each a <> 0 in F, exactly one of a and -a is in S. Let N be

the number of elements in the intersection of S with { 2a : a e S }.

Prove that N is even.

--

competition/tests/math/putnam/putnam.1987.s

Problem A-1

------- ---

Let z=x+i*y. Then A and B are the real and imaginary parts of

z^2=3i+1/z, and C, D are likewise Re and Im of z^3-3iz=1, and

the two equations are plainly equivalent. Alternatively, having

seen this, we can formulate a solution that avoids explicitly

invoking the complex numbers, starting with C=xA-yB, D=yA+xB.

Problem A-2

------- ---

Counting, we see that the numbers from 1 to n digits take

up (10^n*(9n-1)+1)/9 spaces in the above sequence. Hence we need

to find the least n for which 10^n*(9n-1)+1 > 9*10^1987, but it

is easy to see that n = 1984 is the minimum such. Therefore

f(1987) = 1984.

In general, I believe, f(n) = n + 1 - g(n), where g(n) equals

the largest value of m such that (10^m-1)/9 + 1 =< n if n>1,

and g(0) = g(1) is defined to be 0.

Hence, of course, g(n) = [log(9n-8)] if n>0. Therefore

f(0) = 1, f(n) = n + 1 - [log(9n-8)] for n>0.Q.E.D. Problem A-3 ------- --- We have a differential equation, solve it. The general solution is y = f(x) = e^x*(x^2 + a*x + b), where a and b are arbitrary real constants. Now use completing the square and the fact that e^x > 0 for all real x to deduce that (1) f(x) > 0 for all real x iff 4b > a^2. (2) f'(x) > 0 for all real x iff 4b > a^2 + 4. It is now obvious that (2) ==> (1) but (1) /==> (2). Q.E.D. Problem A-4 ------- --- Setting x=0, u=1 we find F(y,z)=P(0,y,z) so F is a polynomial; keeping x=0 but varying u we find F(uy,uz)=u^2*F(y,z), so F is homogeneous of degree 2, i.e. of the form Ay^2+Byz+Cz^2, so P(x,y,z)=R(y-x)^2+S(y-x)(z-x)+T(z-x)^2 for some real R,S,T. The three given values of P now specify three linear equations on R,S,T, easily solved to give (A,B,C)=(5,-7,6). If now P(A,B,C)=0 then (C-A)=r(B-A), r one of the two roots of 5-7r+6r^2. This quadratic has negative discrminant (=-71) so its roots are complex conjugates; since their product is 5/6, each one has absolute value sqrt(5/6). (Yes, you can also use the Quadratic Equation.) So if B-A has absolute value 10, C-A must have absolute value 10*sqrt(5/6)=5*sqrt(30)/3. Problem A-5 ------- --- There is no such F. Proof: assume on the contrary that G extends to a curl-free vector field on R^3-{0}. Then the integral of G around any closed path in R^3-{0} vanishes because such a path bounds some surface [algebraic topologists, read: because H^2(R^3-{0},Z)=0 :-) ]. But we easily see that the integral of F around the closed path z=0, x^2+4y^2=1 (any closed path in the xy-plane that goes around the origin will do) is nonzero--- contradiction. Problem A-6 ------- --- For n>0 let T(n) = x^a(n)/n^3 and U(n) = T(3n) + T(3n+1) + T(3n+2) and for k>=0 let Z(k) = sum {n=3^k to 3^(k+1)-1} T(n) We haveZ(k+1) = sum {n=3^(k+1) to 3^(k+2)-1} T(n) = sum {n=3^k to 3^(k+1)-1} [T(3n) + T(3n+1) + T(3n+2)] = sum {n=3^k to 3^(k+1)-1} U(n)

Let us compare U(n) to T(n). We have a(3n)=a(n)+1 and a(3n+1)=a(3n+2)=a(n).

Thus

U(n) = x^[a(n)+1]/(3n)^3 + x^a(n)/(3n+1)^3 + x^a(n)/(3n+2)^3

and so U(n) has as upper bound

x^a(n) * (x+2)/(3n)^3 = T(n) * (x+2)/27

and as lower bound

x^a(n) * (x+2)/(3n+2)^3 = T(n) * (x+2)/(3+2/n)^3

in other words U(n) = T(n) * (x+2)/(27+e(n)), where e(n)<(3+2/n)^3-27 tends to

0 when n tends to infinity. It follows then that

Z(k+1)= Z(k)*(x+2)/(27+f(k))

where f(k)<(3+2/3^k)^3-27 tends to 0 for n tending to infinity.

Now the series is the sum of all Z(k). Thus for x>25 we have Z(k+1)>Z(k) for k

large enough, and the series diverges; for x<25 we have Z(k+1)< r * Z(k) (with

r=(x+2)/27<1) for every k, and the series converges. For x=25 the series

diverges too (I think so), because Z(k+1)/Z(k) tends to 1 for k tending to

infinity.

Another proof:

I would say,for x<25. Let S(m) be the sum above taken over 3^m <= n < 3^(m+1).

Then for the n's in S(m), the base 3 representation of n has m+1 digits.

Hence we can count the number of n's with a(n)=k as being the number

of ways to choose a leading nonzero digit, times the number of ways

to choose k positions out of the m other digits for the k zeroes, times

the number of ways to choose nonzero digits for the m-k remaining positions,

namely( m ) m-k 2 ( ) 2 . ( k )

Hence we have3^(m+1)-1 m ----- ----- \ a(n) \ ( m ) m-k k > x = > 2 ( ) 2 x / / ( k ) ----- ----- n=3^m k=0 m = 2 (x+2) . m -3m m -3(m+1) Hence we can bound S(m) between 2 (x+2) 3 and 2 (x+2) 3 . It is then clear that the original sum converges just when inf ----- \ m -3m > (x+2) 3 converges, or when x<25. / ----- m=0

Problem B-1

------- ---

Write the integrand as(ln(x+3))^(1/2) 1 - --------------------------------- . (ln(9-x))^(1/2) + (ln(x+3))^(1/2)

Use the change of variables x = 6-t on the above and the fact that

the two are equal to deduce that the original is equal to 1.

QED.

Problem B-3

------- ---

First note that the above values for x and y imply that

x^2 + y^2 = 1. On the other foot note that if x<>1 ,x^2 + y^2 = 1,

and 2 <> 0, then (x,y) is of the required form, with r = y/(1-x).

Also note that r^2 <> -1, since this would imply x = 1.

Derivation of r: We want x = (r^2-1)/(r^2+1) ==> 1-x = 2/(r^2+1),

and also y = 2r/(r^2+1) ==> 1-x = (2y)/(2r) if 2<>0. Hence if

2<>0, r = y/(1-x).

The above statement is false in some cases if 1+1 = 0 in F. For

example, in Z(2) the solution (0,1) is not represented.

QED.

Problem B-4

------- ---

Observe that the vector (x(n+1), y(n+1)) is obtained from (x(n), y(n))

by a rotation through an angle of y(n). So if Theta(n) is the inclination

of (x(n), y(n)), then for all n,

Theta(n+1) = Theta(n) + y(n)

Furthermore, all vectors have the same length, namely that of (x1, y1),

which is 1. Therefore y(n) = sin (Theta(n)) and x(n) = cos (Theta(n)).

Thus the recursion formula becomes

(*) Theta(n+1) = Theta(n) + sin (Theta(n))

Now 0 < Theta(1) < pi. By induction 0 < sin(Theta(n)) = sin(pi - Theta(n))

< pi - Theta(n), so 0 < Theta(n+1) < Theta(n) + (pi - Theta(n)) = pi.

Consequently, {Theta(n)} is an increasing sequence bounded above by pi, so

it has a limit, Theta. From (*) we get Theta = Theta + sin(Theta),

so with Theta in the interval (0,pi], the solution is Theta = pi.

Thus lim (x(n),y(n)) = (cos(Theta), sin(Theta)) = (-1, 0).

Problem B-5

------- ---

First note that M has rank n, else its left nullspace N has C-dimension >n

and so R-dimension >2n, and thus nontrivially intersects the R-codimension

2n subspace of vectors all of whose coordinates are real. Thus the

subspace V of C^(2n) spanned by M's columns has C-dimsension n and so

R-dimension 2n, and to prove the R-linear map Re: V-->R^(2n) surjective,

we need only prove it injective. So assume on the contrary that v is

a nonzero vector in V all of whose coordinates are purely imaginary,

and let W be the orthogonal complement of <v>; this is a subspace of

C^(2n) of C-dim. 2n-1 and R-dim. 4n-2 . W contains N,

which we've seen has R-dimension 2n; it also contains the

orthogonal complement of <i*v> in R^(2n), which has R-dimension 2n-1.

Since (2n)+(2n-1) > (4n-2), these two real subspaces of W intersect

nontrivially, producing a nonzero real vector in N---contradiction.

So Re: V-->R^(2n) indeed has zero kernel and cokernel, Q.E.D. .

Problem B-6

------- ---

Let P be the product of elements of S; then P'=2^|S|*P, the product of

the elements of 2S, is either P or -P according to whether |2S-S| is

even or odd. (each element of 2S is either in S or in -S, so match

the factors in the products for P and P'.) But by Fermat's little

theorem, 2^(p-1)=1, and since |S|=(p^2-1)/2=(p-1)*(p+1)/2 is a multiple

of p-1, also 2^|S|=1 and P=P', Q.E.D. .

This solution--analogous to one of Gauss' proof of Quadratic

Reciprocity--is undoubtedly what the proposers had in mind, and had

it been the only solution, B-6 would be a difficult problem on a par

with B-6 problems of previous years. Unfortunately, just knowing

that F* is a cyclic group of order |F|-1 for any finite field F,

one can split F* into cosets of the subgroup generated by 2 and -1

and produce a straightforward, albeit plodding and uninspired, proof.

I wonder how many of the contestants' answers to B-6 went this way

and how many found the intended solution.

Another proof:

Given such a set S, it is immediate to verify that for any a in S, if

one deletes a and adjoins -a to obtain a new set S' then the number

of elements in the intersection of S' and 2S' is congruent (modulo 2)

to the number of elements in the intersection of S and 2S. If S and

S' are any two sets meeting the condition of this problem, then S can

be changed to S' by repeating this operation several times. So, it

suffices to prove the result for any one set S meeting the condition of

the problem. A simple candidate for such an S is obtained by letting

(u, v) be a basis for F over the field of p elements and letting S

be the unions of the sets {au + bv: 1 <= u <= (p-1)/2, 0 <= b < p} and

{bv: 0 <= b < (p-1)/2}. An elementary counting argument completes the

proof.

Continue to: