==> 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.