Discussions of the 1998 Putnam exam. Here are 1. The problems; 2. My initial solutions (incomplete and in two cases (B2,B3) incorrect); 3. Followups and discussions by others (slightly edited). ============================================================================== A1. A right circular cone has base of radius 1 and height 3. A cube is inscribed in the cone so that one face of the cube is contained in the base of the cone. What is the side-length of the cube? A2. Let s be any arc of the unit circle lying entirely in the first quadrant. Let A be the area of the region lying below s and above the x-axis and let B be the area of the region lying to the right of the y-axis and to the left of s. Prove that A+B depends only on the arc length, and not on the position, of s. A3. Let f be a real function on the real line with continuous third derivative. Prove that there exists a point a such that f(a) . f'(a) . f''(a) . f'''(a) >= 0. A4. Let A1=0 and A2 = 1. For n > 2, the number A_n is defined by concatenating the decimal expansions of A_{n-1} and A_{n-2} from left to right. For example A_3 = A_2 A_1 = 10, A_4 = A_3 A_2 = 101, A5=A4 A3 = 10110, and so forth. Determine all n such that 11 divides A_n. A5. Let F be a finite collection of open discs in R^2 whose union contains a set E \subseteq R^2. Show that there is a pairwise disjoint subcollection D_1, ..., D_n in F such that Union( 3 D_j, j=1..n ) {contains} E. Here, if D is the disc of radius r and center P, then 3D is the disc of radius 3r and center P. A6. Let A, B, C denote distinct points with integer coordinates in R^2. Prove that if ( |AB| + |BC| ) ^2 < 8 . [ABC] +1 then A, B, C are three vertices of a square. Here |XY| is the length of segment XY and [ABC] is the area of triangle ABC. B1. Find the minimum value of 6 6 6 (x + 1/x) - (x + 1/x ) - 2 ---------------------------- 3 3 3 (x + 1/x) + (x + 1/x ) B2. Given a point (a,b) with 0 < b < a, determine the minimum perimeter of a triangle with one vertex at (a,b), one on the x-axis, and one on the line y = x. You may assume that a triangle of minimal perimeter exists. B3. Let H be the unit hemisphere {(x,y,z) : x^2 + y^2 + z^2 = 1, z >= 0 }, C the unit circle {(x,y,0): x^2 + y^2 = 1 }, and P a regular pentagon inscribed in C. Determine the surface area of that portion of H lying over the planar region inside P, and write your answer in the form A sin alpha + B cos beta, where A, B, alpha, and beta are real numbers. B4. Find necessary and sufficient conditions on positive integers m and n v\so that Sum_{i=0}^{mn-1} (-1)^{ floor(i/m) + floor(i/n) } = 0. B5. Let N be the positive integer with 1998 decimal digits, all of them 1; that is, N = 1111 ... 11. --(1998 digits)-- Find the thousandth digit after the decimal point of sqrt(N). B6. Prove that, for any integers a,b,c there exists a positive integer n such that sqrt( n^3 + a n^2 + b n + c ) is not an integer. ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: 1998 Putnam exam -- some solutions [SPOILER] Date: 6 Dec 1998 06:58:36 GMT The annual Putnam exam was held today (Sat. Dec. 5). This is a math contest for undergraduates in North America. The problems are posted separately. Attached are some solutions to most of the problems. If experience is any guide, it's unlikely that all the solutions here are fully correct... I'm still lacking a solution for A6 and part of B4. [SPOILER] A1. The length of the sides of the cube is determined by the fact that two opposite corners of the top face must touch the cone. By symmetry, these two points and the center line of the cone all lie in one plane. The intersection of that plane with the cube is a s x sqrt(2)*s rectangle, where s is the length of a side of the cube. The intersection of the plane and the cone is an isosceles triangle containing the bottom edge and top corners of the rectangle. (Boy, is flat text a bad medium for this!) Now note similar isosceles triangles: the height=3, width=2 one must be similar to the height=(3-s), width= sqrt(2)*s one. This gives a proportion from which we deduce 3 sqrt(2) s + 2 s = 6, or s = 6/(3 sqrt(2) + 2) = (9/7) sqrt(2) - (6/7) A2. "The unit circle" must mean the one centered at the origin (imprecise!) An arc s on the circle is determined by its endpoints p,q. We thus write A(p,q) and B(p,q) for the two areas in question; the statement is that A(p,q) + B(p,q) is a function of l(p,q), the arclength between the points. Since this is at heart a calculus question we might as well use calculus ideas: let's hold one endpoint fixed at p0 = (0,1). In other words, define A0( p ) = A( p0, q) and likewise B0; then A(p,q) = A0(q) - A0(p) and likewise B. These new functions are especially easy to analyze. The region whose area is A consists of three parts: the region whose area is B, a triangle which, with the first region, forms the circular sector subtended by the arc, and finally another triangle between the other and the horizontal axis. Calling the areas of these regions a1, a2, and a3 respectively, we have A = a1 + a2 + a3, B = a1, and a2 = a3. Thus A + B = 2(a1+a2), twice the area of a circular sector. Since the radius of the circle is 1, this sum is numerically equal to the length of the arc. So we have A(p,q) + B(p,q) = (A0(q) - A0(p)) + (B0(q) - B0(p)) = l0(q) - l0(p) = l(p,q), the length of the arc. A3. If there is a point where any of the derivatives vanish, we are done. Otherwise, by continuity, they each maintain a _single_ sign across the whole line. What we are led to is a lemma: if f and f'' each keep a single sign across the line, then they have the _same_ sign. Proof of lemma: Taylor's theorem may be written f(x) = f(0) + f'(0) x + f''(c)/2 x^2 for some c = c_x between 0 and x. If f''(0) < 0 then f''(c)/2 < 0 too by hypothesis, so for every x, f(x) < f(0) + f'(0) x. But this linear expression is certainly negative for some x, so f(x) is certainly negative. somewhere, and thus everywhere. Likewise f''(0) > 0 forces f(0) > 0, i.e., f(0) and f''(0) must have the same sign. Applying this lemma to f' we see f'(0) and f'''(0) have the same sign, too. Hence f(0) f'(0) f''(0) f'''(0) > 0. [Thanks to Richard Blecksmith for convincing me the problem is easy.] A4. Since I dislike trying to prove things about digit strings let me instead develop formulas for the A's. First let d(n) be the number of digits of A(n): d(1) = d(2) = 1 and d(n) = d(n-1) + d(n-2) by construction. This is the familiar Fibonacci sequence. Then the process of concatenation gives this recursion: A(n) = A(n-1)*10^d(n-2) + A(n-2) Now reduce mod 11 : A(n) = A(n-1)*(-1)^d(n-2) + A(n-2) mod 11. This suggests we need the parity of d(n) but an easy induction shows d(n) to be odd unless n = 2 mod 3. Thus we have the patterns: A(3k+1) = A(3k) + A(3k-1) mod 11 A(3k) = -A(3k-1) + A(3k-2) mod 11 A(3k-1)=-A(3k-2) + A(3k-3) mod 11. Now, a short calculation shows A(7)=A(1) and A(8)=A(2) (mod 11) so these three formulas give a proof by induction that A(n+6) = A(n) for all n. Since A(n)=0 mod 11 among the smallest n only when n = 1, 7, etc. we deduce that A(n) is a multiple of 11 iff n = 1 mod 6. A5. We can prove this by induction on the number |F| of disks in F; if |F| <= 1 there is nothing to prove. Let D1 be the largest disk in F, and let F' be the set of disks in F which do not meet D1; let E' be the union of all the disks in F'. By induction there are disks D2, D3, ... in F' which are disjoint and whose triples cover E', and of course by construction of F' these D_i are disjoint from D1. We need only show that 3D1 covers all the points in E which are not already in E'. But any such point must have been covered by one of the disks in F, and so if not covered by a disk in F' it lies in one of the disks meeting D1. Thus its distance from the center of D1 is less than r1 + diam(D) = r1 + 2 r <= 3 r1, it's then in 3D1. A6. Indeed, the points ABC in order must be _consecutive_ vertices of a square, I guess, but I didn't finish a proof. B1. This problem is considerably simplified with an identity familiar to Fermat's-Last-Theorem-solvers! For any n we have the identity x^n + y^n = sum( a_{n,i} (-xy)^i (x+y)^(n-2i) ) where a_{n,i} = (n/ (n-i) ) * binomial(n-i,i). This is easily proved by induction, but in this problem we only need it for a couple of small values: x^3+y^3 = (x+y)^3 - 3xy(x+y) x^6+y^6 = (x+y)^6 - 6xy(x+y)^4 + 9(xy)^2(x+y)^2 - 2 So in the problem at hand, let y=1/x and z=x+y. Then the fraction in question is z^6-(z^6-6z^4+9z^2-2)-2 6z^4 - 9z^2 ----------------------- = ----------- = 3z z^3 + (z^3-3z) 2z^3 - 3z Since it is clear that z = x+1/x takes on a minimum of z=2 at x=1, we conclude the fraction attains a minimum of 6 there. B2. This is the closest I have seen to a mathematical physics problem on the Putnam exam! If you stand in a room whose walls are two mirrors at a 45-degree angle, where do you look on the wall in front of you to see your back side? The answer is that the light rays will take a path of minimal length to reach your eyes, and hence will travel along the minimal triangle in question. On the other hand, the light rays will reflect off the mirrors at an angle equal to the angle of incidence. A quick diagram then shows the angle of the paths at (a,b) to be 90 degrees (more generally, twice the angle between the mirrors). Knowing that the minimal triangle is a right triangle and has the reflection property at the horizontal axis, I work out that if the fixed point is at (r cos u, r sin u) then the other vertices are at (r/(sin u + cos u), 0) and (r/(2 cos u), r/(2 cos u)) making the perimeter r/( cos(u) * (cos(u) + sin(u) ) ). I have to say I'm not really satisfied with this method of solution; this was too much computation and too much physics. I also tried simple multivariable minimization and even tried Lagrange Multipliers to avoid having to extract square roots. While the answers agree with mine, they don't seem any easier to me. B3. Here's the region we want the area of. Start with the unit sphere. Along the equator mark off five equally spaced points. Slice the sphere with five planes perpendicular to the plane of the equator, each of the five slicing off a circular cap with one of the five points as its center. The five circular caps are tangent along the equator. Slice in half along the equator to get the set whose area we want. Clearly this area is (1/2)( Sph - 5 Cp ) where Sph is the area of the sphere, Sph = (4/3) pi, and Cp is the area of each circular cap. Now, it is a standard (perhaps surprising) fact from calculus that the area of one of these caps is proportional to its depth from center point to slicing plane. When that depth is 2 we have Cp = Sph, so in general the relation must be Cp = (2/3)pi * depth. On the other hand, this depth is in our case the distance between the circle C and the midpoint of a side of the pentagon. Clearly the distance from that midpoint to the origin is cos(pi/5), so depth=1-cos(pi/5). So the area we seek is (1/2)( (4/3)pi - (10/3)pi(1-cos(pi/5)) ) or -pi + (5/3) cos(pi/5) {I note that the instructions regarding the format of the answer are pretty pointless...} B4. I believe the sum is zero iff m and n are divisible by the same powers of 2, but my proof is incomplete. Note that the product of the i-th and (mn-1-i)-th terms is (-1)^(m+n-2), so if m+n is odd, the summands cancel in pairs and the sum is zero. This occurs iff one of m,n is odd and the other is even. On the other hand if m and n are both odd, then there is an odd number of summands, so the result is =1 mod 2, and so never zero. Thus my claim holds if at least one of m, n is even. A similar proof covers one direction in the general case: if m = 2^r m' and n = 2^r n', let L = 2^r m' n'. Then in the sum, let i = L*u + j with u=0, ..., 2^r-1 and j = 0, ..., L-1. Since [i/m]+[i/n] = [j/m]+[j/n] + u(m'+n'), we may factor the sum into a certain sum over j and the sum sum( (-1)^(u(m'+n')), u=1..2^r ). But as long as m'+n' is odd, this sum is zero. That is, the original sum is zero if m and n are divisible by different powers of 2. I don't have a proof in the general direction for general pairs (m,n). It seems from numerical experiments that the sum is gcd(m,n)^2 in this case, so the factor 2^r I have pulled out, above, is only part of the story. B5. We have N = (10^1998 - 1)/9. Let us consider more generally the case N = (10^(2r) - 1)/9. What is sqrt(N) ? Certainly sqrt(N) = 10^r * sqrt(1 - 10^(-2r)) / 3. Now, the Taylor series for sqrt(1-x) at x=0 begins 1 - x/2 - ..., where subsequent terms may be estimated as (1/2)*(-1/4)(1-c)^(-3/2)*x^2 for some c between 0 and x. In particular the remainder is between 0 and -1/8 x^2. Thus we compute sqrt(N) = (10^r/3) - 10^(-r)/6 - 10^(-3r)/8 * epsilon for some epsilon in [0,1]. Naturally, the integer part of sqrt(N) thus begins with r 3's. After the decimal point, we have three contributions: + 1) An unterminating string of 3's - 2) A string of r 0's follow by a 1 and repeating 6's - 3) A string of at least 3r 0's followed by undetermined digits. The net sum is then a string of r 3's, a single 1, and at least 2r-2 6's. In particular, the (r+1)'st decimal digit is a 1. Taking r = 999 gives the answer "1". B6. We must show that it cannot be true that for every n there is a u with u^2 = n^3 + an^2 + bn + c. In fact, there cannot even be such a u for every _even perfect square_ n. For if n = (2k)^2, then we would have u^2 = (2k)^6 + a(2k)^4 + b(2k)^2 + c. Let v = (2k)^3 + a k, another integer. Then v^2 = (2k)^6 + a (2k)^4 + a^2k^2, so v is "probably" what u is. More precisely, we estimate |u^2 - v^2| in two ways: it's = |u-v| |u+v| >= |u+v| >= v = 8k^3 + ak but it's also = |(4b-a^2) k^2 + c | <= |4b-a^2| k^2 + |c|. Comparing these inequalities (dividing by k^2, say) we see that something which increases as k -> oo is bounded by something which decreases to a constant, a contradiction. So we have a slightly stronger result: if cannot even be true that sqrt(n^3+...) for infinitely many (even, square) integers. Some general remarks: 1. There was an awful lot of calculus on this test. Two square root estimates and another Taylor's theorem, two maximization problems, and two area/integral problems! 2. One could argue that the problem posers must have been reading the math newsgroups lately! Problem B6 was in sci.math.research as "if a polynomial's values are all square, is the polynomial square too?", Problem B1 uses an identity typical in Fermat's Last Theorem "proofs", and Problem A3 is perhaps suggestive of the one about a function all of whose derivatives where bounded. dave ============================================================================== From: hwatheod@leland.Stanford.EDU (theodore hwa) Newsgroups: sci.math Subject: Re: 1998 Putnam exam -- some solutions [SPOILER] Date: 6 Dec 1998 08:28:15 GMT : B2: ... : I have to say I'm not really satisfied with this method of : solution; this was too much computation and too much physics. I also : tried simple multivariable minimization and even tried Lagrange : Multipliers to avoid having to extract square roots. While the answers : agree with mine, they don't seem any easier to me. But the point at which the angle of incidence=angle of reflection can be determined without any computation. The result we want is: if P,Q are two points on the same side of a line l (all in the same plane), then the point R on l that minimizes the sum PR+RQ is the intersection of PQ' with l, where Q' is the reflection of Q. (Proof: PR+RQ = PR+RQ', but P and Q' are on _opposite_ sides of the line l, so the point of minimization must be the intersection of PQ' and l.) There is also physics motivation in this (imagine someone looking from 'inside' the mirror). Then the problem is easy. Let B be the given point (a,b). Fix a point A on the line y=x. What point on the x-axis minimizes the perimeter? Since BA fixed, the result above gives that the desired point is the intersection of AB' with l. The perimeter of the resulting triangle is equal to BA + AB'. (This is all easy to see if you draw a picture.) Now which point A on the line y=x minimizes this quantity? This is just another application of the reflection result!! This time the line is y=x and the given points are B and B'. Reflect B to B'', this time across the line y=x. The intersection of the line B''B' with y=x gives the desired point, and the perimeter is just B''B', the desired answer. If B=(a,b) then B' = (a,-b) and B'' = (b,a), and the perimeter is sqrt(2(a^2+b^2)). The vertices of the desired triangle (besides B) are the intersections of the line B'B'' with the lines y=x and the x-axis. We could replace those with any 2 (nonparallel) lines. : B6. We must show that it cannot be true that for every n there is a u : with u^2 = n^3 + an^2 + bn + c. Another solution shown to me by Professor Paul Cohen after the exam goes like this. Let f(n)=sqrt(n^3+an^2+bn+c), and let's suppose that we have f(n) integral for all positive integers n (or even sufficiently large integers n). If U denotes the finite difference operator taking a sequence g(n) to g(n+1)-g(n), then since f(n) is integral, U(U(f(n)) is also integral. On the other hand, f(n)=O(n^(3/2)), so U^2(f(n)) = O(n^(-1/2)) which tends to 0 as n tends to infinity. Since U^2(f(n)) is integral, this implies that U^2(f(n)) is identically 0 for large n, i.e., f(n) is a polynomial of degree 1 for large n, a contradiction. Another problem admitting a similar solution to the above is: Prove that if a is a real number such that n^a is integral for all positive integers n, then a is a nonnegative integer. (Let f(n)=n^a. Then U^k(f(n)) is integral, for all positive integers k. But U^k(f(n)) = O(n^(a-k)). Choose k so that a-k<0, then we find then U^k(f(n)) is identically 0 for large n, so f(n) is a polynomial of degree <= k-1 for large n, so a must be a nonnegative integer <= k-1.) ============================================================================== From: Edward D Lee Newsgroups: sci.math Subject: Re: 1998 Putnam exam -- some solutions [SPOILER] Date: Sun, 06 Dec 1998 09:55:31 -0500 [A6]: I think this solution works. Write |AB|^2 + |BC|^2 < 8[ABC] - 2|AB||BC| + 1 <= 8[ABC] - 2 |AB||BC| sin theta + 1 = 4[ABC] + 1 Here theta is the angle Newsgroups: sci.math Subject: Re: 1998 Putnam exam -- some solutions [SPOILER] Date: Sun, 06 Dec 1998 21:18:32 GMT > A2. I prefer this argument. Let p precede q in the anticlockwise sense. Let C be the intersection of the vertical line through p and the horizontal line through q. Then the area below the arc equals the area of the "triangle" with sides Cp, Cq and the arc pq plus twice the area of the real triangle 0Cp. Adding the corresponding expression for the other area gives twice the area of the sector 0pq. > A6. Indeed, the points ABC in order must be _consecutive_ vertices of a square, > I guess, but I didn't finish a proof. Yes. Let u be the vector BA and v the vector obtained from BC by a pi/2 rotation chosen so that u.v >= 0. Then we need to show u = v and are given (|u| + |v|)^2 < 4u.v + 1. A bit of rearrangement gives |u - v|^2 + 2|u||v| - 2u.v < 1 and so |u - v|^2 < 1. As u and v have integer coordinates then u = v. > B1.... > Since it is clear that z = x+1/x takes on a minimum of z=2 at x=1, > we conclude the fraction attains a minimum of 6 there. Yes, but the numerator is (x + 1/x)^6 - (x^3 + 1/x^3)^2: a nice difference of two squares! > B2... I have to say I'm not really satisfied with this method of > solution; this was too much computation and too much physics. I also > tried simple multivariable minimization and even tried Lagrange > Multipliers to avoid having to extract square roots. While the answers > agree with mine, they don't seem any easier to me. How about reflecting (a,b) through the x-axis and the line y = x to get the new points (a,-b) and (b,a). Each triangle obeying our required conditions maps to a "broken" line between these points, and so its perimiter is minimized when this broken line is a genuine line segment. This has squared length (a+b)^2 + (a-b)^2 = 2(a^2 + b^2). > B3... So the area we seek is (1/2)( (4/3)pi - (10/3)pi(1-cos(pi/5)) ) or > -pi + (5/3) cos(pi/5) Doh! the area of the sphere is 4pi not (4/3)pi :-) [As it happens, I also worked out the volume first :-(] > B4. I believe the sum is zero iff m and n are divisible by the same > powers of 2, but my proof is incomplete. Let S(m,n) denote the sum. I reckon that S(2m,2n) = 2(1 + (-1)^{m+n})S(m,n) from which the conjecture follows readily. This comes from looking at the terms for j = 2k, 2k+1, 2mn+2k and 2mn+2k+1 together in the sum for S(2m,2n) (for 0 <= k < mn). > B6....So we have a slightly stronger result: if cannot even be true that > sqrt(n^3+...) for infinitely many (even, square) integers. Much too complicated! There's a simple modulo 4 argument. We observe that f(n) = n^3 + an^2 + bn + c = 0 or 1 (mod 4) for each n. As f(n) and f(n+2) have the same parity then f(n) = f(n+2) (mod 4) for each n. For n = 0 and n = 1 this yields 2b = 0 and 2b + 2 = 0 (mod 4). Contradiction! Robin Chapman ============================================================================== From: hwatheod@leland.Stanford.EDU (theodore hwa) Newsgroups: sci.math Subject: Re: 1998 Putnam exam -- some solutions [SPOILER] Date: 6 Dec 1998 21:04:25 GMT, and Date: 6 Dec 1998 22:43:23 GMT : B4. I believe the sum is [non-]zero iff m and n are divisible by the same : powers of 2, but my proof is incomplete. I think you mean to say that the sum is _NONzero_ iff .... above. Use L=2^r lcm(m',n') instead. Then u=0,1,...,(2^r gcd(m',n'))-1 in the sum above, and the original sum is over j=0,1,...,L-1. The original sum is thus equal to sum_j (-1)^([j/m]+[j/n]) sum_u (-1)^u(m''+n'') where m'' = L/n, n''=L/m. As before, if m and n are divisible by different powers of 2, then m'' and n'' have opposite parity and the sum is zero. Otherwise, m and n are divisible by the same powers of 2, m'' and n'' are both odd, and the sum over u on the right consists of all 1's, giving a total of 2^r gcd(m',n') = gcd(m,n) since m',n' are odd. The other factor left is summed over j=0,1,...,lcm(m,n)-1, and we want to prove the identity sum( (-1)^([j/m]+[j/n]), j=0,1,...,lcm(m,n) - 1) = gcd(m,n) (*) for m,n divisible by the same powers of 2. This looks do-able, though I can't seem to work it out right now. ============================================================================== From: Iliya Bluskov Newsgroups: sci.math Subject: Re: 1998 Putnam exam -- some solutions [SPOILER] Date: Sat, 05 Dec 1998 17:33:24 -0800 > B2. I would suggest the following: Take M(a,b) to be the given point,A on Ox, B on y=x. Let M'(a,-b) be the symmetric image of M in terms of Ox, and M''(b,a) be the symmetric image of M in terms of y=x. Then the perimeter of ABM is the length of M'ABM''. It is minimum when A and B are on the line M'M''. The corresponding minimum perimeter is the distance between M' and M'', that is sqr[2(a^2+b^2)]. Iliya Bluskov ============================================================================== Date: Mon, 7 Dec 1998 01:13:27 -0600 (CST) From: Fred Galvin To: Dave Rusin Subject: Re: 1998 Putnam exam -- some solutions [SPOILER] [picking up an email thread; summarized here for clarity -- djr] FG: You don't really need a *continuous* third derivative for this, do you? Just that f'''(x) exists everywhere, right? DJR: Yes, except that earlier I had said > A3. If there is a point where any of the derivatives vanish, we are done. > Otherwise, by continuity, FG: Yes, that's what I was commenting on; I guess I confused the issue by quoting too much stuff. What I meant to say was that, if f''' exists everywhere and is never zero, you don't need continuity of f''' in order to conclude that f''' always has the same sign. DJR: Hmm, is that true? Of course there are functions which exist everywhere and are never zero yet don't keep a constant sign; is it clear they cannot be derivatives of anything else? FG: The following argument is paraphrased from p. 98 of Olmsted's _Real Variables_. Suppose that f(x) is differentiable everywhere, and f'(x) is never zero. Consider any two points a < b; we will show that f'(a) and f'(b) have the same sign. The maximum and minimum of f(x) on [a,b] must occur at the endpoints. If f(a) is the maximum and f(b) is the minimum, then f'(a) and f'(b) are both negative; if f(a) is the minimum and f(b) is the maximum, both are positive. Q.E.D. More generally (Exercise 47 on pp. 103-104): "If f(x) is the derivative of some function g(x), on an interval, then f(x) assumes (as a value) every number between any two of its values." I don't see a historical reference here, but I seem to recall that Darboux had something to do with this. ============================================================================== Date: 7 Dec 1998 02:38:47 -0000 From: "D. J. Bernstein" To: rusin@vesuvius.math.niu.edu, djb@cr.yp.to Subject: Re: 1998 Putnam exam -- some solutions [SPOILER] > So we have a slightly stronger result: if cannot even be true that > sqrt(n^3+...) for infinitely many (even, square) integers. Except, of course, if the k polynomial you wrote down really is a square, i.e., if b = a^2/4 and c = 0. Then you have to take non-square values of n. ---Dan ============================================================================== Newsgroups: sci.math Subject: Re: 1998 Putnam exam -- some solutions [SPOILER] Date: Mon, 07 Dec 1998 09:32:58 GMT From: Robin Chapman [B4:] When the sum (which I'll call S(m,n)) is non-zero it does equal gcd(m,n)^2. Let's first suppose that m and n are odd and coprime. Let (j mod m) be the remainder on dividing j by m so that (j mod m) = j - m[j/m]. Also (j mod n) = j - n[j/m]. Hence (j mod m) + (j mod n) = 2j - m[j/m] - n[j/n] = [j/m] + [j/n] mod 2. Hence S(m,n) is the sum of (-1)^(j mod m)(-1)(j mod n) for j=0 ... mn - 1. The pairs (r, s) = (j mod m, j mod n) run over all pairs with 0 <= r < m and 0 <= s < n and so S(m,n) = sum_{r=0}^{m-1} (-1)^r sum_{s=0}^{n-1} (-1)^s = 1. For odd r, m and n we have S(rm, rn) = r^2 S(m,n). We get this by taking together for each j' with 0<= j' < mn the terms for j = trmn + rj' + u where 0 <= t, u < r. Similarly for any m and n we have S(2m,2n) = 2(1 + (-1)^{m+n}) S(m,n). This suffices to show that S(m,n) = gcd(m,n)^2 whenever m and n have the same 2-adic valuation. Robin Chapman ============================================================================== Date: Thu, 6 May 1999 20:59:17 +0900 From: pyunsuengchur To: rusin@math.niu.edu Subject: putnam 1998-A6 [A6]: let B = (0, 0), A = (x_1, y_1), C = (x_2, y_2). And x_1, x_2, y_1, y_2 are integers. LHS : (|AB| + |BC|)^2 = |AB|^2 + |BC|^2 + 2|AB||BC| >= |AB|^2 + |BC|^2 + 4[ABC] (Because of |AB||BC|/2 >= [ABC]) Finally, the given inequality can be converted to |AB|^2 + |BC|^2 < 4[ABC] + 1. LHS : |AB|^2 + |BC|^2 = ( (x_1)^2 + (y_1)^2 ) + ( (x_2)^2 + (y_2)^2 ) RHS : 4[ABC] + 1 = 2*| x_2*y_1 - x_1*y_2 | + 1 If x_2*y_1 - x_1*y_2 < 0, add 2*(x_2*y_1 - x_1*y_2) to both sides. Therefore (x_2 + y_1)^2 + (x_1 - y_2)^2 < 1 LHS is a nonnegative integer. So LHS is zero. ===> x_2 = -y_1, y_2 = x_1. If x_2*y_1 - x_1*y_2 >= 0, add 2*(x_1*y_2 - x_2*y_1) to both sides. Like upper process, x_2 = y_1, y_2 = -x_1. Finally, A, B, C are three vertices of a square. (proof ends) ============================================================================== Date: Wed, 29 Sep 1999 18:37:16 -0600 From: "Bob Palais" To: rusin@math.niu.edu Subject: Putnam '98 B-2 Here's another observation on a Putnam solution- You can turn the physical reflection principle into a more satisfying = mathematical proof and an easier solution, if I'm correct, by appealing to = the principle upon which it is based. If you reflect the point (a,b) in = the y=3Dx mirror, then the distance from any point on the x-axis to any = point on y=3Dx and back to (a,b) is equal to the distance to the same = point on y=3Dx and then to the reflected point, (b,a). The shortest of = these paths will naturally be the straight line from the point on the = x-axis to the reflected point (b,a). This can be made rigorous by two = Pythagorean comparisons, and becomes the geometric basis for the principle = of reflection: minimal path <-> angle of incidence =3D angle of reflection.= =20 However, if you apply it twice in this instance, and also reflect (a,b) in = the x-axis to (a,-b), then any broken path from (a,-b) to a point on the = x-axis to a point on y=3Dx to the point (b,a) will be equal to the perimeter of the triangle whose vertices are (a,b) and the same two = points. The minimum is taken by the straight line joining (a,-b) and (b,a): \sqrt{(a-b)^2 + (a+b)^2}. I compared with your polar formula, and wasn't able to get them to agree, but that doesn't mean they = don't!