PUTNAM 2004 --- ANSWERS ========================================================================== || As usual I am attaching here (1) my initial post to sci.math outlining | || my solutions to the Putnam problems, followed by (2) other answers || || posted or emailed to me. The latter include comments about problems || || A-2 (many; similar), A-4, (many; not similar!), A-5 (hard!), A-6, || || B-1, B-2 (many; similar), B-5, B-6 || ========================================================================== {Note: in future years I should encourage people to retitle their threads for specific questions } From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Putnam Exam 2004 -- [*SPOILERS*] Date: 5 Dec 2004 05:31:02 GMT Message-ID: The Sixty-Fifth Annual Putnam Exam was held today. I have already posted a copy of the questions. Here are as many answers as I have at this moment; I have nothing to say about A-5 and B-6. If I were the grader I wouldn't give myself full credit for some of these answers but I think rather than nail down all the details I will wait for someone else to provide the slickest answers, making the drudgery unnecessary... (See Problems A-2, A-4, and problems with detailed computations such as B-3, B-4, B-5.) Overall I thought this was an easier exam than is typical, which made the event much more fun for the "average" students taking the test. I will add these answers and any other interesting responses to the files I make available about Putnam questions; see http://www.math.niu.edu/~rusin/problems-math/ A-1. Suppose that S.O.'s success count S(N) stayed strictly below 0.80 N for all N < K, but that S(K) >= 0.80 K. This requires S(K-1) = S(K) - 1. Then from S(K-1)/(K-1) < 4/5 and S(K)/K >= 4/5 we conclude that 0 <= 5 S(K) - 4 K < 1 ; since 5 S(K) - 4 K is an integer, it must then equal zero, so S(K) = 4/5. Comment: Obviously the same proof works for any percentage of the form 1 - 1/m with integer m, but for more general percentages the result is false. This problem will make a very pretty example the next time I teach the Intermediate Value Theorem :-) A-2. From Heron's formula, the area and side lengths of a triangle satisfy 16 A^2 = 2 (a^2b^2+a^2c^2+b^2c^2) - (a^4+b^4+c^4) Viewed as a quadratic polynomial in X = a^2, this function is clearly increasing as long as X < (b^2+c^2), which means that the area of a triangle increases with the length of any side as long as the angle opposite that side is acute (a^2 < b^2 + c^2 ). (A student pointed out to me at lunch that this is also obvious from A = (1/2) b h, where the height h of the triangle varies with a but c is fixed; the maximum height occurs with sides b and c perpendicular.) It then suffices to observe that we can transform triangle T_1 to T_2 by a sequence of operations which lengthen just one edge at a time. This is not entirely obvious since, for example, we are not given that the smaller triangle is acute. But it's easy to see in a sketch which I will not attempt in ASCII, showing the portion of the positive octant in a,b,c -space which corresponds to triangles ( a < b+c, etc. ); the acute triangles are the ones external to three cones around the coordinate axes ( a^2 < b^2 + c^2, etc.) If one always lengthens the shortest edge (from among those that need to be lengthened to change T_1 into T_2), then that will always be opposite an acute angle. (An obtuse angle will always be opposite the _largest_ side, and that cannot the the only side remaining to be lengthened since T_2 is acute.) Note: I guess I had never before stopped to think about under exactly what conditions it is true that lengthening the sides of a triangle increases the area. Now I know! A-3. We prove by induction that u_n = (n-1)!! = (n-1)(n-3)(n-5)..., which is easily checked to be valid for small n. Of course this will mean the u_n are integral. If the claim is true for u_n and u_{n+2} then u_{n+2} = (n+1) u_n, so the first column of the matrix in the determinant is a multiple of u_n, and we have simply the recurrence relation u_{n+3} = (n+1) u_{n+1} + n!/u_n = (n+1) n!! + n!! = (n+2) n!! = (n+2)!!, providing the inductive step. A-4. This is a heavily-used formula when n = 2 : xy = (1/4)( (x+y)^2 - (x-y)^2 ). I guess I never really thought about generalizing it before! It suffices to arrange it so that the right side is a nonzero multiple of every x_i ; for then it is a degree-n polynomial and also a multiple of x_1 x_2 ... x_n, so the quotient of the two sides is a constant (necessarily rational, as can be seen from substituting x_1 = ... = 1); we can then divide through to make the constant be 1. If we arrange it so that the right side is symmetric in the x_i, then it suffices to make sure it vanishes when x_1 = 0. For odd n this is easy: for any subset T of N = {1, 2, ..., n}, let S(T) = the sum of the x_i with i in T. Then consider X = \sum (-1)^|T| ( S(T) - S(N-T) )^n , the sum taken over all subsets T of N. When we substitute x1=0 we obtain an alternating sum of terms of the form ( S(U) - S(M-U) )^n where M = N - {1}. Each such term arises exactly twice, once from S(U union {1}) - S(M-U) and once from S(U) - S(N-U); since the cardinalities of U and U union {1} are of opposite parity, these two summands will cancel. Thus, X vanishes when x1=0. On the other hand, X (apparently) doesn't vanish identically; for example, when all x_i equal 1, we have c = \sum (-1)^|T| ( |T| - |N-T| )^n = \sum (-1)^k (2k-n)^n C( n,k ), which seems to equal (-2)^n n! (I computed the first few examples but didn't prove this formula in general.) So whatever the value of c really is (it's obviously integral) we can divide X by c to get a sum which is a multiple of x1, and thus of each x_i, and thus of the product x1 x2 ... x_n, but the quotient must be both constant and taking the value 1. I didn't take advantage of the opportunity to use 0 as a coefficient! A-5. No clue. I worked out the case n=1 completely; the expected number of components is (m+1)/2 . I suppose there might be some kind of induction argument, but since they ask us to prove the number of components is AT LEAST mn/8, that suggests that what we're supposed to do is to find a lot of configurations with lots of components, so that we can bound the expected number without doing all the grubby computations. A-6. Heh, heh, check this one out: Let F(x,y,z,w) = f(x,y) + f(z,w) - f(x,w) - f(z,y); then integrate F^2 over the box [0,1]^4 . Done! (This is the distillation of about 5 pages of computations, followed by a great big step back to look at What The Computations Really Mean. I have learned that to understand these integral inequalities it pays to think in terms of step functions and simple functions; writing all that out gave me a solution but then I realized this other way to say it. Note that it is critical that the domain of integration be the UNIT square.) B-1. This is really standard. Write r = p/q in lowest terms; then we have c_n p^n + c_{n-1} p^{n-1} q + ... + c_0 q^n = 0 and so for each j between 0 and n we see q^j divides c_n p^n + c_{n-1} p^{n-1} q + ... + c_{n-j+1} p^{n-j+1} q^{j-1} = p^{n-j}( c_n p^{j} + c_{n-1} p^{j-1} q + ... + c_{n-j+1} p^1 q^{j-1} ) Since p and q are coprime, q^j divides the other factor. Dividing through, we may express the integer quotient as a polynomial in r. B-2. Another slick one: Let S = {1, 2, ..., m}, T = {m+1, ..., m+n}. How many functions are there from S union T to S union T ? (m+n)^(m+n). Among those are the functions that send precisely m elements of the domain to S, and the other n elements to T. There are C(m+n,m) ways to choose which elements go to S, and once those are chosen there are m^m n^n such functions. So (m+n)^(m+n) >= (m+n)!/m!n! m^m n^n . B-3. If a > 2 we may use a constant function: a rectangle measuring a by 2a/(a-2) has perimeter and area equal. If a<2 there is no such function. The area is a m where m is the mean value of f over [0,a], which is certainly no larger than the maximum value M of f on the interval. On the other hand, the perimeter is at least the length of the line segments joining (0,0), (a,0), and (x,M) for some x in the interval, but each of the non-horizontal segments has length more than M, so the perimeter is more than 2M, which is more than aM, which is more than a m, the area. The case a=2 is similar; just use the fact that the perimeter is then at least 2 + 2 sqrt(1 + M^2). B-4. This is pretty standard too. One could matrices, but let's instead view the plane as being the set of complex numbers; a rotation by an angle theta is accomplished by multiplication by u = exp(i theta). (The function f(z) = P + u (z - P) is the rotation around P.) So we are composing the functions R_k(z) = P_k + u ( z - P_k) = u z + (1-u) k By induction on m we find (R_m o ... o R_2 o R_1) (z) = u^m (z) + S_m where S_m = (1-u) m + u S_{m-1}, i.e. S_m = (1-u) ( m + u (m-1) + u^2 (m-2) + ... + u^m (0) ). = m - u - u^2 - ... - u^m = m - (u - u^{m+1})/(1 - u) In the problem we were given that theta = 2 pi / n , so u^n = 1, meaning (R_n o ... o R_2 o R_1) (z) = u^n (z) + S_n = z + n, a simple translation R(x,y) = (x+n, y). This motion is easily demonstrated for low n. B-5. It makes more sense to deal with the logs. We need to look at lim_{x->1-} lim_{N->\infty} sum_{n=0}^N x^n (log(1+x^{n+1}) - log(1+x^n)) = lim_{x->1-} lim_{N->\infty} ( sum_{n=1}^N (x^{n-1} - x^n) log(1+x^n) ) -log(2) + x^N log(1+x^{N+1}) For any x < 1, the last term tends to 0 as N->\infty, so we have only - log(2) + lim_{x->1-} (1/x - 1) sum_{n=1}^\infty x^n log(1+x^n) Now, we may estimate the infinite sum using bounds on the logarithm from its Taylor series; for example, we have log(1+x^n) > x^n - x^{2n}/2 but log(1+x^n) < x^n - x^{2n}/2 + x^{2n}/3 . From these we obtain inequalities on the sum: it lies between x^2/(1-x^2) - (1/2)(x^3/(1-x^3)) and x^2/(1-x^2) - (1/2)(x^3/(1-x^3)) + (1/3)(x^4/(1-x^4)), and we may obtain more bounds of this type. Multiplying in the additional factor (1/x - 1) (which is positive) gives bounds such as x^1/(1+x) - (1/2)(x^2/(1+x+x^2)) and x^1/(1+x) - (1/2)(x^2/(1+x+x^2)) + (1/3)(x^3/(1+x+x^2+x^3)) Applying these bounds to each x < 1 we find the limit to lie between 1/2 - (1/2)(1/3) and 1/2 - (1/2)(1/3) + (1/3)(1/4) and more generally it is alternately larger or smaller than a partial sum of the the absolutely convergent series (1/1)(1/2) - (1/2)(1/3) + (1/3)(1/4) - ... Carrying out this argument more generally to finite expansions of the Taylor series shows that the limit must equal this infinite sum. If we add 2( (1/2)(1/3) + (1/4)(1/5) + (1/6)(1/7) + ...) we obtain the famous telescoping series, which sums to 1. But in like manner we may recognize this addend as 2( (1/2) - (1/3) + (1/4) - (1/5) + ... ), which is 2 (1-log(2)). So the series in the last paragraph converges to 2 log(2) - 1. So I conclude that the logarithm of the original limit is log(2) - 1, and so the limit itself must be 2/e . B-6. No clue. It's a nice problem though -- sort of a teaser for the Twin Prime conjecture or something. (Let A = set of all primes.) For contrast, consider what happens when A = set of all squares (B = set of (almost) all composites), or A = an arithmetic progression (B is an ideal of Z), or A = powers of 2 (this B is indeed sparse). I look forward to a solution of this one. ============================================================================== [A-2.] From: Petr Lisonek To: rusin@vesuvius.math.niu.edu Subject: A-2 Date: Sat, 4 Dec 2004 22:07:28 -0800 (PST) Minor revision rec'd at: Date: Sat, 4 Dec 2004 22:35:21 -0800 (PST) For i=1,2 let alpha_i, beta_i, gamma_i denote the angle in T_i opposite side a_i, b_i, c_i, respectively. It is easy to prove by contradiction that (alpha_1 <= alpha_2) or (beta_1 <= beta_2) or (gamma_1 <= gamma_2). W.l.o.g. assume alpha_1 <= alpha_2. Since T_2 is acute, sin(alpha_1) <= sin(alpha_2) and area(T_1) = 1/2 b_1 c_1 sin(alpha_1) <= 1/2 b_2 c_2 sin(alpha_2) = area(T_2). From: Robin Chapman Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- [*SPOILERS*] Date: Mon, 06 Dec 2004 08:49:38 +0000 An alternative method: enlarging the second trinagle by a constant factor allows us to assume that a = a'. Draw both triangles on the same base: ABC and A'BC say with A and A' on the same side of BC. Draw the line L through A parallel to BC and the line L' perpendicalar to L at A. If the second triangle had larger area, A' would lie beyond L (opposite side of L to BC). Divide the "beyond" of L into two quadrants by L'. If A' is beyond L then b' > b if L is in one quadrant and c' > c in the other (here is where we use acuteness). From: baloglou@panix.com (George Baloglou) Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- Questions Date: 6 Dec 2004 18:23:38 -0500 Here is a solution that does not employ Heron's area formula: Let T_1 = ABC. At least one of the angles of T_2 has to be greater than or equal to one of the angles of ABC, say Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- Questions Date: Mon, 06 Dec 2004 17:36:29 -0600 Here's an even shorter solution: the area of T_2 is equal to all of a_2 b_2 sin(theta_2)/2 a_2 c_2 sin(phi_2)/2 b_2 c_2 sin(psi_2)/2 where theta_2, phi_2, psi_2 are the angles between the two sides which appear in the respective formulas. The same formulas work for T_1, with of course all the subscripts changed to 1. We are given that the lengths of the sides are all nonincreasing, and since the sum of the angles is constant one of them must not increase as well. Since the angles are all less than pi (here's where acute comes in) that means that the sine of that angle must not increase. Hence at least one of those expressions is the product of three terms which do not increase over the originals. From: Nuwan D de Silva To: rusin@vesuvius.math.niu.edu Subject: putnam Date: Tue, 07 Dec 2004 13:49:40 -0500 (EST) Name corrosponding angles of T1, T2 as A1, B1, C1 and A2, B2, C2 Then at least for one corrosponding pair of angles, Angle T2> Angle T1 (otherwise we have A1+B1+C1>A2+B2+C2 -contradiction). Say A2 > A1 , T2 is acute THrefore 0 < A1 < A2 < 90 Threfore sinA1 To: rusin@vesuvius.math.niu.edu Subject: 65 th Putnam exam Date: Sun, 05 Dec 2004 12:48:41 -0500 Let D_1 be tha angle between a_1 and b_1 in T_1 and D_2, the angle between a_2 and b_2 in T_2. We have A_1 = a_1b_1 Sin(D_1)/ 2 <= a_2b_2 Sin(D_2)/2 = A_2 (since we can suppose, WLOG, that D_1 <= D_2 and then, since T_2 is acute, D_1 <= D_2 <= PI/2) From: "Ignacio Larrosa Caņestro" Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- [*SPOILERS*] (A2) Date: Wed, 8 Dec 2004 12:22:57 +0100 The area can be computed as S = (1/2)b*c*sin(A). If you shorten the side a, mantaining b and c, you decrease the angle A. If A isn't obtuse, sin(A) decrease also, so also the area decrease. If T1 is also non-obtuse, we can go from T2 to T1 shortening sides opposites to non-obtuse angles, perhaps in more that three steps, changing the side shortening if any of the other angles became stright. Then S(T1) < S(T2) If T1 is obtuse, angle A1 is obtuse by example, we take T1' with sides b1 an c1 equals to the T1 ones, and angle A1' = pi - A1. Then S(T1) = S(T1') < S(T2). ============================================================================== [A-4.] From: Robin Chapman Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- [*SPOILERS*] Date: Mon, 06 Dec 2004 08:49:38 +0000 I got n! x_1 x_2 ... x_n = sum_T (-1)^{n-|T|}(S(T))^n eschewing coefficient -1. :-) From: retsop_swen@yahoo.com Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- [*SPOILERS*] Date: 6 Dec 2004 20:38:43 -0800 If you take the finite differences with spacing x1, then x2, then x3, ... then xn, applied to the polynomial T^n, you get a constant, namely n! * (x1 x2 ... xn). The x1, x2, ... factors are maybe clearer to see if you use the finite difference quotient operators (f(T) - f(T-xi)) / xi which have the same behavior on highest degree terms as taking a derivative. From: Mitch Harris Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- [*SPOILERS*] A4 Date: Tue, 07 Dec 2004 15:40:07 +0100 > I didn't take advantage of the opportunity to use 0 as a coefficient! And Robin's doesn't take advantage of -1 for a_{ij}. Notice that you don't need 2^n terms. For n=2k, (-x - y + z ...)^{2k} = (x + y - z ...)^{2k} For n=2k+1, (-x - y + z ...)^{2k+1} = -(x + y - z ...)^{2k+1} For example, n = 3: xyz = 1/24((x+y+z)^3 -(-x+y+z)^3 -(x-y+z)^3 -(x+y-z)^3) How about in less than 2^{n-1} terms? Using 1,0, and -1? Reminds me of the game played in Strassen's faster than n^3 matrix multiplication algorithm. ============================================================================== [A-5.] From: retsop_swen@yahoo.com Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- [*SPOILERS*] Date: 6 Dec 2004 20:38:43 -0800 The expected number of components is >= the expected number of 1-point components = sum (over all points P in the rectangle) of the probability that P is isolated. The probability that any given point is isolated is 2 * (1/2)^(number of its neighbors) which is at least 1/8. From: "D. J. Bernstein" Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- [*SPOILERS*] Date: Tue, 7 Dec 2004 05:05:48 +0000 (UTC) retsop_swen@yahoo.com wrote: > The probability that any given point is isolated is > 2 * (1/2)^(number of its neighbors) which is at least 1/8. No, only 1/16. More generally, say a connected region contains c points and touches t additional points. There's probability 1/2^(c+t) that the region is all red and the additional points are all black; and disjoint probability 1/2^(c+t) that the region is all black and the additional points are all red; for a total probability of 2/2^(c+t) that the region is maximal monochromatic. For example, c=1 usually means t=4 and 2/2^(c+t) = 1/16. The problem is to prove that the sum of 1/2^(c+t-1), over all connected regions, is at least mn/8. Single-point regions get you to only about mn/16; it's certainly not that easy! From: "epurdy" Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- [*SPOILERS*] Date: 6 Dec 2004 21:27:18 -0800 > The expected number of components is >= the expected number of 1-point > components = sum (over all points P in the rectangle) of the > probability > that P is isolated. The probability that any given point is isolated > is > 2 * (1/2)^(number of its neighbors) which is at least 1/8. Actually, the probability is only 1/16: 1/32 that the point is red and its neighbors are black and 1/32 that the point is black and its neighbors are red. From: "D. J. Bernstein" Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- Questions Date: Mon, 6 Dec 2004 04:33:50 +0000 (UTC) George Baloglou wrote: > How about this: show by induction on n that the expected number of *added* > CMCs (connected monochromatic components) as we add a new row exceeds n/8; Adding the mth row adds, on average, (1+[m=1])(n+2+[n=1])/8 new single-square regions. This is easy to prove. The problem is that adding the mth row can also _lose_ regions. I haven't found a weighting of regions that makes the average easy upper bound for the gain outweigh the average easy upper bound for the loss. This is the only problem that I haven't solved yet. I've resorted to computer simulations to get an idea of what's going on. The limiting ratio for large m,n is clearly very close to 1/8. Maybe very slightly larger (is 1/8 the right answer for regions without holes?), which would turn this into a finite computation---but even after adding up 1/16 for one-square regions, 1/64 for two-square regions, 5/512 for three-square regions, and so on up to 20-square regions, I'm still below 1/8. From: "D. J. Bernstein" Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- Questions Date: Mon, 6 Dec 2004 05:56:35 +0000 (UTC) Attach a random row to the bottom of the row 10101010101... The first row has n regions. The first two rows together have, on average, about n regions---certainly not (9/8)n. So it's simply not true that adding a random row to a fixed matrix produces an expected (1/8)n increase in the number of regions. George Baloglou wrote: > [Of course if you can get a region where the expected number > is indeed below 7mn/48 then you will have proved the incorrectness of > my argument without going into its specifics!] Here are the number of regions in twenty random 192x192 colorings: 4979, 5068, 5012, 5073, 5038, 5065, 4941, 5141, 4905, 4960, 4944, 4994, 4933, 4883, 5060, 4917, 4976, 4945, 4977, 5047. You think the average is above 5376? It isn't clear to me exactly which probability space you have in mind, so I can't comment specifically on what you did wrong. From: "D. J. Bernstein" Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- Questions Date: Mon, 6 Dec 2004 18:17:53 +0000 (UTC) G. A. Edgar wrote: > Is it convenient in your simulation to get the information on what the > sizes of the regions are? Yes. It's also easy to compute the (proven) limiting ratios for every small region size. Unfortunately, as I mentioned earlier in the thread, the total is still below 1/8 even if you include region sizes up to 20. From: andrewbadr@gmail.com Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- Questions Date: 6 Dec 2004 23:30:18 -0800 We seem to agree on all this: If on an infinite grid, we can show that the average size S of a connected monochromatic region (CMR) is 8 or smaller, we're done. Cutting out a finite portion will decrease S and thus increase the expected number of regions N to above m*n/8. (A=m*n=S*N, so S<8 implies N = A/S > m*n/8). To find N is to find the sum_{n=1}^{+inf} of n*p(n) where p(n) is the probability of some randomly chosen square in an infinite grid being in a CMR of size n. This is where I don't understand your calculations: I might have just totally misinterpreted your posts, but it sounds like you've found p(1)=1/16 and p(2)=1/64 and sum_{n=1}^20 p(n) < 1/8. FIRST Q: I found p(2)=1/16. 1/64 for 7 square to work out the way we want: a given neighbor of our randomly chosen square, and their 6 neighbors. But there are 4 possible neighbors to choose from, giving 4/64=1/16. SECOND Q: If your total for the first 20 probabilities is less than 1/8, then rest of the sum for N must be at least 21*7/8, which gives N > 8, violating the problem. In conclusion, I'm increasingly convinced that I simply misinterpreted what you're doing, but hopefully I did so in a useful way. From: andrewbadr@gmail.com Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- Questions Date: 7 Dec 2004 02:31:08 -0800 A correction to my above post: I found p(2)=1/32. 1/128 for 7 squares to work out the way we want: a given neighbor of our randomly chosen square, and their 6 neighbors. But there are 4 possible neighbors to choose from, giving 4/128=1/32. From: Alexander Ryba To: rusin@math.niu.edu Subject: putnam A5 Date: Mon, 6 Dec 2004 11:39:45 -0500 (EST) Here's a sketch for A5 which I haven't seen on the sci.math solutions yet --- ------------------------------------------ We use induction on the number of rows (m say) of the rectangle. Adding an (m+1)st row to an m x n rectangle adds some new regions: these are 1 x r rectangles contained within the (m+1)st row. However adding the (m+1)st row also subtracts some regions from the m x n part, because the squares of the (m+1)st row can link up two previously unlinked regions of the upper m x n part. (And of course some squares of the last row are simply absorbed into existing regions of the upper part.) We will estimate both contributions and show that the expected value of regions added minus regions fused is at least n/8. (This is enough to complete the induction --- the base case being a 0 x n rectangle.) First we estimate added regions: -------------------------------- A block of r squares of the last row is a new connected region if: 1. All squares are color C 2. The two (or fewer) adjacent squares of the last row are not C 3. The r squares immediately it are not C. The probability of all this is at least 2/(2^(2r+2)). (The numerator is from the two choices for C. Blocks at the end of the last row have fewer neighbors and give a slightly higher probability.) Thus the expected number of added new regions is at least: n/2^3 + (n - 1)/2^5 + (n - 2)/2^7 + (n - 3)/2^9 + ... + 1/2^(2n+1) Now we estimate fused regions from the m x n rectangle: ------------------------------------------------------- A 1 x r rectangle of the last row fuses two regions X and Y of the m x n rectangle if it is monochromatic (of color C) and if it begins under a color C square of X and ends under a color C square of Y. Note also that r >= 3. However if some other square right on top of the 1 x r rectangle has color C and belongs to the region Z, then the 1 x r rectangle shows that X fuses with Z and Z fuses with Y. Moreover, we could obtain the same information with the two subrectangles that fuse X to Z and Z to Y. Thus, the number of fused regions from the m x n rectangle is bounded by the number of 1 x r rectangles of the last row that are monochromatic of color C and are immediately under a rectangle whose end points have color C, but whose non-end points have color not(C). The probability that a 1xr rectangle of the last row has these properties is: 2/ (2^(2r)). Thus the expected number of regions of the (m x n) rectangle that get fused is: (n - 2)/2^5 + (n-3)/2^7 + ... + 1/2^(2n - 1). (We start with (n - 2) 1x3 rectangles, then (n - 3) 1x4 rectangles and so on.) Now, compare added regions with subtracted regions --------------------------------------------------- In this second sum the term (n - i)/(2^(2i + 1)) is clearly bounded by a term (n - i + 1)/(2^(2i + 1)) in the first sum. Thus the difference between the two sums that we have calculated is at least n/2^3 (which is the first term of the first sum and has no corresponding term of the second sum). From: elkies@math.harvard.edu (Noam Elkies) Newsgroups: sci.math Subject: *SPOILER*: A-5 on Putnam 2004 Date: Tue, 7 Dec 2004 16:54:54 +0000 (UTC) My solution was: Build up the chessboard in lexicographic order starting from a 1*1 square. This square always has 1>1/8 connected monochromatic region (CMR). When we start a new row, we gain a new CMR with probability 1/2. When we add a new square to an already started row, we gain a new CMR with probability 1/4, and lose one with probability at most 1/8. (*) Hence the expected number of new CMR's goes up by at least 1/8 at each step, for a total of more than mn/8. (*) Suppose without loss of generality that the new square is red. The only way that adding this square loses a region is its neighbors are red squares that were not previously connected. Thus the other common neighbor of these two squares was black: ????????????? ****RR??????? ****BR******* ************* ************* and this happens with probability 1/8. Unless the new square is on the second row or column, there are other ways that the two squares could be connected around the black square, so the actual probability is usually a bit under 1/8. ======= Alison Miller, a first-year student here suggested an alternative approach: use the Euler characteristic formula! Consider the graph whose faces are CMR's and whose edges are unit edges separating two adjacent CMR's (or one CMR from the complement of the rectangle). Some vertices will have degree only 2, but that doesn't affect Euler's formula. Some CMR's will not be simply connected; this *does* affect Euler's formula, but only in our favor. Since the complement of the m*n rectangle doesn't count as a CMR, Euler's formula takes the form #(vertices) - #(edges) + #(CMR's) = 1 + H >= 1 where H is the total number of holes in CMR's that are not simply connected. Now take expected values: Vertices: each of the (m+1)(n+1) vertices of a checkerboard square is a vertex unless it is an internal vertex surrounded by four squares assigned the same color. Hence the expected number of vertices is (m+1)(n+1) - (m-1)(n-1)/8. Edges: each of the 2(m+n) perimeter edges is an edge of our graph. Each of the interior 2mn-(m+n) edges is an edge if and only if it separates two squares of opposite colors, which happens with probability 1/2. Hence the expected number of edges is mn + 3(m+n)/2. It follows that the expected number of CMR's is at least #(edges) - #(vertices) + 1 = (mn + 3(m+n)/2) - ((m+1)(n+1) - (m-1)(n-1)/8) + 1 = mn/8 + 3(m+n)/8 + 1/8 > mn/8, Q.E.D. ======= The two solutions are more closely related than they might seem at first. Both solutions relate the excess over mn/8 + O(m+n) with the total number of holes: if in my solution a new (say) red square does not lose a CMR even though it connects two red squares that did not previously have a common red neighbor, then they were already connected in a CMR with a hole. --Noam D. Elkies From: retsop_swen@yahoo.com Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- [*SPOILERS*] Date: 8 Dec 2004 17:20:58 -0800 D. J. Bernstein wrote: > retsop_swen@yahoo.com wrote: > > The probability that any given point is isolated is > > 2 * (1/2)^(number of its neighbors) which is at least 1/8. > > No, only 1/16. You're right, it's not that easy. Thanks. However, I think this type of approach, adding a local expression over all points, can be made to work. ------------------------------------------------------------ Solution #1: Compute the winding number of each Connected Monochromatic Region, and sum over all regions. The answer is the number of CMR, if all are simply connected. (For multiply connected CMR, see below). Winding number is a local integral. It is the sum over all (m+1)(n+1) corners of squares in the diagram, of local winding number contributions that are easy to compute: a. Corners of the m x n rectangle contribute 1/4 each = 1 b. Non-corner points on the boundary contribute winding number 1/2 if the squares that meet there have opposite color = expected winding of 1/4 per point. c. Interior points P of the rectangle contribute nothing unless the 2x2 square centered at P is checkerboard-colored with 2 squares of each color (probability of 1/8) and contributes winding of 4*(1/4)=1 in that case. Expected winding = 1/8 per point. So all (m+1)(n+1) points contribute an expectation of >= 1/8, which is > mn/8. We are done provided we can address the issue of multiply connected CMR: Simply connected CMR's contribute 1. Multiply connected CMR will contribute 1 only if they are maximal; the contribution of inner regions (and their inner-inner regions, etc) will cancel out. Closed curves which are boundary components of two CMR's will make a net contribution of zero, because they will be traversed in both directions. So the calculation shows the slightly stronger result, that the expected number of "maximal CMR", i.e. the number of closed curves which are boundary components of just one CMR, in this sense) is mn/8 + 3/8(m+n) + 1 > mn/8. ------------------------------------------------------------- Solution #2: Use Pick's theorem to add up the areas of all CMR's. Pick's formula for a polygon with h holes is Area = # Interior pts + 1/2 # Boundary pts - (1 - # holes). Adding this over all CMRs, mn = # Int + 1/2 # Boundary - # CMR + [something >= 0 from holes] Expected # CMR >= E[Int] + 1/2 E[Boundary] - mn The rest is an easy calculation. Note that boundary points are counted with multiplicity 2 (for a given CMR) if two corners of that CMR meet there, as in a 3x3 square with the center and one corner removed; and that a given point must be counted separately for each CMR whose boundary contains it. Each of the (m-1)(n-1) points inside the rectangle is: - an interior point if the 2x2 square around it is monochromatic, probability = 1/8. - a boundary point of multiplicity 4 if its 2x2 square is checkerboard-colored (probability 1/8)= expectation 2/8. - a boundary point of multiplicity 2 if its 2x2 square is of any other type (probability 6/8) = expectation 6/8. This gives an expectation of 1/8 + 2/8 + 6/8 = 9/8 per point, or 9/8 (m-1)(n-1). Corners of the rectangle are boundary points of multiplicity 1, with probability 1, for an expectation of 1/2 per point = 2. The (2m+2n - 4) external points of the rectangle are boundary points in the sense of Pick's theorem, with multiplicity 1 if two equal-colored squares meet there (prob 1/2) and multiplicity 2 otherwise (prob 1/2), for an expectation of 3/2 per point = 3 (m+n-2) Thus: Expected # CMR >= 9/8 (m-1)(n-1) + 2 + 3(m+n-2) - mn = mn/8 + 15/8 (m+n) - 23/8 > mn/8. I'm puzzled why this doesn't give the exact same answer as Solution #1, as it seems to be calculating the same geometric/topological quantity. But, even in case of a calculation error, we know that the approach using Pick's theorem works because the expectation per each of the (m+1)(n+1) points is at least 9/8, which still exceeds 1/8 after subtracting 1 from mn of the points. > > More generally, say a connected region contains c points and touches t > additional points. There's probability 1/2^(c+t) that the region is all > red and the additional points are all black; and disjoint probability > 1/2^(c+t) that the region is all black and the additional points are all > red; for a total probability of 2/2^(c+t) that the region is maximal > monochromatic. For example, c=1 usually means t=4 and 2/2^(c+t) = 1/16. > > The problem is to prove that the sum of 1/2^(c+t-1), over all connected > regions, is at least mn/8. That's interesting. Is there a way to use that to write an infinite series for the true proportion of CMR per area (for an infinite rectangle). It should be higher than 1/8. From: "Jim Ferry" Newsgroups: sci.math Subject: Re: *SPOILER*: A-5 on Putnam 2004 Date: 9 Dec 2004 12:04:51 -0800 >> Show that the expected number of connected monochromatic >> regions is greater than m n / 8 . > I set out to calculate a lower bound for the expected number of > CMRs per unit area on an infinite grid, the reasoning being that > a MxN boundary could only help (divide) and never unite. If I can > get the lower bound to 1/8, I have shown what the problem asks. Let r be the expected number of CMRs per unit area. Noam Elkies posted a nice proof that r > 1/8 for any rectangle. For an infinite grid, Robert Ziff has found the numerical result r = 0.13154. See http://www.mathsoft.com/mathresources/constants/discretestructures/article/0,,2246,00.html (Ziff's result, KS(1/2) = 0.065770, is based on clusters of one color only.) Apparently, no closed form solution is known for the infinite grid. I have found exact results for semi-infinite grids: for an n by infinity strip and for an n by infinity cylinder. Here are the exact results for n <= 5: n r(strip) r(cylinder) * 1 1 1 - - * 2 2 * 5 5 2 -- -- * 16 16 * 169 19 3 --- -- * 672 96 * 39089 421 4 ------ ---- * 176640 2560 * 89351789444611689 68793 5 ------------------ ------ * 439583056742725120 458240 I've computed these up to n=7 for the strip, and n=9 for the cylinder, but they grow unwieldy. Here are numerical values: n r(strip) r(cylinder) 1 0.50000000000000000000 0.50000000000000000000 2 0.31250000000000000000 0.31250000000000000000 3 0.25148809523809523810 0.19791666666666666667 4 0.22129189311594202899 0.16445312500000000000 5 0.20326486217804029700 0.15012438896648044693 6 0.19127901060670776462 0.14295086597958005559 7 0.18273060344786138290 0.13894468047611946140 8 0.13653882028358344362 9 0.13501624475917424566 These values are upper bounds, so they are not useful for the Putnam problem. It is interesting that Noam Elkies's simple argument yields such a tight lower bound on r for the infinite grid: 0.125 < 0.13154. -Jim Ferry Metron, Inc. f rr @m tsc .c m e y e i o From: Noam D. Elkies Newsgroups: sci.math Subject: Re: *SPOILER*: A-5 on Putnam 2004 Date: Sun, 12 Dec 2004 03:37:46 +0000 (UTC) > Apparently, no closed form solution is known for the infinite grid. > [...] > It is interesting that Noam Elkies's simple argument yields > such a tight lower bound on r for the infinite grid: 0.125 < 0.13154. The argument I gave suggests that in fact 1/8 is quite close to the correct answer. More precisely, let p be the probability that the two R squares land in the same component when the * squares in this half-infinite grid: ******R ******BR***** ... ************* ... ************* ************* ... are each independently filled with R or B, each having probability 1/2. Then it follows easily from my argument that the limit for large m,n of the ratio of the number of monochromatic clusters to the area mn equals (1+p)/8. Now while p is clearly positive, it can't be very large: already the probability that each R is connected to a square in the row below it is 2/9, the product of 1/3 for the top R times 2/3 for the bottom one. This gives a crude upper bound of 11/72=0.1527777... on (1+p)/8. For a lower bound, the shortest path between the two R's has length 5, giving p>1/32, which is already enough to push (1+p)/8 above 0.1289; if I did this right then we get p>173/4096 by using also the paths of length 7 or 9, so (1+p)/8 > 0.1302795... which is only a bit below the value reported by Robert Ziff in the URL cited above. NDE P.S. I'm sure that I'm not the first to find this argument -- surely the proposer of this Putnam problem, and/or the researchers in this kind of percolation theory, were aware of this too. ============================================================================== [A-6.] From: "Junping Shi" To: Subject: putnam a6 Date: Tue, 7 Dec 2004 14:09:57 -0500 Thanks for your answer of Putnam on your website. Your proof of A6 is really smart, and I just want you to know that another way of solving A6 is to use Fourier series: \sum_{i,j} C(i,j) w_i(x) w_j(y) then just with normal calculation, A6 cab be proved since eventually the inequality becomes \sum_{i} C(i,1)+\sum_{j} C(1,j) \le C(1,1)+\sum_{i,j} C(i,j) The proof probably is not elegant as yours, but it could be generalized in several ways. [I responded to say this:] Actually that's a very nice proof, although it is very problematic to say what it means that this arbitrary continuous function f is "equal" to its Fourier series. But that's a very natural way to proceed. I hope you don't mind if I add your mail to my web pages about the test. [In response I got this message, Date: Tue, 7 Dec 2004 14:46:44 -0500] I don't mind if you want to add my mail to your web pages. For continuous function "f", the Fourier series of "f" will converge to "f" if "f" is continuous except at the end points. But for the integral, the values of "f" at a finite many points are not important. In fact, the inequality holds for any function "f" which is square integrable, i.e. belonging to L^2 space, which include the class of continuous functions. Junping From: djr To: me Subject: How did I arrive at my solution to A-6? Date: none [For future reference I thought I'd save my notes on A6. During the exam I considered the case n=m=2 in the argument below, then realized that for general n,m I would have to use the fact that sum(r_i)=1. It was only while writing this up for posting that I realized I could turn the _analogy_ of a set of measure zero in R^4 into a technique for solving the problem. Here is what I was going to post. --djr] It suffices to prove this for simple functions and take a limit, so let us assume we have partitioned the edges into intervals of length r1, r2, ..., r_n and s1, s2, ..., s_m respectively, and that f takes the value a_{ij} on the (i,j)-th rectangle. Subtracting the left side from the right, we see that this is what we must prove positive: ( \sum_i \sum_j r_i s_j a_{ij} )^2 + \sum_i \sum_j r_i s_j ( a_{ij} )^2 - \sum_i r_i ( \sum_j s_j a_{ij} )^2 - \sum_j s_j ( \sum_i r_i a_{ij} )^2 This expression is a polynomial in the r_i and s_j which includes quadratic and linear terms. We may make them all quadratic by replacing r_i by r_i * 1 = r_i * (r1 + r2 + ... + r_n) and similarly for the s_j. Then in general the coefficient of r_i r_k s_j s_l (which is positive) will be 2 a_{ij} a_{kl} + 2 a_{il} a_{kj} + a_{ij}^2 + a_{il}^2 + a_{kj}^2 + a_{kl}^2 - 2 a_{ij} a_{il} - 2 a_{kj} a_{kl} - 2 a_{ij} a_{kj} - 2 a_{il} a_{kl} = (a_{ij} + a_{kl} - a_{il} - a{kj})^2 which is also positive. The sum of all these terms is of course then positive too. I am glossing over the special cases in which i=k or j=l which are left to the reader (although technically I guess in the limit they [...and here I was going to write something about being a set of measure zero; then asked myself, "where?" and I realized this was all about measures, sums, and integrals in [0,1]^4 . I stopped mid-sentence and went back to scratch paper!] From: anonymous@mathforum.org Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- [*SPOILERS*] Date: Thu, 9 Dec 2004 01:04:48 +0000 (UTC) Here's a less opaque proof. Let me write suggestively: int{x=0 to 1} f(x,y) dx = _x, similar for _y and int{x=0 to 1} int{y=0 to 1} dy = _xy. Also, I'll denote Dx(f) = f - _x, similar for Dy. Note that the _x = 0. We can write the function f as: f = _xy + _y + _x + Dx(Dy(f)). Note that <.>_x, <.>_y, Dx, and Dy all commute pairwise, so the above expression is unique and well defined. What we've done here is present f as a sum of its mean and fluctuations about the mean. The inequality that needs to be proven in this notation is: _xy + _xy^2 - <_x^2>_y - <_y^2>_x >= 0. Write f using the above formula, expand and simplify. The above inequality becomes equivalent to <(DxDy(f))^2>_xy >= 0, which is obvious. How I came up with it was that I tried f(x,y) = X(x)Y(y), then evaluating the left hand side of the desired inequality gives (-^2)(-^2) >= 0. After staring at this for a bit I realized that for both X and Y this is just the statement that var(X) >= 0 and var(Y)^2 >= 0, which is proved by writing X = + (X-) and expanding the definition of var(X) = <(X-)^2>. Then it was a simple matter to generalize this to two integration variables. The upside of this proof is that it should be easy to generalize to more than just two integration variables. And that it's not important that the integration is over a unit square, any rectangular region with total weight and weight along each coordinate section equal 1. ============================================================================== [B-1.] From: Bill Dubuque Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- [*SPOILERS*] Date: 05 Dec 2004 05:39:48 -0500 You needn't essentially reprove the rational root test as you do. Instead you can simply invoke it in an inductive manner as follows. n n-1 n-2 n-3 Write P(X) = a X + b X + c X + d X + ... n-2 n-3 Then r is a root of F(X) = ((ar + b)r + c) X + d X + ... By induction (ar + b)r is in Z, hence so is the leading coef of F. So the rational root test applies, yielding the leading coef of F. is a denominator for the root r, i.e. ((ar + b)r + c) r in Z. QED --Bill Dubuque ============================================================================== [B-2.] From: Robin Chapman Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- [*SPOILERS*] Date: Mon, 06 Dec 2004 08:49:38 +0000 One of the terms in the binomial expansion of (m+n)^{m+n} is (m+n choose m) m^m n^n so that (m+n)^{m+n} > (m+n choose m) m^m n^n From: "James Pirk" Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- Questions Date: 5 Dec 2004 11:50:39 -0800 is there an easy, direct (no frills) proof of b-2? something like (m+n)! (m+n)^{m+n} ------ < ------------- m!n! m^m n^n iff C(m+n,m) < m^{-m}n^{-n} \sum_{k=0}^{m+n} C(m+n,k)m^k n^{m+n-k} iff C(m+n,m) < \sum_{k=0}^{m+n} C(m+n,k)m^{k-m} n^{m-k} but in the above summation we see there is a term of the form C(m+n,m)m^0 n^0 (when k=m), so that means that term and left hand side cancel. So you have 0 < [sum of positive things] . of course this seems to easy for a solution to a putnam problem. where is my error? i havent really looked at it in depth. From: borchers@nmt.edu (Brian Borchers) Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- Questions Date: 5 Dec 2004 16:31:01 -0800 > is there an easy, direct (no frills) proof of b-2? For positive integers m and n, and any real numbers a and b, by the binomial theorem, (a+b)^(m+n)= sum(C(m+n,k)*a^(k)*b^(m+n-k),k=0..(m+n)). For positive integers a and b, each term in this sum is a positive integer. Thus we can consider the k=m term and get that (a+b)^(m+n) > C(m+n,m)*a^m*b^n. In particular, if we let a=m, b=n, we get that (m+n)^(m+n) > (m+n)!*m^m*n^n/(m!*n!). Rearranging the inequality a bit gives the desired result (m+n)! m!*n! ----------- < ---------. (m+n)^(m+n) m^m*n^n From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Putnam B-2 (Was: Re: Putnam Exam 2004 -- Questions) Date: 6 Dec 2004 06:20:22 GMT >For positive integers m and n, and any real numbers a and b, by the >binomial theorem, This is really the same proof I gave. C'mon, doesn't _everybody_ think in terms of maps between finite sets? :-) > (a+b)^(m+n)= sum(C(m+n,k)*a^(k)*b^(m+n-k),k=0..(m+n)). This just counts the maps from m+n to a+b in groups according to the number k of elements in the domain which are sent to a and the number (m+n)-k which are sent to b. That's what I did, and then I picked out the special case k = m, same as you: >For positive integers a and b, each term in this sum is a positive >integer. Thus we can consider the k=m term and get that > > (a+b)^(m+n) > C(m+n,m)*a^m*b^n. But you do get Brownie Points for generalizing beyond the requested result to get (a+b)^{m+n} / (m+n)! > a^m/m! * b^n/n! for arbitrary _positive real numbers_ a,b ; technically my combinatorial proof only covers _positive integers_ a and b. Is (a+b)^{m+n} / (m+n)! > a^m/m! * b^n/n! true for all positive a,b,m,n when "!" is interpreted with the Gamma function? From: retsop_swen@yahoo.com Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- [*SPOILERS*] Date: 6 Dec 2004 20:38:43 -0800 Any solution by estimating the integral on [0,1] of x^m (1-x)^n (Euler beta integral)? From: Nuwan D de Silva Subject: putnam To: rusin@vesuvius.math.niu.edu Date: Tue, 07 Dec 2004 13:49:40 -0500 (EST) [(m+n)^(m+n)]/ (m+n)! is the coefficient of x^(m+n) in the power series expansion of e^(m+n)x e^mx . e^nx = e^ (m+n)x multiplying (m^m)/m! (i.e the coefficient of x^m in the expansion of e^mx) with (n^n)/n! (the coefficient of x^n in the expansion of e^nx) is only one term of the coefficient of x^(m+n) in the product e^mx. e^nx Threfore [(m^m)/m!] [(n^n)/n!] < {(m+n)^(m+n)/ (m+n)!} the ineqality follows. From: mburr@eecs.tufts.edu To: rusin@math.niu.edu Subject: Another solution to B2 Date: Sun, 5 Dec 2004 11:54:23 -0500 There's another solution to B2 that is somewhat simpler (but not as slick) 1) Clear fractions so that we get the following (m+n)!*m^m*n^n<(m+n)^{m+n}*m!*n! 2) If we use the binomial formula, then the coefficient of m^m*n^n in (m+n)^{m+n} is m+n choose m, so then the above formula can be written (m+n)!*m^m*n^n Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- Questions Date: 17 Jan 2005 06:53:56 GMT My first thought is that a rotation about a point is identical to a translation followed by a rotation through the same angle about some different point. Hence all the 2pi/n rotations about various points can be collapsed into a single rotation through 2pi (i.e. identity), followed by a translation. So it reduces to finding the single translation, which will depend upon the points acting as the centers of rotation. A quick mental check with n=2 and n=3 indicates that the translation will map (0,0) to (n,0). Sure enough, there is an elegant way to show that the overall transformation will send (0,0) to (n,0). Looking at which point ends up at (2,0) after the first rotation for n=3 or n=4, it looks a lot like the corner of an equilateral triangle or square. That prodded my intuition... Consider a regular n-gon sitting with one vertex at (0,0), an adjacent vertex at (1,0), and the body of the n-gon below the x-axis. Then each 2pi/n rotation through (k,0) will "roll" the polygon along the x-axis. After n such rolls, the original (0,0) vertex will be at (n,0). Of course, at this point I felt like an idiot for having to go through all the previous reasoning to arrive at the painfully obvious answer that I should have seen all along. An excellent mathematical problem, From: Robin Chapman Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- Questions Date: Mon, 17 Jan 2005 09:09:35 +0000 The slick way of doing problems with rotations is to work in the complex plane where anticlockwise rotation with centre a through angle t is z |--> exp(it)(z - a) + a. Here the rotation R_j is z |--> u(z - j) + j where u = exp(2 pi i/n). The composition of the R_i is thus z |--> u( .... u(u(u(z-1) - 1) -1 ) .... - 1) + n = u^n z - u^{n-1} - u^{n-2} - ... - u - 1 + n = z + n. ============================================================================== [B-5.] From: The World Wide Wade Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- [*SPOILERS*] Date: Mon, 06 Dec 2004 14:04:47 -0800 Or: Let A_n(x) = (x-1)x^n/(1+x^n); the nth term in the product is (1 + A_n(x))^(x^n). The log of the product is sum (n=0,oo) x^n*ln(1 + A_n(x)) (1). Now ln(1+y) = y + O(y^2) as y -> 0, and each |A_n(x)| <= 1-x. So (1) can be written as sum (n=0,oo) x^n*[A_n(x) + O((x-1)^2)] (2). Because sum x^n = 1/(1-x), we can ignore the O((x-1)^2) in (2). Now x^n*A_n(x) = (x-1)x^(2n)/(1+x^n) = (x-1)*(x^(2n) - x^(3n) + x^(4n) - ...) >= (x-1)*(x^(2n) - x^(3n) + x^(4n) - x^(5n) + x^(6n)), using standard alternating series ideas, and where we've stopped at 6 just to illustrate. Summing on n, a lower bound for our sum is (x-1)*[1/(1-x^2) - 1/(1-x^3) + ... + 1/(1-x^6)]. Well now take the limit as x->1- of the last expression using (blush) L'Hospital. You get - 1/2 + 1/3 - ... - 1/6. It follows that the lower limit of our sum is >= - 1/2 + 1/3 - ... - 1/6. And of course we could have stopped at any even number of terms. So the lower limit is >= - 1/2 + 1/3 - 1/4 + ... = ln(2/e). Same idea (looking at any odd number of terms) shows the upper limit is <= ln(2/e). So the limit of the sum in question is ln(2/e); therefore the limit of the original product is 2/e. ============================================================================== [B-6.] From: "Paul Pollack" Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- B-6 Date: 6 Dec 2004 23:20:01 -0800 NOTE: In the proof below I diverge from the notation above in that I use B to denote the entire difference set A-A. But b_1 < b_2 < ... still denotes only the positive elements of B. PROOF: We are to prove that if A has positive upper density (limsup N(x)/x > 0), then b_{i+1} - b_i is bounded. Suppose this were false. We choose a near-largest counterexample (by "counterexample" I mean set A of positive upper density for which b_{i+1}-b_i is unbounded). Precisely, we let delta_0 > 0 be the supremum of the set of upper densities of counterexamples A. Choose a counterexample A with upper density delta > 3*delta_0/4. We take two cases: 1) For some positive integer m, the sets A and A+m are disjoint. In this case, A' := A U (A+m) has upper density 2*delta > 3*delta_0/2 > delta_0, hence A' is not a counterexample. Since A' is not a counterexample, the gaps between the consecutive positive elements of B':= A'-A' = B U (B+m) U (B-m) are bounded. Since B' contains arbitrarily large positive elements, it follows that every positive integer is at a bounded distance from an element of B'. But if every positive integer is within C of an element of B', then every positive integer is within C':=C+m of an element of B. It follows that every gap b_{i+1} - b_i is smaller than 2C'+2 (otherwise b_i + C'+1 is more than C' away from any element of B). This contradicts that A is a counterexample. 2) A and A+m intersect for every positive integer m. Then for every positive integer m, one can find an element a in the intersection of A and (A+m). Writing a = a' + m with a' also in A, we have m = a-a'. So B contains *every* positive integer, so the gaps between consecutive positive elements of B are (quite) bounded. Again, this is a contradiction. Hope this helps, Paul From: retsop_swen@yahoo.com Newsgroups: sci.math Subject: Re: Putnam Exam 2004 -- [*SPOILERS*] Date: 7 Dec 2004 14:44:00 -0800 1. Let T be the complement of B = {t : A is disjoint from A + t}. 2. If we can find n disjoint translates of A for all n, we are done (as A then has upper density <= 1/n for each n). 3. But that's easy because T contains long intervals of consecutive integers (its complement, B, has unbounded gaps): A, A + t1, A + t2, A + t3, ... disjoint means that the t's and their pairwise (absolute) differences are all in T, One can arrange this by taking t_n to be the last element in an interval in T of length greater than t_(n-1). ==============================================================================