Solutions to the 2001 Putnam as seen in sci.math and in email. This is sequence of messages; you might have to scroll down to see all the comments related to a single question. In particular, there is a long section at the end consisting of several approaches to resolving A6. -- dave ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: William Lowell Putnam 2001 Date: 3 Dec 2001 01:51:42 GMT In article <9ueev5$teo$1@news.math.niu.edu>, Dave Rusin wrote: >I will post some answers a little later today. OK, here you go. I lack a couple. I thought the path to the answers of most of the morning questions were pretty clear; less so about the afternoon ones. (Maybe I was getting tired!) Not much geometry, I see, and no "advanced" material (differential equations, abstract algebra). The answers below would likely be considered incomplete by the graders, e.g. I don't always write details for why the domains of functions are as indicated, etc. (I do usually think to check, though!) A1. a*(b*a) = ((b*a)*b)*(b*a) = b Remark: This has to be the shortest Putnam answer I've ever written! A2. The probability a_i of getting exactly i heads is the coefficient of x^i in F(x) = \prod_{k=1}^{k=n} ( 1/(2k+1) x + 2k/(2k+1) ) . We want the sum of the a_i with i odd, but of course the odd powers of x in a polynomial F are precisely the ones which remain in (1/2) ( F(x) - F(-x) ), so our probability is (1/2) ( F(1) - F(-1) ) = (1/2) ( 1 - \prod( (2k-1)/(2k+1) ) ) Fortunately, this product telescopes to 1/(2n+1), so that our answer is just n/(2n+1) . A3. Define Q_m(x) = x^2 - 2(m+2) x + (m-2)^2, so that P_m(x) = Q_m(x^2). If P_m has two quadratic factors, then by comparing coefficients of x^4 and x^3, we conclude the factorization is, up to sign, (x^2 + a x + b) (x^2 - a x + c) for some integers a, b, c. Expanding and comparing coefficients, we see we need a^2 - b - c = 2m+4, a(b-c)=0, bc = (m-2)^2. If a = 0, then both factors are linear in x^2, that is, we have obtained a factorization of P_m from a factorization of Q_m. But it is well known that a rational quadratic factors rationally iff the discriminant is a square, and we find the discriminant to be (2m+4)^2 - 4(m-2)^2 = 32m. Thus m/2 must be a rational (hence integral) square. When that condition holds, say m = 2n^2, then Q_m does indeed factor integrally, and hence P_m does as well. If instead a is not zero, then we must have c = b, in which case the other two equations force b = +- (m-2) and then a^2 must equal either 8 or 4m. The first is obviously impossible, so m must be a perfect square. (Conversely, in this case, we have two factors, which we check to be integral). There remains the case that P_m has a linear factor and a cubic one, but that would imply P_m has an integer root r, in which case Q_m would have an integer root (namely r^2). We have already considered the cases in which Q_m can factor over the rationals (only some of which, of course, will give P_m a _linear_ factor). So our answer is that P_m factors iff either m or m/2 is square. A4. View the plane as a vector space with origin at T and with the vectors TR and TS as a basis. We can then assign coordinates to other points in this figure. The key observations we will take from the coordinates are that (i) the coordinates of midoiuts of line segments are the averages of those of the endpoints, and (ii) collinear segments must have equal slopes. So in this coordinate system we have T=(0,0), R=(1,0), S=(0,1). The lines ST, TR, RS are, respectively, described by the equations x=0, y=0, x+y=1. Thus we may describe the original vertices as being points of the forms A=(-a,0), B=(b,1-b), C=(0,c). Using the midpoint property we compute the other points as E=(a,0), F=(2-b, b-1), G=(0,2-c). Now the collinearity conditions impose three equations on a,b,c: From AFC we have (b-1)/(2-b+a)=c/a, i.e. c=a(b-1)/(2-b+a) From BEC we have (1-b)/(b-a)=-c/a; add and get that b=a+1 (so c=a^2) From AGB we have (1-b)/(b+a)=(2-c)/a, i.e. -a/(2a+1)=(2-a^2)/a. This implies a satisfies the equation 0 = a^3 - 2a - 1, which has a=-1 as a root and a^2 - a - 1 = 0 as a factor, so that a=(1 + sqrt(5))/2 (the negative roots are clearly inapplicable). The ratios of the areas or RST and ABC can be computed in any coordinate system, for example as half the area of the corresponding parallelogram, which may be computed with determinants. The triangle RST corresponds to the identity matrix (det=1) and the triangle AB corresponds (using the vectors AB and AC) to the matrix with rows [b+a, 1-b], [a, c] and determinant (b+a)c-(1-b)a = (b+a)a^2 - (1-b)a = (2a+1)a^2 + a^2 = 2a^2(a+1) = 7 + 3 sqrt(5). So the areas are in this ratio, making the area of RST equal to 1/(7 + 3 sqrt(5)) = (7 - 3 sqrt(5))/4. Remarks: I really fought the use of algebra, but it seems inevitable in view of the answer. Too bad -- I thought I saw shades of Morley in the problem. It also looked like one could use that trick of adding- and-subtracting areas which is used e.g. to compute areas of spherical triangles by intersecting hemispheres. But no. Note to students: this use of coordinates is _not_ the same as assuming STR is a _right triangle_. Interestingly, however, the assertion that the area of STR _could_ be computed without knowing angles implies that any choice of angles would give the same answer, so that we could freely assume the angles were indeed right angles! The triangle RST ends up about 1/14 the size of ABC. I'd have guessed it was a bit larger (and sort of expected "1/9" as the answer). A5. Note that 2001 = 3.23.29 and 2002=2.7.11.13 . Working mod 3, we find that neither a nor a+1 can be a multiple of 3, so a = 1 mod 3, whence 1^(n+1) - (-1)^n = 0 mod 3, which requires n to be even. Read modulo a, the equation yields -1 = 2001, so that a | 2002; read modulo a+1, it yields (-1)^(n+1) = 2001, which (since n is even) implies a+1 must also divide 2002. We can easily list the divisors of 2002 (only half of which are candidates: a=1 mod 3 requires either both or neither of 2 and 11 to divide a) and find that only if a=1 or a=13 can the equation be satisfied. (Of course a=1 won't work.) Finally checking the equation 13^(n+1) - 14^n = 2001 mod 8, we have 5.5^n - (-2)^n = 1, which (since n is even) means 5 - 4^(n/2) = 1 mod 8. Only if n=2 is this possible. So there is only one candidate solution, and lo and behold 13^3 - 14^2 = 2197 - 196 = 2001. Remarks: Naturally this suggests the more general situation: what are the solutions of a^(n+1) - (a+1)^n = C for other C ? It is easy to check that the left side is negative for large n (the cut-off is about n = a log(a) ) but of course one must use integrality constraints to bound a. As noted above, a must divide C+1, which implies there are at most finitely many solutions. I have not yet checked to see how large the solution sets can get as C varies. A6. I don't really have an answer to this one. (Presumably the answer is 'no'; I suppose they're going to insist on proof...) We may use coordinates and assume the parabola is the solution set of y = a x^2 for some a>0, and then consider endpoints which are a distance of 4 apart (measured along arclength), and for each such pair, check to see whether the whole arc lies in a circle. But surely this is not required for the problem. The arclength integral involves rather complicated logarithm terms. There has to be a way which involves geometry or calculations with less to sort out. (A flexible upper bound on parabolic arc length would be helpful.) NB -- if forced to proceed as I have begun, I would probably parameterize the parabola with x = (t^2-1)/(4at) ; that points to the origin when t=1, and traces out the rest of the curve with positive t's. The virtue is that the arclength from the origin is ( t^2 - 1/t^2 + 4 ln(t) )/(16a), which is not too intractible. It's particularly helpful to parameterize _pairs_ of points on the curve not by pairs of values t1, t2 but rather by a starting parameter t and a _ratio_ of parameters r = t2/t1 > 1. That way, the arclength formula involves no log(t) term; for fixed values of r we can compute the value of t for which the points with parameters t and rt are separated by 4 units of arc. There's a quadratic equation in t^2 to solve. This is not for the faint of heart. I don't claim to have a complete solution by this means. [Note added after posting: see the lower portion of this file for numerous approaches to solving A6 -- arguably the most popular question on this test! --djr] B1. Let a_kl be the color of the square in row k and column l, a_kl = +1 if red and =-1 if black. We are given that forall k, sum_l a_kl = 0 forall l, sum_k a_kl = 0 Thus the excess of the red total over the black total is sum_{k,l} a_kl ( (k-1)n + l ) =sum_k (k-1)n sum_l a_kl + sum_l l sum_k a_kl = 0 + 0 = 0. Remark: I blanked on this one! I was thinking about the effect under permutations of rows and columns, yadda yadda... Not till someone else mentioned summing parts along rows and columns did the light dawn. B2. Add and multiply by x to get 2 = ( (y+x)^5 + (y-x)^5 )/2. Subtract and multiply by y to get 1 = ( (y+x)^5 - (y-x)^5 )/2. Add and subtract to discover (x+y) = 3^(1/5), (x-y) = 1. Add and subtract to get (x,y) = ( (1+3^(1/5))/2, (3^(1/5)-1)/2 ). Remark: There are fruitful ways to approach this even had the formulas been not _quite_ so special. The two sides separately are homogeneous, so one could set y = k x, and play with the equations a bit to get a (quintic) polynomial in k which must be satisfied, and then a power of x must equal some rational expression in k. This approach would almost be _useful_, as opposed to the above, which is merely _clever_. [Typo has been corrected in the final answer for clarity --djr] B3. Note that = k iff k^2 - k + 1 <= n <= k^2 + k. So it's sum_k sum_{n as above} (2^k + 2^{-k}) (1 / 2^n ) =sum_k (2^k + 2^{-k}) (1/2^(least n -1) - 1/2^(greatest n) ) [geom.series] =sum_k (2^k + 2^{-k}) (2^k - 2^{-k})/2^(k^2) =sum_k (2^(2k) - 2^(-2k))/2^(k^2) =sum_k 2 (1/2^(k^2-2k+1) - 1/2^(k^2+2k+1)) Now the sum over the odd values of k telescopes to 2. ( 1/2^((1-1)^2) ) and the sum over the even values of k telescopes to 2. ( 1/2^((2-1)^2) ). My answer is 3 . B4: The statement is true. If x = c/d in lowest terms, then f(x) = (d^2-c^2)/(cd) will also be in lowest terms, so that in particular the denominator of f(x) is larger than the denominator of x unless c = 1, and the numerator of f(x) is never 1. Thus given y = a/b in S, it is clear that y is not in f^(n) (S) for n > b+1, say. Remark: writing x = cot(\pi x') and likewise for y, we see that f is simply the doubling map on R/Z. This makes it easy to find the _real_ points in the intersection, though of course there is no useful cognate in R/Z to the set of rational x. B5: I'm stumped. Note that it is probably important to use the fact that a and b have been bounded; the hypothesis implies that g^2 is a _convex_ linear combination of g, identity, and 0 (I wonder if the stronger hypothesis that a, b < 1/2 is really necessary?) Of course we will also need continuity; e.g. g(x) = 1/x otherwise meets the hypotheses but not the conclusion. It's a good warmup, in general, to try at least to prove some consequences of what you really want to prove. I can prove, for example, that the iterates g^(n)(x) converge to 0 for any x; thus g(0)=0. Also one can check that g is one-to-one; thus it is either always increasing or always decreasing. I didn't see how to prove it's onto; that too would be a consequence of g(x) = c x (with c <> 0 ). B6: I didn't get anywhere on this. Here's a response sent to me today from Paul Pollack : B6 appears to be taken from Carl Pomerance's paper _The Prime Number Graph_. MathSciNet links to an online version of the article. Here is the argument: Consider the convex hull of {(a_n,n) | n>=1}. As a_n/n -> 0, n/a_n -> oo, and this implies the non-vertical portion of the convex hull is polygonal with infinitely many vertices. Each such vertex is of the form (a_k,k) -- but then if 1 <= i <= k-1,the midpoint ((a_{k-i}+a_{k+i})/2,k) of the segment connecting (a_{k-i},k-i) and (a_{k+i},k+i) lies to the left of (a_k,k), so that a_{k-i} + a_{k+i} < 2*a_k, as was to be shown. ============================================================================== From: "Paul Pollack" To: "Dave Rusin" Subject: Re: William Lowell Putnam 2001 Date: Sun, 2 Dec 2001 01:58:01 -0800 > For the past decade or so people have posted questions and solutions > starting around, oh, 5pm Fiji time on Saturday, i.e. when the day > is done. I was planning to post the questions soon but will wait a day > I guess. (I'm still short a few good answers. A6 anyone? B5? B6?) B6 appears to be taken from Carl Pomerance's paper _The Prime Number Graph_. MathSciNet links to an online version of the article. Here is the argument: Consider the convex hull of {(a_n,n) | n>=1}. As a_n/n -> 0, n/a_n -> oo, and this implies the non-vertical portion of the convex hull is polygonal with infinitely many vertices. Each such vertex is of the form (a_k,k) -- but then if 1 <= i <= k-1,the midpoint ((a_{k-i}+a_{k+i})/2,k) of the segment connecting (a_{k-i},k-i) and (a_{k+i},k+i) lies to the left of (a_k,k), so that a_{k-i} + a_{k+i} < 2*a_k, as was to be shown. HTH, Paul ============================================================================== From: "Robin Chapman" Newsgroups: sci.math Subject: Re: William Lowell Putnam 2001 Date: Mon, 3 Dec 2001 16:15:36 +0000 (UTC) "Dave Rusin" wrote in message news:9uelrf$8no$1@news.math.niu.edu... > > B5: I'm stumped. Note that it is probably important to use the fact that > a and b have been bounded; the hypothesis implies that g^2 is a > _convex_ linear combination of g, identity, and 0 (I wonder if the > stronger hypothesis that a, b < 1/2 is really necessary?) Of course > we will also need continuity; e.g. g(x) = 1/x otherwise meets the > hypotheses but not the conclusion. > > It's a good warmup, in general, to try at least to prove some > consequences of what you really want to prove. I can prove, for example, > that the iterates g^(n)(x) converge to 0 for any x; thus g(0)=0. > Also one can check that g is one-to-one; thus it is either always > increasing or always decreasing. I didn't see how to prove it's onto; > that too would be a consequence of g(x) = c x (with c <> 0 ). Let r and s be the roots of t^2 - at - b = 0. We'll show that either g(x) = rx for all x or g(x) = s(x) for all x. Let r be the larger root, then 1 > r > 0 > s and |s| < r. As bx = g(g(x)) - a g(x) then g is injective. So g is strictly increasing or strictly decreasing. Its range is an open interval. It cannot be bounded above, as if g(x) -> x as x -> infinity then g(g(x)) -> infinity and to g(g(k)). Similarly g's range is unbounded below and so g is bijective: g^{-1}(x) = (g(x) - ax)/b. We can write x = p(x) + q(x) and g(x) = p(x)r + q(x)s. Here p(x) = (g(x) - sx)/(r-s) and q(x) = (g(x) - rx)(s-r). By induction, g^n(x) = p(x)r^n + q(x)s^n for all integers n (positive, zero and negative). As n -> infinity, g^n(x) -> 0 for any x, and we conclude that g(0) = 0. Then if g is increasing it is sign-preserving, and if g is decreasing, it is sign-reversing. Suppose f is increasing and q(x) is non-zero for some x. The sequence g^{-n}(x) = p(x)r^{-n} + q(x)s^{-n} reverses sign for n large enough. This gives a contradiction: so g(x) = rx for all x. Suppose f is decreasing and p(x) is non-zero for some x. The sequence g^n(x) = p(x)r^n + q(x)s^n has constant sign for n large enough. This gives a contradiction: so g(x) = sx for all x. Robin Chapman ============================================================================== From: ayatollah potassium Newsgroups: sci.math Subject: Re: William Lowell Putnam 2001 Date: Tue, 04 Dec 2001 15:07:00 -0500 Dave Rusin wrote: > A1. Consider a set S and a binary operation * on S (that is, for > each a, b in S, a*b is in S). Assume that (a*b)*a = b for all > a, b in S. Prove that a*(b*a) =b for all a, b in S. The identity says that the set of (x,y,z) with z = x*y, has cyclic symmetry, or equivalently, that the map (x,y)->(y,x*y) has order 3. Examples can be generated by taking S a group, and triples with xyz=1, i.e. x*y = (xy)^-1. Are these all? A1 and B5 are recycled from recent putnams, by the way. > A3. For each integer m, consider the polynomial > P_m(x) = x^4 - (2m+4) x^2 + (m-2)^2 > For what values of m is P_m(x) the product of two nonconstant > polynomials with integer coefficients? >From the quadratic formula, x^2 = m+2 +- sqrt (8m). If m is twice a square, this factors. If not, certainly there is no rational root, for its square would equal {rational number +- sqrt(8m)}. In that case a quadratic factor must have the sum of squares of its roots rational, so to force cancellation of the sqrt(8m) terms, one root must be a sqrt of m+2 + sqrt(8m) and the other a sqrt of m+2 - sqrt(8m), so that the roots of one quadratic factor are negatives of the roots of the other. So the factorization would be (x^2 + px + q) (x^2 - px + q) = x^4 + (2q-p^2)x^2 + q^2, where q^2 = (m-2)^2 and 2q - p^2 = -2m-4, i.e. p = sqrt (2m+4 +- 2(m-2)) = sqrt (8) or sqrt(4m). Conclusion: m is a square or twice a square, and this is true for rational, not only integer, values of m. > A4. Triangle ABC has area 1. Points E,F,G lie, respectively, on > sides BC, CA, AB such that AE bisects BF at point R, > BF bisects CG at point S, and CG bisects AE at point T. > Find the area of triangle RST. > [Illustration deleted.] Barycentric coordinates (a,b,c) with a+b+c=1, are very well suited to this. Lines through A are specified by fixing the ratio b/c. Midpoints of these lines have a=1/2. area RST / area ABC = 3x3 determinant of coordinates of R,S,T (because it is the volume ratio of tetrahedron 0ABC to its sub-tetrahedron 0RST, looking at a+b+c=1 as plane in 3-space). ============================================================================== The remainder of this document consists of several approaches for proving A6. All require finding a lower bound on arc length, which can be accomplished in several ways: (1) Approximate the arc length with a polygonal approximation (i.e. approximate the integral with a Riemann sum) (2) Describe arc length exactly as an integral, and then approximate the integrand (3) Compute that integral exactly and then approximate the antiderivative (4) Compute the integral exactly and evaluate it at the extreme case, then check that the integral decreases to that value from nearby higher values. --djr ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: William Lowell Putnam 2001 Date: 3 Dec 2001 02:55:51 GMT In article <9uelrf$8no$1@news.math.niu.edu>, Dave Rusin wrote: >A6. I don't really have an answer to this one. (Presumably the answer >is 'no'; I suppose they're going to insist on proof...) I see now that Dan Bernstein does, and that the answer is 'yes'! I am very surprised. Well, it looks like one indeed had to do this: >We may use >coordinates and assume the parabola is the solution set of y = a x^2 >for some a>0, and then consider endpoints which are a distance of 4 >apart (measured along arclength), and for each such pair, check to see >whether the whole arc lies in a circle. >NB -- if forced to proceed as I have begun, I would probably parameterize >the parabola with x = (t^2-1)/(4at) ; that points to the origin when t=1, >and traces out the rest of the curve with positive t's. The virtue is >that the arclength from the origin is ( t^2 - 1/t^2 + 4 ln(t) )/(16a), >which is not too intractible. >This is not for the faint of heart. This still seems like a lot to do during a Putnam exam, but maybe it's for the best. Following Dan's lead, I can find good solutions easily enough. An arc symmetric around the vertex fits the bill if there are points on the (parameterized) curve with x^2 + a^2 x^4 - 2a x^2 <= 0 and ( t^2 - 1/t^2 + 4 ln(t) )/(16a) >= 2 . These describe two closed subsets of the a,t-plane and sure enough they intersect nontrivially. It's not all that hard to turn one of them into an equation and substitute into the other to get something to graph on Maple. So I can report that there are solutions to our original problem as long as a > 34.74. Perhaps better, I can insist that the endpoints of the arc lie on the circle and try to maximize the length of the arc; that happens when a = 94.09 or so; the arc length is 4.002670... (More precisely, the maximum length occurs with (a,t) = ( ( u+1/u + 14)/32, sqrt(u) ) where ln(u) = 8(u+1)/(u-1). ) Let me add that during the exam I began computing the arclength integrals for the curve y = a x^2 using the techniques I know I have taught a hundred times. After a minute one comes to the integral of sec^3(x), which is always the "starred problem" in the calc-1 text. Unfortunately, I've never committed that one to memory... Now I have a good motivational story the next time I teach that topic. (I still prefer rational parameterizations over the other alternatives. Chacun a son gout.) I will be very surprised to see a lot of high scores on this one. (4.00267 is awfully close to 4 !) Good work, Dan. dave ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Putnam A6 (Was: Re: William Lowell Putnam 2001) Date: 3 Dec 2001 07:12:22 GMT I know, I'm know, I'm having a conversation with myself here, but... In article <9uepjn$9vm$1@news.math.niu.edu>, Dave Rusin wrote: > Well, it looks like one indeed had to do this: [...] >>This is not for the faint of heart. Once you decide to try to prove that A6 has a _positive_ solution, it's clear where to look for a long arc. Even better, when proving inequalities in _this_ direction, it is no longer really necessary to compute the arclength exactly -- we only need a lower bound, and that clearly comes from a polygonal approximation to the curve. It's only a question of finding enough points, in appropriate locations (we know they _exist_ once we compute the integrals). With that in mind, I present an "elementary" solution to problem A6. Simply note that the parabola y = 265 x^2 meets the circle x^2 + (y-1)^2 = 1 at P0=(0,0) and P3=(23/265, 529/265), but also includes the points P1=(1/300, 265/300^2) and P2=(1/50, 265/50^2). The length of the parabolic arc from P0 to P3 must certainly exceed the sum of the distances P0-P1, P1-P2, and P2-P3. These are, respectively, .004447568347, .1043945655, and 1.891406125, which sum to 2.000248259. By symmetry, then, the arc from (-23/265, 529/265) to P3 has length 4.000496518 > 4 . (I believe it's true that by taking only one intermediate point on the right half-arc one cannot show its length exceeds 2. I chose the points above to approximate the maximum sum of a three-segment approximation to the arc length.) You might object that one cannot be expected to work out delicate decimals during the Putnam exam. Very well; you may stick to simple integer arithmetic. Set p= 706130233 and q = 118098 and consider the parabola y = (p/q) x^2. It meets the same circle precisely at the origin and the points (+- 12913992/p, 1412142368/p), and hence the arc between these two is completely contained in the circle. But the right half also passes through points P1=(157464/p, 209952/p) and P2=(1434672/p, 17428608/p), and the distances among these points are exactly P0-P1 = 262440/p, P1-P2 = 17265960/p, P2-P3 = 1394761000/p and these sum to precisely 1412289400/p = 2 + 28934/p > 2 . Now, isn't that better? :-) dave ============================================================================== [ My analysis was a little convoluted, but it's not all that hard to find points like these -- better ones, really -- with simple hand computations. We are looking for points which are on a parabola and within a circle, for which the polygonal distance exceeds twice the radius. This particular phrasing is scale-independent, so we may scale as necessary to assume the parabola is simply y = x^2. So we seek points x1, x2, x3 so that (1) 0 = x0 < x1 < x2 < x3 (2) d_i = dist(P_i, P_{i-1}) is rational (3) d1 + d2 + d3 > 2r, the radius of the disk. It is easily checked that the circle is x^2 + y^2 = 2r y so we may compute 2r = (x3^2 + y3^2)/y3 = 1 + x3^2. Also note that d_i^2 = (x_i - x_{i-1})^2 + (x_i^2 - x_{i-1}^2)^2 = (x_i - x_{i-1})^2 ( 1 + (x_i + x_{i+1})^2 ). So we may rewrite our conditions as: (1) 0 = x0 < x1 < x2 < x3 (2) D_i^2 = 1 + (x_i + x_{i+1})^2 for a rational D_i (3) x1 D1 + (x2-x1) D2 + (x3-x2) D3 > (1 + x3^2) Clearing a common denominator Q, say, we seek _integers_ X_i, E_i, and Q with (1) 0 = X0 < X1 < X2 < X3 (2) E_i^2 = Q^2 + (X_i + X_{i+1})^2 (3) X1 E1 + (X2-X1) E2 + (X3-X2) E3 > (Q^2 + X3^2) This requires Q to be a leg of several different Pythagorean triples. The smallest value of Q which works appears to be Q=45, and there are several sets of three right triangles which will meet all the conditions. Perhaps the nicest uses the triples [45, 28, 53], [45, 200, 205], and [45, 1012, 1013], for which X1=28, X2=172, X3=840. Scaling back, we have solutions x1=28/45, x2=172/45, x3=56/3; d1=53/45, d2=41/9, d3=1013/45. The radius of the circle through P3 is 3145/18, which leaves the arithmetic simple enough. The points are then P0 = [ 0, 0], P1 = [ 56/15725, 1568/707625], P2 = [344/15725, 59168/707625], P3 = [336/ 3145, 6272/ 3145] and the distances between pairs are 2968/707625, 1312/15725, and 1353368/707625, which sum to 2 + 14/78625 > 2. As a bonus, this set of points fairly closely matches the optimal arrangement mentioned above! We're on the parabola y = a x^2 with a=3145/18= 174.72... and are looking at points with x coordinates roughly .0035612, .021876, .1068362 . The length of our whole polygonal curve would be about 4.00035612 This is all just barely possible during a Putnam exam. --dave] ============================================================================== From: baloglou@panix.com Date: Mon, 3 Dec 2001 12:00:31 -0500 (EST) To: rusin@vesuvius.math.niu.edu Newsgroups: sci.math Subject: Re: Putnam A6 (Was: Re: William Lowell Putnam 2001) [reply address is baloglouAToswego.edu] In article <9uf8km$bm$1@news.math.niu.edu>, Dave Rusin wrote: > >Once you decide to try to prove that A6 has a _positive_ solution, >it's clear where to look for a long arc. Even better, when proving >inequalities in _this_ direction, it is no longer really necessary to >compute the arclength exactly -- we only need a lower bound, and that >clearly comes from a polygonal approximation to the curve. It's only a >question of finding enough points, in appropriate locations (we know >they _exist_ once we compute the integrals). > >With that in mind, I present an "elementary" solution to problem A6. ^^^^^^^^^^^^^^^^^ With that not in mind -- I had tried it with just two points, one on the x-axis and one on the circle, only to show that it cannot work -- I would like to propose the following elementary approach. Consider a parabola with vertex at (0, -1) that intersects the x-axis at (b, 0), (-b, 0). It is easy to show that it intersects the unit circle at ((2*(b^2)-b^4)^.5, 1-b^2), (-(2*(b^2)-b^4)^.5, 1-b^2). So it suffices to prove that the parabolic arc length from x = 0 to x = (2*(b^2)-b^4)^.5 does exceed 2 for certain (small) values of b. Direct computation/integration shows the arc length A(b) to be equal to (4-3.5*(b^2)+.75*(b^4))^.5 + .25*(b^2)*ln[((8/(b^2))-4)^.5+((8/(b^2))-3)^.5] It is easy to see that the limit of A(b) as b approaches 0 is 2. To show that it actually achieves values greater than 2, it suffices to show that the limit of the derivative A'(b) as b approaches 0 is positive. But A'(b) consists of several terms that all approach 0 as b approaches 0, including .5*b*ln[((8/(b^2))-4)^.5+((8/(b^2))-3)^.5]. It seems that all this is bound to fail, except that ... now I am going to look at the second derivative A"(b) and show it to be positive near 0, in fact approaching +oo as b approaches 0. The key is certainly the 'middle' term at the end of the previous paragraph, the derivative of which equals .5*ln[((8/(b^2))-4)^.5+((8/(b^2))-3)^.5] - 4/(((8-4*(b^2))*(8-3*(b^2)))^.5) Now as b approaches 0 the first term above approaches +oo, while the second term approaches -.5; likewise, all other terms of A"(b) approach *finite* negative values as b approaches 0, so A"(b) ---> +oo as b ---> 0 appears to hold (if all my calculations are right, and probably even if they aren't!). So with A(b) ---> 2, A'(b) ---> 0 and A"(b) ---> +oo, we conclude that A(b) must exceed 2 in an interval to the right of b = 0. How does this sound? G. B. ============================================================================== From: "Ignacio Larrosa Cañestro" Newsgroups: sci.math Subject: Re: Putnam A6 (Was: Re: William Lowell Putnam 2001) Date: Mon, 3 Dec 2001 13:08:02 +0100 I think it is intuitivally clear thah a closed parabola tangent to the circle at its vertix have a arc with length > 4 inside the circle, because at the vertix they have the same tangent, while in the diametral opposite side they are near ortogonals. Let work in that sense. Consider the parabola y=kx^2 and the circle x^2 + (y^-1)^2=1. x^2 + (k·x^2 - 1)^2 - 1 = 0 k^2·x^4 + x^2·(1 - 2·k) = 0 They intersect at x=0 (double) and at x= +/- sqrt(2k - 1)/k, for k > 1/2. Consider only the right side of the parabola. The arc length from x=0 to x=sqrt(2k - 1)/k is s(k)=INT(sqrt(1 + 4k^2*x^2), x, 0, sqrt(2k - 1)/k) ==> s(k)= LN(sqrt(8k - 3) + 2sqrt(2k - 1))/(4k) + sqrt(2k - 1)sqrt(8k - 3)/(2k) It is easy to see that Lim(s(k), k, inf) = 2, as we could hope. In the Putnam exam is it allowed scientific calculator? If yes, one can guess k=10, 100, 1000, ... For k=100, s(k)=2.00133..., and the answer is YES. Alternativally, it can be proved that s(k) is decreasing for k sufficiently large: s'(k)=(2(8k - 3) - sqrt(2k - 1)sqrt(8k - 3)Ln(sqrt(8k - 3) + 2sqrt(2k - 1)))/(4k^2sqrt(2k - 1)sqrt(8k - 3)) The denominator is positive, and the numerator go to -inf when k go to inf: Lim((2(8k - 3) - sqrt(2k - 1)sqrt(8k - 3)Ln(sqrt(8k - 3) + 2sqrt(2k - 1))), k, inf) = -inf Then s'(k) < 0 for k enough large and, as Lim(s(k), k, inf)=2, s(k)>2 for that k. -- Saludos, Ignacio Larrosa Cañestro A Coruña (España) ignacio.larrosa@eresmas.net ICQ 94732648 ============================================================================== From: "Robin Chapman" Newsgroups: sci.math Subject: Re: Putnam A6 (Was: Re: William Lowell Putnam 2001) Date: Tue, 4 Dec 2001 08:44:44 +0000 (UTC) "Ignacio Larrosa Cañestro" wrote in message news:9ufq7p$3r1$1@diana.bcn.ttd.net... > s(k)= LN(sqrt(8k - 3) + 2sqrt(2k - 1))/(4k) + sqrt(2k - 1)sqrt(8k - 3)/(2k) > > It is easy to see that Lim(s(k), k, inf) = 2, as we could hope. > So s(k) = A(k)/k + 4 + O(1/k) where A(k) = log(sqrt(8k - 3) + 2sqrt(2k - 1))/4 -> infinity as k -> infinity. Hence s(k) > 4 for k large enough. Robin Chapman ============================================================================== From: "Ignacio Larrosa Cañestro" Newsgroups: sci.math Subject: Re: Putnam A6 (Was: Re: William Lowell Putnam 2001) Date: Tue, 4 Dec 2001 10:40:37 +0100 "Robin Chapman" escribió en el mensaje news:9cc144d025bb9ac563685acf044f38ea.22128@mygate.mailgate.org... > "Ignacio Larrosa Cañestro" wrote in message > news:9ui2sa$ejg$1@diana.bcn.ttd.net... > > > Two little typos .. Well, now I understand what you said. I confussed 4's and k's. The only typo was 's(k) > 4', actually 's(k) > 2'. ============================================================================== From: "Robin Chapman" Newsgroups: sci.math Subject: Re: Putnam A6 (Was: Re: William Lowell Putnam 2001) Date: Tue, 4 Dec 2001 13:59:09 +0000 (UTC) > > > > It is easy to see that Lim(s(k), k, inf) = 2, as we could hope. > > > > > > > > > > > So s(k) = A(k)/k + 2 + O(1/k) > > > > > where A(k) = log(sqrt(8k - 3) + 2sqrt(2k - 1))/4 -> infinity as > > k -> infinity. Hence s(k) > 2 for k large enough. > > > > Humm. It isn`t than easy. Actually, Yes it is. > sqrt(2k - 1)sqrt(8k - 3)/(2k) = 2 - O(1/k) Yes. The fact is that k(s(k)-2) -> infinity (very slowly!) as k -> infinity, so s(k) > 2 eventually. Robin Chapman ============================================================================== Date: Wed, 05 Dec 2001 09:26:44 -0500 From: Frank Morgan Subject: Putnam parabola To: Dave Rusin Dear Dave and Friends, Appreciate very much your prompt postings on Putnam. Here's my proposed solution to A6 (hope it's right): Lemma. Sqrt(1+a) >= 1 + 4ca when a =< .25 for some c > 0 (namely 4c = 2sqrt5 - 4). Solution. Consider half of parabola on its side, y = e sqrt x, e small. Then length L satisfies L >= Integral from e^2 to 1 + sqrt(1-e^2) of sqrt(1 + .25 e^2/x) >= Integral from e^2 to 1 + sqrt(1-e^2) of 1 + c e^2/x = 1 + sqrt(1-e^2) - e^2 + c e^2 ln((1+sqrt(1-e^2))/e^2) >= 2 - 2 e^2 + c e^2 ln(1/e^2), which is greater than 2 for e small. Frank Morgan Professor Frank Morgan 2nd Vice-President, MAA Dept of Math and Stats, Williams College Williamstown, MA 01267 (413) 597-2437 Frank.Morgan@williams.edu http://www.williams.edu/Mathematics/fmorgan ============================================================================== From: "Brian R. Hunt" Date: Thu, 6 Dec 2001 14:41:26 -0500 (EST) To: rusin@vesuvius.math.niu.edu Subject: Re: Putnam A6 (Was: Re: William Lowell Putnam 2001) Hello Dave, here is a moderately elegant paper-and-pencil solution to A6 for what it's worth. By the end of the A set I had only managed to convince myself that the answer is yes, worked this out during the B set... ------ Let the polynomial be bx = y^2 where b > 0 will be (very) small. Consider the upper branch of the parabola, which intersects the circle (x-1)^2 + y^2 = 1 at x = 0 and x = 2 - b. Its arclength is \int_0^{2-b} \sqrt{1 + b/(4x)} dx. Since 0 < b/(4x) <= 1/4 for x >= b and \sqrt{1 + z} > 1 + 2z/5 for 0 < z <= 1/4 [check endpoints and use concavity], the arclength of the upper branch exceeds \int_b^{2-b} (1 + b/(10x)) dx = 2 - 2b + (b/10)log((2-b)/b). For b sufficiently small this exceeds 2, and total arclength exceeds 4. ------ Enjoying your solutions and web site as always! Best wishes, Brian Hunt P.S. The rule for students observing the Sabbath is roughly that they must be supervised by a professor or clergyman who vouches that they did not have any communication with the outside world during the day, and that they take the competition immediately after sundown Saturday evening; I have given the competition to a few students this way. So I see no harm in posting once the regular competition is over. ============================================================================== From: baloglou@panix.com (George Baloglou) Newsgroups: sci.math Subject: Re: 2001 Putnam: A6 wins the contest over B5 Date: 10 Nov 2002 12:30:09 -0500 In article , Vaughan Pratt wrote: >In article <0aJy9.18698$U93.1430390@news2.telusplanet.net>, >Larry Hammick wrote: >>A6 >>Can an arc of a parabola inside a circle of radius 1 have >>a length greater than 4? >>======== >>Does the Monthly give a purely computational solution of A6? >No it doesn't, which is too bad since there exists a completely >rigorous computational solution that is shorter than the published >solution while using only simple algebraic manipulation (no symbolic >integration). The trick is to note that the numerical method of >approximating arc length by summing a series of chords yields a >rigorous *lower* bound, which is all that A6 needs. The nice thing in >this case is that the chords don't have to be at all short, three >chords (for one half of the parabola) suffice (but not two). Fringe >benefits: the two intermediate points can be lattice points (assuming >the same scaling as in the published solution), and none of the >arithmetic requires more than two decimal places of precision. You >still need a to be large enough. The problem with the lower bound approaches is the implicit assumption that such an arc does exist: indeed the scarcity of solvers suggests that most contestants who attempted the problem opted for an upper bound (and a negative answer). On the other hand, a brutally computational approach such as the one I posted here about a year ago arrives at the answer rather naturally, I think. [My solution, archieved by Dave Rusin among several others, relies on a study of the arc length function of the most obvious family of aspiring parabolas by way of its first *and* second derivatives -- a 'graphing' problem that I should have been able to clear in about 20 minutes ... were I at the age of the contestants!] Still, the Monthly's solution is very clean and much shorter than the one published in the Mathematics Magazine (February 2002 issue), for example. And there is nothing wrong with trying for *both* upper and lower bounds and see which one works instead of actually evaluating the integral ... except that, once again, circumstantial evidence suggests that most contestants did not think too highly of those parabolic arcs :-) ] baloglouAToswego.edu ============================================================================== From: pratt@boole.Stanford.EDU (Vaughan Pratt) Newsgroups: sci.math Subject: Re: 2001 Putnam: A6 wins the contest over B5 Date: Thu, 14 Nov 2002 23:29:52 +0000 (UTC) In article , George Baloglou wrote: (apropos of my three-chord solution to problem A6 of last year's Putnam) >The problem with the lower bound approaches is the implicit assumption >that such an arc does exist: indeed the scarcity of solvers suggests that >most contestants who attempted the problem opted for an upper bound (and a >negative answer). How is this a problem? I wasn't offering an approach, I was offering a solution. As far as the approach is concerned, the natural starting point is the immediate observation that the respective limits for thick and thin parabolas are 2 and 4. A proof that that the passage from thick to thin is monotonic would immediately give a negative answer. Ok, so one can imagine all but one of the contestants trying and (necessarily) eventually failing to find this proof (or worse, thinking they'd found it and moving on). But that seems very wrong. If one runs into difficulty finding a proof, one should start considering the possibility that maybe it's not monotonic after all. In the following *working* (not final answer), we'll keep an open mind about the outcome right up until the very end. If it's not monotonic and the arc length turns around and starts to shrink somewhere before the limit, it will have to approach the limit of 4 from above, unless it turns around a second time (or even number of times) and starts to grow again. Multiple turning points seem unlikely (maybe two but one should definitely be considered first). Approaching 4 from above starts to look somewhat plausible when you consider that a very thin parabola consists of a short essentially sideways swing followed by a long essentially vertical run to just a hair short of the top of the circle. This suggests exploring the proposition, what you win on the swing you lose on the run (sorry). Using the trick of making the parabola thin by holding it fixed at y = x^2 and instead growing the diameter D of the circle, and noting that the two curves intersect at altitude D - 1, what you lose on the run is therefore at most 1. Let's look more closely at what it actually is, and then see whether you can win it back on the swing. The curvature of most of a thin parabola is way too small to make any difference (unless everything else turns out to balance exactly, so let's not worry about that unless it actually happens). So take (p,p^2) as the point where we can fruitfully start approximating the parabola by a straight line and (q,q^2) the point where the parabola meets the circle (q^2 = D-1). Since the parabola's shape at the bottom isn't changing, p may as well be independent of diameter D. The length of the straight line between these two points is sqrt((q^2-p^2)^2 + (q-p)^2) = (q^2 - p^2) sqrt( 1 + ((q-p)/(q^2-p^2))^2 ) = (q^2 - p^2) sqrt( 1 + 1/(q+p)^2 ) = q^2 - p^2 + 1/2 + O(1/q^2) = D - 1 - p^2 + 1/2 + O(1/q^2) = D - (p^2 + 1/2) + O(1/q^2) Neglect O(1/q^2) for now, with the same caveat as when we neglected the curvature above: come back to it later only if the outcome is within 1/q^2 ~ 1/D of 4. So we want to know how the arc length of the parabola from (0,0) to (p,p^2) (the swing) compares with p^2 + 1/2. We need to start exploring p large enough to get us onto the "straight" bit of the parabola. p = 1 might be a bit small for this but let's try it anyway. For this we need the arc length to be p^2 + 1/2 = 1.5. Ooh, very close already! The arc length is bounded below by the line >from (0,0) to (1,1), of length > 1.41, a shortfall of .09, and above by the circle arc from (0,0) to (1,1), of length 1.57, an excess of .07. Could go either way here. We could try to calculate the parabola arc length more exactly but it's much easier just to crank p up a little. So look at p = 2. This ups the ante to p^2 + 1/2 = 4.5, an increase of 3 over the target of 1.5 we had with p = 1. Hence the arc length from (1,1) to (2,4) had better exceed 3 if we're to make any progress this way. But look, even the line segment from (1,1) to (2,4), sqrt(10) > 3.16, is longer than 3, in fact by .16 which is more than the shortfall of .09 we had with the straight line from (0,0) to (1,1). So we have chord lengths exceeding 1.41 + 3.16 + D - 4.5 = D + 0.07 and the answer is a clear positive. End of working. For the final answer write down the 6 lines of algebra above to arrive at a chord length of D - 4.5 + O(1/D) for the third chord and then show that the distances (0,0) to (1,1) to (2,4) exceed 4.5. Note that this was not a lower bound approach until the very end, before that it was an approximation approach where we temporarily set ostensibly neglible terms aside. >On the other hand, a brutally computational approach >such as the one I posted here about a year ago arrives at the answer >rather naturally, I think. You seem to be claiming that approximating the arc length of the whole parabola with the one uniform technique is more natural than breaking the parabola up into structurally distinct components and approximating each of their lengths with the most appropriate technique for that component. Would that also apply to proving that the length of the closed curve x^100 + y^100 = 1 lies in (7,8)? >[My solution, archieved by Dave Rusin among several others, relies on a >study of the arc length function of the most obvious family of aspiring >parabolas by way of its first *and* second derivatives -- a 'graphing' >problem that I should have been able to clear in about 20 minutes ... >were I at the age of the contestants!] Time better spent on the next problem. Vaughan Pratt ============================================================================== Date: Sat, 16 Nov 2002 15:56:21 -0800 From: Vaughan Pratt To: rusin@vesuvius.math.niu.edu Subject: Last year's A6 Hi, Dave, In your list of solutions to A6 from last year's Putnam (yeah, I know, ancient history), your three-chord lower bound involved some nontrivial numerical work. Turns out if you make your two intermediate points variable you don't need any numerical work (beyond that associated with 1-2 digit integer coefficients). So consider the parabola y = x^2 for y from 0 to d - 1 where d is the diameter of the circle sitting on the origin. Split it in three like you did, calling the points O,P,Q,R in order, so that O = (0,0), P = (p,p^2), Q = (q,q^2), and R = (r,r^2) where r^2 = d - 1. Take 0 << 2p = q << r where f << g means f = o(g), i.e. f(x)/g(x) tends to 0. The lengths of the three chords are then given by |OP| = sqrt(p^4 + p^2) |PQ| = sqrt(9p^4 + p^2) |QR| = sqrt((r^2-q^2)^2 + (r-q)^2) = (r^2 - q^2) sqrt( 1 + ((r-q)/(r^2-q^2))^2 ) = (r^2 - q^2) sqrt( 1 + 1/(r+q)^2 ) = r^2 - q^2 + 1/2 + O(1/r) = d - 1/2 - 4p^2 + O(1/r) |OP| + |PQ| + |QR| is then given by p^2 (sqrt(1 + 1/p^2) + 3 sqrt(1 + 1/(9p^2))) + d - 1/2 - 4p^2 + O(1/r) = p^2 (1 + 1/(2p^2) + 3 + 1/(6p^2) + O(1/p^4) - 4 - 1/(2p^2)) + d + O(1/r) = d + 1/6 + O(1/p^2) + O(1/r) This tends to d + 1/6 as p and r tend to infinity. Vaughan Pratt