lotus

previous page: 144 competition/tests/math/putnam/putnam.1967.p
  
page up: Puzzles FAQ
  
next page: 146 competition/tests/math/putnam/putnam.1988.p

145 competition/tests/math/putnam/putnam.1987.p




Description

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.

145 competition/tests/math/putnam/putnam.1987.p


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 have

Z(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 have

3^(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:













TOP
previous page: 144 competition/tests/math/putnam/putnam.1967.p
  
page up: Puzzles FAQ
  
next page: 146 competition/tests/math/putnam/putnam.1988.p