Some suggested answers to the 1997 Putnam exam. The first part is the set of solutions as I originally deposited them the evening after the test. At the end I have some posts to the newsgroup sci.math which fill in the holes and correct the calculations in B6. dave rusin@math.niu.edu ------------------------------------------------------------------------------ A1. Let us commit the heresy of introducing coordinates with O at the center, so we have points O: (0,0) H: (-11,0) F: (-11, -5) M:(0,-5). The descriptions of M and O make B and C equidistant from both of them; thus the line of points equidistant from B and C is the vertical axis. Since BC is then horizontal and contains F we have coordinates B: (-x, -5) C: (x, -5). Since FH is in the altitude through A, we also have the point A:(-11,y). The altitude through B passes through H, so its slope is 5/(x-11). THe line AC has slope - (y+5)/(x+11). Since those two are perpendicular, we find x^2-11^2 = 5(y+5) = 5y + 25 On the other hand, A and B are equidistant from O too, so we find y^2+11^2=x^2+5^2, i.e. x^2-11^2 = y^2-25. Comparing these equations shows y^2-5y-50=0, i.e. y=10 (not -5). Then x = 14, so segment BC has length 28. ------------------------------------------------------------------------------ A2. ------------------------------------------------------------------------------ A3. I don;t know. The first factor is x*exp(-x^2/2). The second is a Bessel function or hypergeometric or something, but the key property (I suppose) is that it satisfies a DE xg'' + g' = x g. Thus an integral int x f g can be written int f (x g') ' and we can use integration by parts twice. But I end up with int x^2 f g, which doesn't close the loop quite like I expected. Hmm. ------------------------------------------------------------------------------ A4. This is essentially a group cohomology question, asking us to recognize some 1-cycles. From the equation x e x^(-1) = e x x^(-1) we deduce (after cancellation) that phi(x) phi(e) = phi(e) phi(x), i.e., whatever E = phi(e) is, it's in the center of G. From the equation x x^(-1) e = e e e we deduce (after cancellation) that phi(x) phi(x^(-1)) = E^2, so phi(x^(-1)) = phi(x)^(-1) E^2. From the equation y^(-1) x^(-1) (xy) = e e e we deduce phi(y^(-1)) phi(x^(-1)) phi(xy) = E^3; from the previous two paragraphs we see this becomes phi(y)^(-1) phi(x)^(-1) phi(xy) = E^(-1). If we set psi(x) = E^(-1) phi(x), then this implies psi(xy) = E^(-1) phi(xy) = E^(-2) phi(x) phi(y) = psi(x) psi(y) so psi is indeed a homomorphism. ------------------------------------------------------------------------------ A5. The symmetric group S_10 acts on the n-tuples in the obvious way, and so breaks the collection of them into orbits; each orbit is of cardinality [S_10 : G] where G is the stabilizer of an element in that orbit. This stabilizer is easy to compute: within a given S_10 orbit we may obviously find a unique representative with a_1 <= a_2 <= ... <= a_10. Its stabilizer G is the product of symmetric groups S_(n1) x S_(n2) x ..., where a_1 = a_2 = ... = a_(n1) < a_(n1+1) = ... = a_(n1+n2) < ... Thus the number of elements in that orbit is 10! / (n1! n2! ... ). (Note that n1 + n2 + ... = 10.). To decide whether this is even or odd, we look at the cardinality of the 2-Sylow subgroups, that is, the 2-part of this product of factorials. We computer 2^r || n! as shown in this table: n 1 2 3 4 5 6 7 8 9 10 r 0 1 1 3 3 4 4 7 7 8 Now consider the partitions of 10: 10 = 10 10 = 9 + 1 (or 1 + 9) 10 = 8 + 2 10 = 8 + 1 + 1 etc. Each partition determines a subgroup as above, we can compute the 2-part of its index. For example, the partition 10 = 8 + 2 determines a subgroup of order 2^7 * 2^1 * odd, which is therefore of odd index in S_10. Rather than enumerate all partitions, observe that if any summand n_i is equal to 1, the corresponding stabilizer group has S_1 = {e} as a factor, and so up to isomorphism is a subgroup of S_9, whose index in S_10 is already even. So it suffices to consider partitions with all summands > 1: 10 = 10, 8+2, 7+3, 6+4, 5+5, 6+2+2, 5+3+2, 4+4+2, 4+3+3, 4+2+2+2, 3+3+2+2, and 2+2+2+2+2. We compute the 2-power of the stabilizer from the table above: respectively, 8, 8, 5, 5, 6, 6, 5, 7, 5, 6, 4, 5 Very well, then, all orbits have stabilizers of odd index except those with stabilizer isomorphic to S_10 or S_2 x S_8. Thus, all ordered 10-tuples of solutions to the original equation fall into orbits of even length except those of the form a_1 + ... = a_10 ( = 10, obviously) or of the form a_1 = a_2 <> a_3 + ... + a_10. Call these last two numbers x = a_1 and y = a_10. Then we are to have 2/x + 8/y = 1, or y = 8x/(x-2). Since gcd(x,x-2) = 1 or 2, the integrality of this y forces x-2 to divide 8, if x is odd, and forces x/2 -1 to divide 8 if x is even. This gives solutions x=3, 4, 6, 10, 18 (with y=24, 16, 12, 10, 9 respectively). Note that this includes the case x=y of the previous paragraph. Thus there are evenly many permutations of all solutions except the oddly many permutations of solutions (3, 3, 24, 24, ...), (4, 4, 16, ...), (6, 6, 12, 12, ...), (18, 18, 9, 9, ...), and of course (10,10, ...). N_10 is ODD. ------------------------------------------------------------------------------ A6. ------------------------------------------------------------------------------ B1. Their {x} is only applied to numbers in (0, 2). In particular, {m/6n} = m/6n, if m < 3n, and otherwise is (6n-m)/m. The other {m/3n} is a bit harder, but is clearly one of m/3n, if m < (3/2)n (3n-m)/3n, if (3/2)n <= m <= 3n (m-3n)/3n, if 3n < m < (9/2)n (6n-m)/3n, if (9/2)n <= m < 6n So we are asked to compute a sum of terms of the form (1/6n)*min(A,B). These A and B are, in the various intervals, m and 2m, if m < (3/2)n m and 2(3n-m), if (3/2)n <= m <= 3n 6n-m and 2(m-3n), if 3n < m < (9/2)n 6n-m and 2(6n-m), if (9/2)n <= m < 6n We can select the minimum in finer ranges: it's m, if m < (3/2)n m, if (3/2)n <= m <= 2n 6n-2m, if 2n < m <=3n 2m-6n, if 3n <= m <=4n 6n-m, if 4n <= m < (9/2) n 6n-m, if (9/2)n <= m < 6n So we sum m for m = 1, 2, ..., 2n and get (2n)(2n+1)/2; we sum 6n-2m for m = 2n+1, ..., 3n and get 6n(n) - ((3n)(3n+1)-(2n)(2n+1)); we sum 2m-6n for m = 3n+1, ..., 4n and get ((4n)(4n+1)-(3n)(3n+1)) - 6n(n); we sum 6n-m for m = 4n+1, ..., 6n-1 and get (2n-1)+...+1 = (2n-1)(2n)/2. Looks to me like the sum is 6n^2, so S_n = n . (I'm positive there's a better solution somewhere!) ------------------------------------------------------------------------------ B2. We are given that f f' + f' f'' = - x g (f')^2. But the left side is half the derivative of F = f^2+(f')^2; the right side is clearly <= 0 for x>0 and >=0 for x < 0. So F is increasing on ( - oo , 0 ) and decreasing on (0, oo ). In particular, its maximum value is at x=0. Of course its bounded below by zero, too, so F is bounded. It follows that f (and f') are also bounded. This is a simple variant of the well-known tricks we calc teachers inflict on students learning how f+f'' is related to sine and cosine... ------------------------------------------------------------------------------ B3. In order to keep this argument elementary, let us make it an integer question. Let L be the LCM of all the integers m = 1, .., n; it's the product of the largest power of each prime less than n. Then S = Sum(L/m) is a sum of integers; it sums to (L/q_n) * p_n, so 5 doesn;t divide q_n iff S is congruent to zero modulo the largest power 5^k less than n. That is, our problem is to show: if n = a0*5^k + a1*5^(k-1) + ... is the base-5 representation of a number n, then the integer sum S = Sum (L/m) is congruent to zero mod 5^k iff ... We will show that having the sum be a multiple of 5^k is well-nigh impossible; indeed, one can't even get it to be a multiple of 125, so if k>=3, then we're sunk. Well, why wouldn't S be a multiple of 125? After all, four out of five terms being added have m prime to 5, hence L/m is a multiple of 5^k, and hence (for k>2) a multiple of 125. We need only check the remaining terms, in fact, we need only check those terms with m a multiple of 5^(k-2); for in these cases L/m is not a multiple of 5^3. Is S even a multiple of 5? Well, every term L/m being summed is a multiple of 5 except when m = 5^k, 2*5^k, ..., a0*5^k. These contribute a sum of L'+L'/2+L'/3+..., where L'=L/5^k is an integer prime to 5. Depending on a0 this sum is either L', 3*(L'/2), 11*(L'/6), or 25*(L'/12). Only the last is a multiple of 5, that is, we must have a0=4. Is S a multiple of 25? Again the answer depends only on the few terms 5^(k-1), .., 5^(k-1)*(5*a0+a1). As a0=4, this is the sum of 20 to 24 terms. We've summed the ones actually divisible by 5^k (and got 25(L'/12) ). The others can be summed easily if a1=4: we are adding 5L'/i where i ranges over the integers less than and prime to 25, that is, for i in Z/25^*. Well, in Z/25, this is 5L' times the sum of the reciprocals of all elements, which is the sum of all elements, which is preserved under negation, and thus is zero. So S is indeed a multiple of 25 if a1=4. Counting backwards we compute that the same is _not_ true if a1=3, 2, or 1, but holds if a1=0. Well, now, is S a multiple of 125? Once again, we sum only over the m which are multiples of 5^(k-2). We have seen that the multiple of 5^k sum to 25(L'/12), and the other multiples of 5^(k-1) sum to (5L')*(a multiple of 25). Now we need only sum over the _other_ multiples of 5^(k-2). Each gives a summand which is a multiple of 25L'; we need only determine if that multiplier is a multiple of 5. It's easily checked to be so for the sum of any 5 consecutive 5-regular reciprocals. The final value of the sum thus depends only the value of a2: the last a2 summands increase the total by an amount congruent to 25, 100, 100, 25, or 0 mod 125, respectively. But now we have all the terms grouped into multiples of 125 except a few: the multiples of 5^k gave a sum of the form 25(L'/12) (which is congruent to 75 mod 125), and the final (ungrouped) multiples of 5^(k-2) add either 0, 25, or 100 mod 125. In no case is the sum = 0 mod 125. Thus S cannot be congruent to 0 mod 125. If k>=3, that means S is not a multiple of 5^k, and thus 5 | q_n . So all the values of n in problem B3 must be n = a0*5^k + ... with k <=2, so that n < 125. For k>0 we have the constraint a0=4, and for k>=1 we have the additional constrain a1=(0 or 4). Thus our n must be k=0: a0 k=1: 4*5 + a1 k=2: 4*25 + 4*5 + a2, or 4*25 + 0*5 + a2 that is, n={1, 2, 3, 4; 20, 21, 22, 23, 24; 100, 101, 102, 103, 104; 120, 121, 122, 123, 124} (The only idea here is to note that the sum of the "top 4" "sinks down" 2 "levels", as does the sum of the "next 20"; but the former sinks down to 1/12 mod 5, which can't be balanced by anything in the "next level". On the other hand, actually getting that to paper without "quotes" proved to be a real challenge!) ------------------------------------------------------------------------------ B4. Note that by construction a(m,n)=0 if n<0 or n>2m, so the sum S_k in question is really a sum over all integers i. This makes the bookkeeping a little simpler. I claim S_(k+1) = S_k-S_(k-1)+S_(k-2). Indeed, by definition we have a(m+1,n)=a(m,n)+a(m,n-1)+a(m,n-2) so a((k+1)-i,i) = a(k-i,i) + a((k-1)-(i-1),i-1) + a((k-2)-(i-2),i-2) Taking an alternating sum over all i now proves my assertion. Since a brief calculuation give S_k for k=0, 1, 2 to be 1, 1, 0 we then compute succeeding values to be 0, 1, 1, 0, ... In particular, we have returned to the original sequence of 3 values, so of course the remaining values will repeat (in blocks of 4) and so especially we see S_K is either 0 or 1. ------------------------------------------------------------------------------ B5. So we have a sequence of integers a_1 = 2 and a_(i+1) = 2^(a_i). We must show a_n = a_(n-1) mod n, but in fact more is then true: a_i = a_(i-1) for all i>= n. This we prove by induction (it's clearly true when n=1,2). Suppose it's known to be true for all n < N. If N is odd, 2 is an invertible element of Z/NZ, and so by Euler's theorem, 2^phi(N) = 1 mod N. More generally, then, 2^r = 2^s whenever r = s mod phi(N). Since phi(N) < N, we have by induction that a_i = a_(i-1) mod phi(N) for all i >= phi(N), and in particular for all i >= N-1. So Euler's theorem gives 2^(a_i) = 2^(a_(i-1)) mod N, that is, a_(i+1) = a_i mod N whenever i+1 >= N. That completes the induction in this case. If N is a power of 2, say N=2^k, then all a_i = 0 mod N as long as a_(i-1) > k. In particular, a_i = a_(i-1) mod N for i >= N, which is the induction statement. Finally, if N = N1*N2 with N1 a power of 2 and N2 odd, then a_i = a_(i-1) modulo both N1 and N2 as long as i is at least as big as both. By the Chinese Remainder Theorem, a_i = a_(i-1) mod N for those i. This completes the induction; taking in particular i = N gives the desiredd conclusion. ------------------------------------------------------------------------------ B6. Dissection in what category? Is a "part" just a subset or a triangle or ... ? I assume this problem allows decompositions into arbitrary subsets. I will describe a decomposition first, then show it is optimal. ASCII is hardly the right medium here, so let me advise the reader to draw a picture something like this: place a roughly regular pentagon in the middle of the triangle, with two edges along the two longest edges of the triangle, one edge marking off an isoceles triangle at the top of the figure, and the other two edges meeting a little above the bottom of the triangle. Mark an edge from there to the middle of the short leg so as to create a quadrilateral in each of the two lower corners. That will be an optimal dissection with suitable length sides. Here is the construction in detail. Label the vertices of the original triangle A, O, and B, with OA the vertical edge and OB the horizontal one. Mark off segments of length r on each end of the hypotenuse and on the top end of the vertical side. (I will compute r in a moment; it's about 1.90. For this construction to make sense, we will need 3/2 < r < 2.) Mark also the midpoint of the bottom edge and a point on that edge of distance r from B. Finally mark a point on the vertical edge a distance r from this last point. We now have points on the perimeter of the triangle which I label, in clockwise order, O, C, D, A, E, F, B, G, H. Also construct a point X in the interior to be directly above G and of distance r from O. (It's also of distance r from B, right?) Then pentagon will be CDEFX, the quadrilaterals OCXH and BFXH and the isoceles triangle ADE. What is the diameter of this dissection? The diameter of ADE is r (since angle A is less than pi/3). Likewise BFXH has 3 interpoint distances equal to r; FH is less because the angle at B is less than pi/3, and likewise FX must be even less; finally, a little Pythagorean work on HGBX shows HX is less than r assuming r < 3. We must work harder to get the diameters of the other two pieces. HC and OX are of length r; OH is 3-r < r, and we have seen HX < r. OC must be less than HC. A prodigious effort to track right triangles suggests CX^2 = (r^2+6r-9) - (2r-3)sqrt(6r+9); the condition that CX be more than r is that r < 3/2, which we have agreed not to do. Thus the diameter of this quadrilaterial is only r. We turn finally to the pentagon. All its outer edges have lengths less than r by previous results. I will compute the conditions necessary to guarantee that the other five inter-point distances be <=r; the condition that EX be <=r will force an lower bound on r which we then take as our definition of r. I must use coordinates: in order of ease we have O(0,0) A(0,4) B(3,0) G(3/2,0) D(0,3-r) H(3-r,0) C(0,sqrt(6r-9)) AB is 4x+3y=12, so we find E((3/5)r, 4-(4/5)r), F(3-(3/5)r, (4/5)r) Finally, X( 3/2, sqrt(r^2-9/4) ). I compute the five distance, set equal to r, solve for r. Clearly as r decreases from 2 to 3/2, say, these distances will decrease, so the diamter is less than or equal to r as long as we keep r larger than the largest of these roots in the interval (3/2, 2). For example, the equation for DX has a root around 1.65, meaning that DX < r as long as r > 1.65. For CE, the root is about 1,74; for EX it's 1.75; for CF it's 5/8; and for DF it's r0 = (36-3sqrt(14))/13, which is about 1.90, the largest of the five. This then is the constraint: keep r around 2, and the pentagon will have small diameter. Shrink it to 1.90, and the diameter increases to something larger than r. So we have our construction and have proved that its diameter is really r0. Now suppose there is a construction with a smaller diameter. In particular, O, A, B, and (say) (3/2, 4/2) must be in different parts. In addition, the parts containing A and B must lie in semicircles of radius r (the diameter of the dissection) passing near D and E (respectively F, X, and H). But if r < r0, this will leave points D and F outside these three regions, hence in the same remaining region, hence of distance less than r, a contradiction if r < r0. As you can see, this last paragraph is simple. It's fairly clear at the outset how to proceed. But I see no easy proof that with this r, the remaining pieces do indeed have a diameterat most r0. I used Maple to verify my calculations, which is of course not permitted on the exam. dave ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Putnam exam 1997 -- some answers available. Date: 7 Dec 1997 09:44:41 GMT Well, it's that time again. The Putnam exam was administered today at colleges and universities in North America. Usually we get a flood of posts right away, but I don't see any yet. I'd like to see answers to a few of the ones I missed. Rather than post solutions this year, I'll just leave some at http://www.math.niu.edu/~rusin/problems-math/putnam.97 Maybe it's just brain atrophy but I had a hard time with several of the problems this year. There were also some that I thought would be straightforward, but took more work than I expected to get it at all close to complete. I wasted kind of a long time with problem A3 and didn't get what I thought I should get; consequently I haven't yet even had a chance to really think about a couple of others (A2 and A6). A1 was the standard get-your-feet-wet problem; a good one, I thought. I though A4 and B4 were really closer to homework problems than Putnam problems, (but I guess that explains why my students think my homework sets are too hard.) B2 was really a generalization of the formula sin^2+cos^2=1, so calculus teachers have a better chance with that one. I had a hard time expressing answers to B1 and B3, although the ideas are simple enough. Problem A5 was also clear from the start although I didn;t expect the answer I got. I also liked B5, but don't tell my abstract algebra students, who have a test on Euler's theorem next Wednesday, and I may have just found a test question... Problem B6 seemed really laborious. I must have done something wrong. Here's the problem. Imagine that my ascii-art consisted of straight line segments: "The dissection of the 3-4-5 triangle shown below has diameter 5/2. * |\ | \ |____\ 5 | /|\ | / | \ |/ | \ *____|____* 3 Find the least diameter of a dissection of this triangle into four parts. (The diameter of a dissection is the least upper bound of the distances between pairs of points belonging to the same part.)" That's it. (When did "dissection" and "part" become standard nomenclature and why wasn't I informed? Are we to work with line segments? curves? arbitary subsets of the triangle?) Anyway, I think I see what to do, as I can make a construction with the lowest possible diameter, but _proving_ that I've got the LUB of the distances is quite a chore; there are so many pairs of vertices to consider. Did anyone see an easier way out? dave ============================================================================== From: bhunt@noJUNKipst.umd.edu (Brian R. Hunt -- delete noJUNK to reply) Newsgroups: sci.math Subject: Re: Putnam exam 1997 -- some answers available. Date: 7 Dec 97 16:38:53 GMT rusin@vesuvius.math.niu.edu (Dave Rusin) writes: >Well, it's that time again. The Putnam exam was administered today at >colleges and universities in North America. Usually we get a flood of >posts right away, but I don't see any yet. I'd like to see answers to >a few of the ones I missed. >Rather than post solutions this year, I'll just leave some at > http://www.math.niu.edu/~rusin/problems-math/putnam.97 Looks good to me, except I disagree w/ B6 (see below). Your solution to B4 is much nicer than the ugly mess I had in mind. Some comments on the other problems: A2: The basic idea is this. Once you have n players with multiple pennies in front of them, an odd value of n tends to produce a stable cycle (BAD), while an even n tends to redistribute the wealth to n/2 "haves" and n/2 "have-nots" (GOOD). The have-nots all drop out in the same round. So then the question is whether n/2 is odd or even. By looking at what goes on in the first couple rounds, you can deduce that n = 2^k + 1 or 2^k + 2 is necessary and sufficient. But all you really need to do is take one of these sequences, say n = 2^k + 2, and show what happens. After the first 2 players drop out, you have a distribution 311...1 with 2^k players remaining. After 1 round you have 422...2 with 2^(k-1) players. After another couple rounds you have 644...4 with 2^(k-2) players. Etc. A3: I only gave this one a cursory look at the time; I'm not sure I remember what the second term was, but I suspect now that I was errant in viewing it as an exponential as well. In any case, once you reduce the first term to x*e^(-x^2/2), you can multiply everything out, integrate term-by-term, and perhaps something nice will happen. A6: Work out the first few values of n and you start to see Pascal's triangle. If I recall the notation correctly, c = n-1 and x_k = (n-1 choose k-1). This makes the recursion work, and it shouldn't be too hard to show that any larger value of c makes x_(n+1) positive. B6: I got 25/13, as did one of the students I was proctoring. Then again I thought the answer was 15/8 for a while, so who knows -- seems like a problem that lends itself to convincing but wrong answers. Here's a rough picture of what I have in mind. A |\ | \ | \E D|__-\ | \F |____/\ | / \ |__|____\ C G B Coordinates: A = (0,4), B = (3,0), C = (0,0), D = (0,27/13), E = (15/13,32/13), F = (24/13,20/13), G = (14/13,0). DE and FG are circular arcs of radius 25/13. The unlabeled horizontal line runs from (0,15/13) to (19/13,15/13). Note that D is exactly 25/13 from F. I think that all other relevant distances are smaller. Suppose a diameter r < 25/13 were possible. The sets containing A and B could respectively extend no further than circular arcs DE and FG with radius r. Assume all sets are closed, so that C, D, E, F, G must each belong to one of the remaining 2 sets. Check that lengths CE and GE are > r, so that C and G must be in the same set. Check that DG and CF are > r, so that D and F must both be in the opposite set as C and G. Thus DF must be at most r, which requires r >= 25/13. -- Brian R. Hunt bhunt@ipst.umd.edu ============================================================================== From: "Travis Fisher" Newsgroups: sci.math Subject: Re: Putnam exam 1997 -- some answers available. Date: Sun, 7 Dec 1997 11:14:15 -0600 Dave Rusin wrote in message <66dr69$rtt$1@gannett.math.niu.edu>... > >Well, it's that time again. The Putnam exam was administered today at >colleges and universities in North America. Usually we get a flood of >posts right away, but I don't see any yet. I'd like to see answers to >a few of the ones I missed. Well, I can fill you in on problem A2. Two possible sets are {2^n+1} and {2^n+2} for n in N. The second one is a bit easier to prove, so that's what I'll do here. I will call a player live who still has coins. I will call a round the series of passes that starts with the lowest numbered live player passing and ends with the highest numbered live player passing. Note that in the first round, the first player is eliminated, all even-numbered players are eliminated, and all odd numbered players except for player 3 end up with 2 coins. Player 3 has 2 coins plus the additional one or two passed by the last player; with n=2^n+2 the last player is even and passes two coins. So after the first round, 2^(n-1) players remain, where the first has 4 coins and is about to pass 1, while all subsequent players have 2 coins. This is begging for proof by induction, where the inductive assumption is that a round begins with 2^k live players (k>=1), where all but the first player have the same number of coins. Call the players p1,p2,..,pk in that playing order. The claim is that given such a setup, the next round where players are eliminated, players p2,p4,..,pk will all be elimanated, leaving 2^(k-1) players where all but the first have the same number of coins. We can see this by noting that each round, the even numbered players receive 1 coin and pass 2, and so have a net loss of one coin for the round, while the odd players receive 2 coins and pass 1, and so have a net gain of one coin for the round. Since all the even players start with the same number of coins, they all run out during the same round. Note this does not affect their coin passing that round. Similarly, all odd players except the first have the same net gain through this process, and so end that round with the same number of coins. So then by induction, there will be a round where 2^0 = 1 players remain. Clearly this last remaining player must have all the coins. --Travis Fisher tfisher@math.unl.edu ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Putnam A3 (was: Re: Putnam exam 1997 -- some answers available.) Date: 7 Dec 1997 19:09:21 GMT Problem A3 asks us to evaluate a definite integral \int_0^\infty (...)*(...) where the two factors are written as power series. I was heading down a blind alley yesterday, which not only prevented me from solving this problem but kept me from working on the others! The first power series is easily recognized to be that of x*exp(-x^2/2). The second is g(x) = 1 + x^2/2^2 + x^4/(2^2 4^2) + x^6/(2^2 4^2 6^2) + ... This is actually a Bessel function ( BesselI(0,x) ) but I assume we're not supposed to know that. I thought we were supposed to notice that g satisfies a differential equation x g''(x) + g'(x) = x g(x) so that an integral int( x f(x) g(x) ) can be rewritten as int(f(x) (x g')'(x)), thus allowing the use of integration by parts. Now I think this is wrong; at least according to maple there is no closed form antiderivative of int( x exp(-x^2/2) BesselI(0,x) ). Here's what I think we're supposed to do: write the integral as int_0^\infty x exp(-x^2/2) Sum( x^(2n)/(n!)^2/2^(2n) ) and expand into a sum Sum( (1/n!)^2 (1/2^(2n)) int_0^\infty x^(2n+1) exp(-x^2/2) That last integral is easy to get by induction. It's = 2^n int_0^\infty u^n exp(-u) du = 2^n [ -u^n exp^(-u) + n int u^(n-1) exp(-u) du ] using first substitution then integration by parts. Thus by induction the portion in the brackets is just n!, so the integral is 2^n n!, and the sum is Sum( (1/n!) (1/2^n) ) = exp(1/2), that is the answer to the original problem is sqrt(e). dave ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Putnam exam 1997 -- some answers available. Date: 7 Dec 1997 19:23:24 GMT In article , Brian R. Hunt -- delete noJUNK to reply wrote: >Looks good to me, except I disagree w/ B6 (see below). Hunt is quite right; I had a brain-o (that's like a typo but it's not the typing fingers which are to blame...). For some reason I set the coordinates of his point D to (0,3-r) rather than (0,4-r), giving a slightly wrong answer. But the analysis was the same. I stand by my original complaint: in this problem, establishing a lower bound of 25/13 on the diameter is easy because five points ABCDF can be found all of whose distances are at least 25/13, requiring each to be in a different "part" if parts of diameter < 25/13 are used. But to show a diameter of 25/13 is in fact achievable, one has to demonstrate that the diameters of the parts in a particular configuration really are 25/13 or less. >B6: I got 25/13, as did one of the students I was proctoring. Then >again I thought the answer was 15/8 for a while, so who knows -- seems >like a problem that lends itself to convincing but wrong answers. >Here's a rough picture of what I have in mind. > > A > |\ > | \ > | \E >D|__-\ > | \F > |____/\ > | / \ > |__|____\ >C G B > >Coordinates: A = (0,4), B = (3,0), C = (0,0), D = (0,27/13), >E = (15/13,32/13), F = (24/13,20/13), G = (14/13,0). > >DE and FG are circular arcs of radius 25/13. The unlabeled horizontal >line runs from (0,15/13) to (19/13,15/13). Note that D is exactly >25/13 from F. I think that all other relevant distances are smaller. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ This is the part which seems like a real pain in the extremity. dave ============================================================================== Date: Mon, 08 Dec 1997 10:57:42 +0000 From: Robin Chapman To: rusin@math.niu.edu Subject: Putnam solutions A4: E = phi(e) needn't be central. We can take phi to be constant, and this constant need not be in the centre. Note that E commuting with phi(x) for all x doean't imply E commutes with y for all y in G. A5: This is easier if you recall the result (due to Kummer?) that a prime p divides a binmomial coefficient (a+b choose a) to the order m, if m is the number of carries when a and b are added in base p. Thus as 10 is 1010 in base 2, the only odd binomial coefficients (10 a) occur when a = 0, 2, 8 and 10. Now refining a partition mulitplies the corresponding multinomial coefficient by a factor, so the only odd multinomial coefficients corrrespond to the partitions which are not refinements of (10-a) + a for a <> 2, 8. The only non-trivial one is 8+ 2 itself. -- Robin Chapman "256 256 256. Department of Mathematics O hel, ol rite; 256; whot's University of Exeter, EX4 4QE, UK 12 tyms 256? Bugird if I no. rjc@maths.exeter.ac.uk 2 dificult 2 work out." http://www.maths.ex.ac.uk/~rjc/rjc.html Iain M. Banks - Feersum Endjinn ============================================================================== From: Keith Wolcott Newsgroups: sci.math Subject: Different solution to Putnam A1 Date: Tue, 09 Dec 1997 16:44:18 -0600 Here is a different solution than I have seen posted for problem A1 of the Putnam competition. This solution is due to Hillel Gauchman. %Format: LaTeX2e \documentclass[12pt]{article} \pagestyle{headings} \setlength{\textwidth}{6.0in} \setlength{\textheight}{9.0in} \setlength{\oddsidemargin}{0.25in} % 1.25" margin on the side \setlength{\topmargin}{-1in} % the page head 0.5" from the top \begin{document} \thispagestyle{empty} \centerline{\bf PROBLEM A1, PUTNAM 1997} \medbreak \centerline {\bf PROBLEM} \medbreak \noindent A rectangle, $HOMF$, has sides $HO=11$ and $OM=5$. A triangle $ABC$ has $H$ as the intersection of the altitudes, $O$ the center of the circumscribed circle, $M$ the midpoint of $BC$, and $F$ the foot of the altitude from $A$. What is the length of $BC$? \vspace{4cm} \centerline {\bf SOLUTION} \bigbreak \centerline {\bf by Hillel Gauchman (Eastern Illinois University, cfhvg@eiu.edu)} \bigbreak \noindent Let $R$ be the circumradius of $\triangle ABC$. Denote by $K$ the point of intersection of median $AM$ and segment $OH$. It is known that the three points: the circumcenter, the centroid, and the orthocenter belong to the same line (the so-called ``Euler's line''). Therefore point $K$ must be the centroid of $\triangle ABC$. This allows us to make simple calculations: $AK/KM=2$, so $AH=2\cdot HF=10$, and from right $\triangle OHA$, ~~$R=OA=\sqrt{OH^2+AH^2}=\sqrt{11^2+10^2}$. Then from right $\triangle OBM$, in which $OB=R$, we find $BM=\sqrt{BO^2-OM^2}=\sqrt{11^2+10^2-5^2}=14$. Hence $BC=2\cdot BM=28$. \vspace{3cm} \noindent{\bf Notes.~~ (1).} If $HO=a$ and $OM=b$, then $BC=2\sqrt{a^2+3b^2}$. If $OHFM$ is a square with side $a$, then $BC=4a$. \bigbreak \noindent {\bf (2).} Triangle $ABC$ is determined uniquely since $AC=\sqrt{15^2+3^2}=\sqrt{234}$ (from right $\triangle AFC$), and $AB=\sqrt{25^2+15^2}=5\sqrt{34}$ (from right $\triangle AFB$). \medbreak \noindent In general case, $AB=\sqrt{2a^2+12b^2+2a\sqrt{a^2+3b^2}}$, and $AB=\sqrt{2a^2+12b^2-2a\sqrt{a^2+3b^2}}$. We conclude that $\triangle ABC$ exists (the inequality $2a^2+12b^2>2a\sqrt{a^2+3b^2}$ holds for all $a$'s and $b'$s) and is determined uniquely always. \end{document} ============================================================================== From: gross@math.utah.edu (Fletcher Gross) Newsgroups: sci.math Subject: Re: 00A07 1997 Putnam problems and unofficial solutions (TeX) Date: Tue, 09 Dec 1997 08:30:19 -0600 I have a shorter proof of A5. Namely if S is the set of all ordered 10-tuples that satisfy the condition and if G is the group of all permutations of 10 objects, then G operates on S and under this action, S is partitioned into orbits. The problem then becomes that of determining those orbits of odd length. The length of an orbit is the index in G of the subgroup fixing some member of the orbit so an orbit has odd length if and only if it is fixed by a Sylow 2-subgroup of G. Now a Sylow 2-subgroup of G has, in its action on {1, ..., 10}, exactly 2 orbits, one of length 8 and one of length 2. Thus if a member of S is fixed by a Sylow 2-subgroup of G, 8 of the integers must be equal and the other 2 are also equal, i.e., we must have 8/a + 2/b = 1. This is equivalent to (a - 8)(b - 2) = 16. This leads at once to five possibilities a - 8 = 1, 2, 4, 8, and 16. When a and b are not equal, there are 45 elements of S while if a = b, there is only one such element. Thus there are exactly 4(45) + 1 elements of S which are in orbits of odd length. Hence the number of elements in S is odd. -- Fletcher Gross Department of Mathematics University of Utah Salt Lake City, Utah 84112 email: gross@math.utah.edu ============================================================================== Date: Mon, 08 Dec 1997 14:56:15 +0000 From: Robin Chapman To: rusin@math.niu.edu Subject: Putnam B4 The generating function sum a_{m,n} x^n y^m is 1/(1-y(1+x+x^2)). The sum we're after is the y^k coefficient when we replace x by -y in this, i.e., the y^k coefficient of 1/(1-y+y^2-y^3) = (1+y)/(1-y^4). This is 1 if k is 0 or 1 mod 4 and 0 otherwise. -- Robin Chapman "256 256 256. Department of Mathematics O hel, ol rite; 256; whot's University of Exeter, EX4 4QE, UK 12 tyms 256? Bugird if I no. rjc@maths.exeter.ac.uk 2 dificult 2 work out." http://www.maths.ex.ac.uk/~rjc/rjc.html Iain M. Banks - Feersum Endjinn ============================================================================== Date: Mon, 8 Dec 1997 22:16:44 -0800 (PST) From: Ryan McCorvie To: rusin@math.niu.edu Subject: Re: Putnam exam 1997 -- some answers available. (fwd) Problem A6 works like this: Let X(z) be the generating function for the series. X(z) = x_k+1 * z^k It is routine to verify that the recurrance is equivalent to the following: X'(z) = cX - nzX + z(zX)' Or: X'/X = (c + (1-n)z) / (1 - z^2) Solving for X: X = (1+z)^-alpha * (1-z)^beta where alpha and beta are the values one obtains by partial fraction decomposition. 2*alpha = c + 1-n 2*beta = c + n-1. Recognize that X must be a polynomial if x_n+1 is zero because then xn+2 = (cx_n+1)/(n) = 0 and by the recurrance, all successive terms are zero. So -alpha, beta are nonnegative integers. c is maximized when c=n-1. SO (n-1 ) xk = ( ) (<-- binomial coefficient) ( k-1) Ryan McCOrvie ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Putnam question A3, finally the "right" solution Date: 19 Dec 1997 15:06:23 GMT I had written previously that I was sure problem A3 on the Putnam exam was to be solved by working with the differential equation which the (Bessel) function satisfies, but that I couldn't make that approach work. The problem's proposer wrote to remind me of the trick needed to make it work; now I can give this solution. Recall that problem A3 asks us to evaluate a definite integral of the form C = \int x*e(x)*g(x) dx (this and all other integrals below taken over [0, \infty]). The two factors were written as power series. The first power series is easily recognized to be that of e(x) = exp(-x^2/2). The second is g(x) = 1 + x^2/2^2 + x^4/(2^2 4^2) + x^6/(2^2 4^2 6^2) + ... This g satisfies a differential equation x g''(x) + g'(x) = x g(x). It turns out that this, and the DE e'(x) = -e(x), are really the only ingredients we need for the answer. The trick is to view the desired computation C as a particular value of a function with an extra parameter. Let H(y) = \int x*e(x)*g( x*y ) dx, Thus we seek H(1). For comparison, we have H(0) = \int x*e(x) dx = \int -e'(x) = -e(x) {\big |}_0^\infty = 1. We deduce H by looking to see what differential equation _it_ satisfies. We simplify notation a bit by writing H(y) = \int x*F(x,y) dx where F(x,y) = e(x)*g( x*y ). Since e and g satisfy second-order DEs, there will be relations among the second-order derivatives of F, too. Indeed, we compute F_y (x,y) = x*e(x)* g'( x*y ) and thus F_{yx} (x,y) = e(x)g'(xy) - x^2 e(x)g'(xy) + xy e(x)g''(xy) = -x F_y (x,y) + xy F(x,y) which may be interpreted as an integral equation instead: -\int xF_y (x,y) dx + y*\int x F(x,y) = F_y(x,y) {\big |}_0^\infty = 0. But the left-hand side is simply -H'(y) + y*H(y) ! (Well, OK, we do have to justify differentiating under the integral sign.) Very well, then, H(y) is the solution to H'(y) = y H(y) with H(0)=1. It is now elementary to deduce that H(y) = exp( y^2/2 ). In particular, C = H(1) = exp( 1/2 ). dave ============================================================================== From: Fred Galvin Newsgroups: sci.math Subject: Re: 1998 Putnam exam -- some solutions [SPOILER] Date: Tue, 8 Dec 1998 03:57:18 -0600 On 6 Dec 1998, Dave Rusin wrote: > B2. This is the closest I have seen to a mathematical physics problem on > the Putnam exam! Problem B2 on the 1997 Putnam contest was also a mathematical physics problem: "Let f be a twice-differentiable real-valued function satisfying f(x)+f''(x) = -xg(x)f'(x), where g(x) >= 0 for all real x. Prove that |f(x)| is bounded." Change the notation f(x) to u(t). For t > 0 it's a damped vibration problem, with time-dependent damping coefficient tg(t). For t < 0 the damping becomes negative, i.e., damped vibration in reverse time. By physical reasoning, the energy is maximum at t = 0. The mathematical proof of B2 consists of verifying this by taking the derivative of the energy.