Newsgroups: rec.puzzles,news.answers,rec.answers From: chris@questrel.questrel.com (Chris Cole) Subject: rec.puzzles Archive (competition), part 09 of 35 Message-Id: Summary: This is part of an archive of questions and answers that may be of interest to puzzle enthusiasts. Part 1 contains the index to the archive. Read the rec.puzzles FAQ for more information. Date: Wed, 18 Aug 1993 06:04:57 GMT Archive-name: puzzles/archive/competition/part4 Last-modified: 17 Aug 1993 Version: 4 ==> 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 ; 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 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. Source: ftp://rtfm.mit.edu/pub/usenet/news.answers/puzzles/archive/competition/part4