From jwu@cadvision.com Sat Nov 22 20:46:02 1997 Return-Path: Received: from huey.cadvision.com (huey2.cadvision.com [207.228.64.5]) by clinch.math.niu.edu (8.8.5/8.8.5) with ESMTP id UAA20172 for ; Sat, 22 Nov 1997 20:46:01 -0600 (CST) Received: from jwu.cadvision.com (ts85ip16.cadvision.com [207.228.71.16]) by huey.cadvision.com (8.8.5/8.8.5/DCE/TRI) with SMTP id TAA07756 for ; Sat, 22 Nov 1997 19:45:54 -0700 From: "eggkai" To: "Dave Rusin" Subject: Re: Putnam 1989 solution Date: Sat, 22 Nov 1997 19:45:16 -0700 Message-ID: <01bcf7b9$d5a063c0$1047e4cf@jwu.cadvision.com> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 4.71.1712.3 X-MimeOLE: Produced By Microsoft MimeOLE V4.71.1712.3 Status: RO >Not handy, but I remember doing the problems (I almost always do them alongside >the students, so the problems back to about 1977 (!) are familiar to me.) >So if you get stuck, drop me a line. >dave > First of all, thank you for your time. I am only a high school student, so I won't bother you with calculus problems. 1989, A-1 How many promes among the positive itegers, written as usual in base 10, are alternating 1's and 0's, beginning and ending with 1? 1989,A-3 Prove that if 11z^10 +10iz^9 + 10iz - 11 = 0 then |z|=1. (Here z is a complex number and i^2=-1) 1989, A-4 If alpha is an irrational nmber, 0 < alpha < a, is there a finite game with an honest coin such that the probability of one player winning the game is alpha? (An honest coin is one for which the probability of heads and the probability of tails are both 1/2. A game is finite if with probability 1 it must end in a finite number of moves.) 1989 B-1 A dart, thrown at random, hits a square target. Assuming that any two parts of the target of equal area are equally likely to be hit, find the probability that the point hit is nearer to the center than to any edge. Express your answer in the form (a*sqrt(b) + c)/d, where a, b, c, d are integers. From rusin Sat Nov 22 22:46:40 1997 Return-Path: Received: from vesuvius.math.niu.edu.niu.edu (vesuvius.math.niu.edu [131.156.3.93]) by clinch.math.niu.edu (8.8.5/8.8.5) with SMTP id WAA20277; Sat, 22 Nov 1997 22:46:38 -0600 (CST) Date: Sat, 22 Nov 1997 22:46:38 -0600 (CST) From: Dave Rusin Message-Id: <199711230446.WAA20277@clinch.math.niu.edu> To: jwu@cadvision.com Subject: Re: Putnam 1989 solution Cc: rusin Status: RO >1989, A-1 >How many promes among the positive itegers, written as usual in base 10, are >alternating 1's and 0's, beginning and ending with 1? The numbers are (10^(2n)-1)/99 but 10^(2n)-1 = (10^n-1)*(10^n+1). So the only way you'll get a prime is if one of those two factors is 99 >1989,A-3 >Prove that if > 11z^10 +10iz^9 + 10iz - 11 = 0 >then |z|=1. (Here z is a complex number and i^2=-1) I'm sure there was a slick argument, but right now this is what i would do. Multiply this polynomial by its complex conjugate to get a polynomial whose roots occur in complex pairs. That polynomial is 121(z^20+1) + 100(z^18+z^2) - 42z^10 Well, the roots of this are the square roots of the roots of 121(z^10+1) + 100(z^9+z) - 42z^5 so it is necessary and sufficient to show _these_ roots lie on the unit circle. Now, the symmetry in the coefficients is a sign to use this trick: divide by z^5 and then set q=z+1/z. You'll get a polynomial in q: 121*q^5 + 100*q^4 - 605*q^3 - 400*q^2 + 605*q + 158 This changes sign between q=2 and q=1, q=1 and q=0, and between q=0 and q=-1. Also (looking near the roots of its derivative) it becomes positive near q=-7/4 before becoming negative again. Thus, 5 real roots in [-2,2]. We don't need to know anything else about those roots. Now recover the z's using z^2-qz+1=0. Since |q|<2, z is of the form z=(1/2)(q +- i*sqrt(4-q^2) ). The norm of this complex number is 1. >1989, A-4 >If alpha is an irrational nmber, 0 < alpha < a, is there a finite game with >an honest coin such that the probability of one player winning the game is >alpha? (An honest coin is one for which the probability of heads and the >probability of tails are both 1/2. A game is finite if with probability 1 it >must end in a finite number of moves.) I seem to recall the answer is "yes". and you construct the game using the expansion of alpha in binary, but I can't recall offhand the construction. >1989 B-1 >A dart, thrown at random, hits a square target. Assuming that any two parts >of the target of equal area are equally likely to be hit, find the >probability that the point hit is nearer to the center than to any edge. >Express your answer in the form (a*sqrt(b) + c)/d, where a, b, c, d are >integers. We seek the area of that portion of the unit square which is closer to the center than the edges. The boundary of this region is the set of points whose distance from the origin (sqrt(x^2+y^2) ) equals the distance to the nearest edge (if the nearest edge is the top one, for example, that distance is 1-y). This leads to equations like x^2+y^2=(1-y)^2, which unscrambles to x^2=1-2y, which is a parabola. Thus the region in question is bounded by four parabolas, and we simply take four times the area of one pie-shaped piece. The top one, say, is bounded by the parabola y=(1/2)-(1/2)x^2 and the lines y=x and y=-x. This being the 20th century, no one knows how to get the area except by integration, but that's OK; integrate y from x=-r to x=+r (r a root of x = (1/2) - (1/2)x^2), the subtract the area of the triangles at the sides of the pie piece. I get r=sqrt(2)-1, the integral is r-r^3/3, the triangles are each r^2/2, the pie piece is then r-r^3/3-r^2=(4/3)sqrt(2)-5/3. So the whole shebang is (16 sqrt(2)-20)/3, if my arithmetic is right (no promises). Hope this isn't too sketchy. Look for the Amer Math Monthly for details. Good luck. dave