Some answers to the 2003 Putnam exam. For more information about the exam, and for the statements of the questions, see http://www.math.niu.edu/~rusin/problems-math/ where (eventually) several formats will be available. Shown first is my post to sci.math, containing answers for the easy ones (and some commentary). I have flagged the most notable errors, which were addressed in later messages. Other posts and email have been dissected and attached below in order of the problems (scan for "A1", "A2", etc.) I have to say that some of the solutions presented by others are strinkingly simple and elegant! -- djr ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Putnam 2003 -- SOME SPOILERS Date: 7 Dec 2003 19:09:50 GMT Here are some answers to this year's Putnam questions. Suffering the ravages of old age, perhaps, I didn't finish as many as I usually do. Maybe the questions were a bit harder this year; certainly quite a few of them caused me to spin my wheels pursuing the wrong "usual trick" for too long. I have no answers here for: A2, A4 and A5 (probably not hard), and B6. My answer for A6 clearly misses some pretty idea. Hmm, maybe I just wasn't really awake for the morning session! Questions appeared in a previous post. A1 Let m be the number of summands equal to a_1 ; the other k-m (possibly zero) summands will be equal to (a_1)+1, and so the sum will be n = m a_1 + (k-m) (a_1 + 1) = k a_1 + (k-m). Since 0 <= k-m < k, this equation precisely represents the division algorithm with divisor k, that is, there is precisely one such pair ( a_1 , m ) associated to each value of k. So the number of such representations is precisely the number of possible summands, which is n. A2 No clue. The question can be interpreted as: "Show that the aritmetic mean of the geometric means is no bigger than the geometric mean of the arithmetic means," which is a nice question. A3 Write x in the form x = z - 3 pi / 4. Since cos(-3 pi/4)= sin(-3 pi/4) = -1/sqrt(2), we can expand the other trig functions in terms of c = cos(z), x = sin(z) : sin(x) = -1/sqrt(2) (c + s) cos(x) = -1/sqrt(2) (c - s) and so on. The expression inside the absolute value signs is then E = -sqrt(2) c + (c+s)/(c-s) + (c-s)/(c+s) - sqrt(2) (1/(c+s) + 1/(c-s)) = -sqrt(2) c + (2)/(c^2-s^2) - sqrt(2) (2c)/(c^2-s^2) = -sqrt(2) c - (2)(sqrt(2)c - 1)/(2c^2-1) = -sqrt(2) c - (2)/(sqrt(2) c + 1) = -( x + 2/(x + 1) ) where I have set x = sqrt(2) c for brevity. This expression clearly has a (local) exteme magnitude only when 1 = 2/(x+1)^2, i.e. x=-1 +- sqrt(2) (although only x = -1 + sqrt(2) is possible as we must have x = sqrt(2) cos(z) > -sqrt(2) .) There, the value is E = -( 2 sqrt(2) -1 ) so that the minimum value of the absolute value is 2 sqrt(2) - 1 = 1.828... Remark: other rational parameterizations of the function, in one free or two constrained variables, lead to quite a bit of algebra which takes far too much time to be useful. Trust me when I make this claim... A4 No good answer. If the "larger" quadratic has real roots this is not hard, but otherwise I wasn't sure how to proceed past reducing the problem to the case with A=C=1,B=0. Clearly this suggests a sequence of results of the form " |p(x)| <= |P(x)| for all x iff ...", ending with a condition stated independent of x, presumably refering to the discriminants of p and P and perhaps some other invariants. But I didn't spend much time on this one. A5 Did not spend any time on this one. Probably not hard. A6 [** WARNING: THIS ANSWER IS INCORRECT -- see below **] The answer seems to be "yes, it is possible", but right now all I have is a very inelegant answer. The partition is very naturally constructed by considering each small n in turn, but I don't see any argument which is both convincing and brief which guarantees that the process can be followed ad infinitum. Here is the sequence: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... A B B A B A A B B A A B A B B ... continuing by setting n to be in A iff n-12 is. A completely uninspired check will show that if this sequence is reversed and then shifted forward by 0, 1, ..., 11 steps, and then placed directly beneath the original sequence, then the number of times two A's align (between n=1 and n=12 inclusive) and the number of times two B's align will be equal. So for example when calculating r_A(n) and r_B(n) when n is of the form 24k+1, we will find 12k unordered pairs {s1, s2} whose sum is n, and we find that when we check whether s1 and s2 are in A or B, we simply repeat our computations k times; each time we find equal numbers of A+A pairs as B+B pairs (and of course many A+B pairs). Therefore r_A(n) = r_B(n) when n = 1 mod 24. Similar arguments hold for any n : in every set of 12 the A+A and B+B pairs are equinumerous, so we only need to consider the leftover summand nearest to n/2. If n = 24k + 2r, we will pair a number congruent to 1 with a number congruent to 2r-1 mod 12, as well as 2 and 2r-2, 3 and 2r-3, and so on (through r-1 and r+1). For each r we can conduct this experiment and find that the numbers of A+A and B+B pairs are equal. A similar experiment applies when n = 24k + 2r + 1 So the pattern seems to check out but this argument is dreadfully dull and says nothing about the obvious conjectures one is tempted to make to extend the problem. B1 No such polynomials exist. The proof here is a version of Richard Blecksmith's. We can use m x n matrices to represent polynomials of bidegree (m-1,n-1), setting M to correspond with the matrix product f(x,y) = (1, x, ..., x^{m-1}) M (1, y, ..., y^{n-1})^t . Given a set of x's and y's we can compute the matrix F of values F_{i,j} = F( x_i, y_j ) similarly as a product X M Y' . In particular, >from the invertibility of Vandermonde matrices we see that the matrix M can be recovered from a few values of f . Now we simply note that if f(x,y) = a(x) c(y) then the corresponding M is simply the product of the column matrix of coefficients of a and the row matrix of coefficients of c, and is in particular of rank at most 1. Similarly f(x,y) = a(x) c(y) + b(x) d(y) corresponds to a matrix of rank 2. On the other hand, f(x,y) = 1 + x y + x^2 y^2 corresponds to the matrix diag(1,1,1,0,0,0...) of rank 3, and so cannot be represented in the given form. I had some other clever ideas for this proof but they all seemed to require an examination of many potential coefficients of small polynomials at the end; I suspect many other people will also have wasted far too much time on what is traditionally the "easy" problem of the afternoon! B2 Given any sequence a_1, a_2, ... we can form the succession of averages a'_1, a'_2, ... as in the problem, and then iterate to get further sequences a^(k)_1, a^(k)_2, ... . It is easily checked by induction that a^(k) _ n = (1/2^k) \sum_{j=0} ^ k binomial(k,j) a_{n+j} In particular, the sequence in the problem leads to x_n = a^(n-1) _ 1 = (1/2^{n-1}) \sum_{j=0}^{n-1} binomial(n-1,j) / (1+j). If we let F(t) = \sum_{j=0} ^ {n-1} binomial(n-1,j) t^{j+1} / (j+1) then our x_n = 1/2^{n-1} F(1). On the other hand, F'(t) is just the expansion of \sum binomial (t+1)^{n-1}, and F(0)=0, so that F(1) = \int_0^1 (t+1)^{n-1} dt = (1/n) (t+1)^n | _0^1 = (2^n - 1)/n Thus x_n = (2 - 2^{1-n})/n < 2/n . B3 It suffices to show that the two integers have the same prime factorizations. If p is a prime, then its multiplicity in n! is well known (and easy to check) to be [n/p] + [n/p^2] + [n/p^3] + ... On the other hand, the multiplicity of p in lcm{1, 2, ..., k} is r iff p^r <= k <=p^{r+1}, and so the multiplicity in lcm{1, 2, ..., [n/i]} is r iff p^r <= n/i < p^{r+1} i.e. n/p^r >= i > n/p^{r+1}. The number of such integers i is [n/p^r] - [n/p^{r+1}], and therefore the i's in this range contribute r*([n/p^r] - [n/p^{r+1}]) powers of p to the product. Summing, then, over all possible values r, we get a total of \sum_{r=0}^\infty r ([n/p^r] - [n/p^{r+1}]) = \sum_{r=0}^\infty [n/p^r] ( r - (r-1) ) = \sum [n/p^r] which agrees with the number from the first paragraph. B4 Let s1 = r1 + r2, s2 = r3 + r4; p1 = r1 r2, p2 = r3 r4. The relations between the roots and coefficients of f may now be written -b/a = s1 + s2 +c/a = p1 + p2 + s1 s2 -d/a = p1 s2 + p2 s1 +e/a = p1 p2 We can write the middle pair in matrix form as [ 1 1 ] [ p1 ] [ c/a - s1 s2 ] [ ] [ ] = [ ] [ s1 s2 ] [ p2 ] [ -d/a ] If s1 and s2 are different, the matrix is invertible and we can express p1 ans p2 as rational functions of a,c,d, s1, and s2=(-b/a)-s1. So clearly if s1 is rational and a,b,c,d are integers, then p1 and p2 are rational. (We don't need to know e is an integer, but it turns out to have to be rational.) B5 [** WARNING: THIS ANSWER IS NOT QUITE CORRECT -- see below **] The area of the triangle with side lengths a,b,c is given by Heron's formula; 16 Area^2 = 2(a^2b^2 + a^2c^2 + b^2c^2) - (a^4+b^4+c^4). Once we know the values of a,b,c in terms of the distance r from P to O, it follows that we can determine the area of the triangle. (We are also supposed to check that the triangle inequalities a <= b+c etc. hold, but if say a is the largest of the three lengths, then a+b+c, a-b+c, and a+b-c are all positive, and the positivity of -a+b+c is then equivalent to the positivity of the product of these four expressions, which is precisely the formula I have noted is 16 Area^2; that is, what is supposed to be a perfect square will indeed be nonnegative iff the triangle inequalities hold.) So the question is how to determine a, b, and c from r. There is a polynomial in six variables A,B,C,D,E,F which expresses the square of the volume of a tetrahedron the squares of whose sides are A,B,C,D,E,F . Setting that polynomial equal to zero then gives a condition on the six lengths between four points which is equivalent to the points being coplanar. I never remember the formula and I spent too much time rederiving it on the exam! Here it is: 0 = (A B D + A B E + A C D + A C F + A D E + A D F + B C E + B C F + B D E + B E F + C D F + C E F ) - (A B F + A C E + B C D + D E F) - (A D^2 + D A^2 + B E^2 + E B^2 + C F^2 + F C^2 ) where A,B,C are the squares of the lengths common to a single vertex P and each of the pairs {A,D}, {B,E}, {C,F} involves all four vertices. Applying this relation to the points P,O,A,B, where the six squared-lengths are A,B,C,D,E,F = r^2,a^2,b^2,3,1,1 we get the relation 2 2 4 4 2 2 2 2 2 4 a b + a + b - 3 a - 3 b + 3 - (3 a + 3 b - 3) r + 3 r = 0 There are two analogous relations involving a,c,r and b,c,r respectively. We can also apply the relation to the points P,A,B,C, obtaining the relation 2 2 2 2 2 2 2 2 2 4 4 4 b c + a c + a b + 3 a + 3 b + 3 c - a - b - c - 9 = 0 That's three equations in four unknowns, and we can use them to solve for a,b,c in terms of r. Here's how we may do this. There are two symmetric functions in use here: S1 = a^2+b^2+c^2 and S2 = a^2b^2 + b^2c^2 + c^2a^2. We can express our symmetric expressions in terms of these: for example a^4+b^4+c^4 = S1^2-2S2 and 16 Area^2 = 4 S2 - S1^2. The last relation above states that S2 = S1^2/3 - S1 + 3, so that in effect we can express everything in terms of S1. Finally, the sum of the initial relations is also symmetric: (S2 + 2(S1^2-2S2) -6S1+9) - (6S1-9)r^2 + 9r^4 = 0. Substituting out S2 this becomes (S1^2 - 3S1) - (6 S1-9)r^2 + 9r^4 = 0. which factors, giving two possible values for S1 : S1 = 3 r^2 or S1 = 3 (r^2 + 1). The first solution is incompatible with the observed value for S1 = a^2+b^2+c^2 when r=0, and then by continuity we observe S1 must be the other value, 3(r^2+1), for all r. (It's also true for most small r that taking S1=3r^2 would lead to a negative value of a^4+b^4+c^4 !) This value of S1 then leads to S2 = 3(r^4-r^2+1). Heron's formula for the area of the triangle can also be expressed in terms of S1 and S2 as 4 S2 - S1^2 = (S1-6)^2/3 , which is now 3(r^2-2)^2. I have to say this is an awful lot of algebra; there must be a better way. Since I couldn't even remember the tetrahedron formula during the exam, I got nowhere at first; now I'm doing the calculations with Maple to make sure at least some of them are right -- obviously not permitted during the exam. B6 No clue. The result is surely also true for any measurable function, so it makes sense to prove it in that context. Then it will suffice to prove the inequality within epsilon (arbitrary); with that liberty we may replace f with a simple function, and we find that the only thing that matters is the measures of the sets on which f takes on a few values. Thus it will suffice to prove the result for increasing step functions. But I'm missing some key insight for that -- even proving this for a function f(x) = { a, if 0 < x < r ; b, if r < x < 1 } seems to lead to an inequality to be proved which involves the parameters a, b, and r , and takes some care to pin down. Two observations: It's easy to prove a similar reverse inequality: 2\int |f| >= \int \int | f(x) + f(y) | dx dy and this one is an equality if f never changes sign. So the proposed inequality is fairly sharp. (In the example of the previous paragraph, if a=1,b=-1, and r=1/2, the inequality we have to prove is an equality.) Second, the problem may be interpreted as follows: given a random-number generator, producing reals (positive and negative) according to some distribution, the expected absolute value of the sum of two of them is at least equal to the expected absolute value of a single one. I think that makes it an interesting question. (You might also find that the previous paragraph makes more sense with this interpretation.) ============================================================================== [A1] From: marciocohen@superig.com.br (Marcio Cohen) Newsgroups: sci.math Subject: Putnam - Initial 3 Solutions Date: 7 Dec 2003 08:53:41 -0800 1. n ways. In fact, for fixed q, n can be written as a+a+a+...+(a+1)+...+(a+1) with (q-r) a's and r (a+1)'s if and only if n = q*a+r, 0<=r<=q-1. But we know there is one and only one way of writing n in this form for fixed q (division algorithm). Since, 1<=q<=n, this gives n partitions. ------------------------------------------------------------------------------ From: Phil Carmody Newsgroups: sci.math Date: 07 Dec 2003 16:30:56 +0200 Ah, memories of Bresenham's line-drawing algorithm et al. Every solution is [_ n/a _] x F plus [^ n/a ^] x C for some a in {1..n} (and those are floor and cieling operators, and the perl 'x' operator). i.e. n. ------------------------------------------------------------------------------ From: toolshed37@yahoo.com (Nobody) Newsgroups: sci.math Date: 7 Dec 2003 17:49:54 -0800 Just want to see if the solution I used works. I basically said the following: Let n > 0 and we will show that for each length k between 1 and n inclusive, there is exactly one sequence of numbers of length k satisfying the inequalities that sums to n. To show this I just used an induction like argument. For each length k, take the k-length sequence that sums to n-1 and increment the smallest element. Now it sums to n, and it satisfies the desired inequalities. For the sequence of length n, it clearly has to be all 1's. QED. Do you think this is worth full credit? ============================================================================== [A2] From: marciocohen@superig.com.br (Marcio Cohen) Newsgroups: sci.math Subject: Putnam - Initial 3 Solutions Date: 7 Dec 2003 08:53:41 -0800 2. Put ai = xi^n, bi=yi^n. We need to show that (x1x2...xn + y1y2...yn)^n <= (x1^n + y1^n)(x2^n+y2^n)...(xn^n+yn^n) Switching (x1,x2,y1,y2) for (sqrt(x1x2),sqrt(x1x2),sqrt(y1y2),sqrt(y1y2)), the LHS (LE) don't change, while the RHS gets smaller, since: (sqrt(x1x2) ^n + sqrt(y1y2) ^n)^2 = (x1x2)^n + (y1y2)^n + 2sqrt( (x1x2y1y2)^n ) <= (x1x2)^n + (y1y2)^n + (x1y2)^n + (x2y1)^n = (x1^n + x2^n)(y1^n+y2^n). Now just repeat the process for (x1,xk,y1,yk) and k=3,4...,n. In the end, we have: LE = LD_final < LD_initial ------------------------------------------------------------------------------ Date: Sun, 7 Dec 2003 16:19:58 -0600 From: Eric Behr To: Dave Rusin [NB -- Eric's idea was to factor out (a_1 ... a_n)^{1/n} and view the inequality as a comparing some values of the function G(x_1, ..., x_n) = (x_1 ... x_n)^{1/n} at points (1,1,1, ..., 1), (p_1, ..., p_n), and (1+p_1, ..., 1_p_n) where p_i = b_i/a_i. --djr] It turns out that I can get it from my rewriting, which up to the boo-boo I showed you looks like G(1+p_1,1+p_2,...,1+p_n) - G(p_1,p_2,...p_n) >= 1, where G is the geom. mean. This now follows easily from parametrizing G between those two points along the straight line (say g(t), t between 0 and 1), and noting that the derivative at any t happens to be g(t)/h(t), with h(t) the harmonic mean of the values p_1+t, p_2+t, ... So it's always >= 1 and the mean value thm does it. Unless another boo-boo is present, of course. But this is probably more complicated than it needs to be. [Eric later added:] I put up some details at http://www.math.niu.edu/~behr/a2.pdf ------------------------------------------------------------------------------ Date: Mon, 8 Dec 2003 09:55:37 -0500 (EST) From: Alexander Ryba To: rusin@vesuvius.math.niu.edu A2. Let x_i = a_i/(a_i+b_i), y_i=b_i/(a_i+b_i) so that x_i+y_i = 1. (x_1...x_n)^(1/n) + (y_1...y_n)^(1/n) <= average(x_i) + average(y_i) (by AM/GM). And the sum of these averages is 1 by x_i + y_i = 1. ------------------------------------------------------------------------------ From: ensato@hotmail.com (N. Sato) Newsgroups: sci.math Date: 7 Dec 2003 18:13:06 -0800 This problem appeared on the 1992 Irish Mathematical Olympiad: http://www.kalva.demon.co.uk/irish/irish92.html ------------------------------------------------------------------------------ From: ray-usenet@manetheren.bigw.org (Ray) Newsgroups: sci.math Date: 7 Dec 2003 23:44:37 -0800 Here's another proof for A2: If any b_i = 0, it's trivial, so we may assume WLOG that each b_i = 1. For 0<=k<=n, consider the nCk ways to take a product of k distinct a_i's; let GM_k and AM_k denote their geometric and arithmetic means, respectively. Since each GM_k <= AM_k, we have \sum_{k=0}^{n} nCk GM_k <= \sum_{k=0}^{n} nCk AM_k, and taking n-th roots gives (a1 a2 ... a_n)^(1/n) + 1 <= (a1+1)(a2+1)...(a_n+1), since GM_k = (a1 a2 ... a_n)^[(n-1)C(k-1)]/[nCk] = (a1 a2 ... an)^(k/n). ------------------------------------------------------------------------------ From: marciocohen@superig.com.br (Marcio Cohen) Newsgroups: sci.math Date: 8 Dec 2003 14:14:07 -0800 As pointed out by Dave Russin, there is one correction to be made in my solution. It took me some time to figure out the way out, but I got it now: (the problem with my solution is that when I repeat the process for (x1,x3,y1,y3), I don't get 3 equals terms (for the new x2 could be different)). The first part of the solution works the same way. It shows that one can, wlog, suppose x1=x2 and y1=y2 (if not, change (x1,x2,y1,y2) for (sqrt(x1x2),sqrt(x1x2),sqrt(y1y2),sqrt(y1y2)) as in my last post). Now we use induction. For n=2 the result is easy to prove. Suppose it's vallid for n-1, apply it for the numbers (x1^2, x3,..,xn), (y1^2, ..., yn): (x1^2 * x2...xn + y1^2 * y2...yn)^n <= (x1^2n + y1^2n)(x2^n+y2^n)...(xn^n+yn^n) <= (x1^n+y1^n)^2 * (x2^n+y2^n)...(xn^n+yn^n). This means the inequality it true for n+1 variables with x1=x2 and y1=y2, and from this the result follows. Not an elegant solution, but .... ------------------------------------------------------------------------------ From tphan@bucknell.edu Mon Dec 8 20:42:50 2003 Date: Mon, 08 Dec 2003 21:42:15 -0500 To: rusin@vesuvius.math.niu.edu Let A_n = (a1 a2 ... a_n)^{1/n} B_n = b1 b2 ... b_n)^{1/n} We need to prove: (A_n + B_n)^n <= (a1+b1) (a2+b2) ... (a_n + b_n) We use induction 1) n = 2 is trivial 2) Suppose we have the inequality for n. Let us look at the inequality for n+1, i.e. the following: (A_{n+1} + B_{n+1}) ^ {n+1} <= (a1+b1) (a2+b2) ... (a_{n+1} + b_{n+1}) (*) Multiply both sides of (*) by (A_{n+1} + B_{n+1}) ^ {n-1} So now, on the right hand side, we have 2 n terms. Apply the induction hypothesis to the first n terms (the last of which is (a_n + b_n) ) and the last n terms (n-1 of which are identically (A_{n+1} + B_{n+1})). Then apply the induction hypothesis again, this time to the two numbers from the last step. After reducing, you should get (*) // [After receiving more details I wrote back --djr] From: rusin@math.niu.edu To: tphan@bucknell.edu Date: Tue, 9 Dec 2003 19:00:42 -0600 (CST) It's poor form to prove an inequality by repeatedly manipulating both sides; there is a real danger that you'll confuse the direction of the inequality or the sense of the logic, especially when using induction. So let me rewrite your proof a bit to fix this. You first establish the case n=2, which is fine, although you might want to write it as a step of inequalities like this: (a1 + b1)(a2 + b2) - (sqrt(a1 a2) + sqrt(b1 b2))^2 = (a1 a2 + b1 b2 + a1 b2 + a2 b1) - (a1 a2 + b1 b2 + 2sqrt(a1 a2 b1 b2)) = (a1 b2 + a2 b1) - 2sqrt(a1 a2 b1 b2) = ( sqrt(a1 b2) - sqrt(b1 a2) )^2 >= 0 so that (a1 + b1)(a2 + b2) >= (sqrt(a1 a2) + sqrt(b1 b2))^2 and thus sqrt((a1 + b1)(a2 + b2)) >= sqrt(a1 a2) + sqrt(b1 b2), as desired. (That is, you never actually write down the inequality for n=2 until you have proved it.) Similarly your inductive step may be re-written as follows: Given a_1 through a_{m+1} and b_1 through b_{m+1}, you define A=(a_1 a_2 ... a_{m+1})^{1/(m+1)} and likewise B. Then you evaluate, not the original right-hand side, but rather the longer (a_1 + b_1)...(a_m + b_m) (a_{m+1} + b_{m+1}) (A+B)^{m-1}. By the inductive hypothesis, the first m factors are at least equal to ((a_1...a_m)^(1/m) + (b_1...b_m)^(1/m))^m = (x+y)^m, say, and (cleverly!) the other m factors are at least ( (a_{m+1} A^{m-1})^(1/m) + (b_{m+1} B^{m-1})^(1/m))^m = (z + w)^m, say. Their product is then also an m'th power, namely of ( x + y )( z + w ) . Next you use the induction hypothesis again, this time for n=2. This tells us that ( x + y )( z + w ) is at least equal to ( sqrt( x z ) + sqrt( y w ) )^2 Then you simplify the inner expressions: for example x z is ( a_1 ... a_m )^(1/m) ( a_{m+1} A^{m-1} )^(1/m) = ( a_1 ... a_m a_{m+1} A^{m-1} )^(1/m) = ( A^{m+1} A^{m-1} )^(1/m) = A^2 so that sqrt(x z) = A. Likewise sqrt( y w ) = B, and so now we know ( x + y )( z + w ) is at least equal to (A + B)^2. Therefore the long product with which we began is at least the m'th power of this, that is, it's at least (A+B)^{2m}. Finally (assuming A+B is nonzero) we can cancel m-1 factors of (A+B) from this last inequality, and deduce that the original product is at least (A+B)^{m+1}. This completes the inductive step, and the proof is complete. ------------------------------------------------------------------------------ Date: 11 Dec 2003 22:59:53 -0800 From: msmukler@math.uchicago.edu (Micah Smukler) Newsgroups: sci.math Subject: Putnam (A2,A6) A2: Proceed by induction. If n=1, then the inequality is clear (in fact, it's an equality...) To get from n-1 to n, apply Holder's inequality with p=n to the two vectors ((a_1a_2...a_{n-1})^{1/n},(b_1b_2...b_{n-1})^{1/n})) and (a_n^{1/n},b_n^{1/n}). ------------------------------------------------------------------------------ Date: Thu, 11 Dec 2003 02:28:32 -0500 From: rrhoades@bucknell.edu To: rusin@vesuvius.math.niu.edu You have posted a few different solutions to the A2 from this years exam. Here is a short solution that you may find interesting. Let f(x) = ((a_1 + b_1)...(a_n +x))^(1/n) - (a_1 ... a_n)^(1/n) - (b_1... b_{n-1} x)^(1/n). Then we wish to show that f(b_n) >=0. We have f(0) = ((a_1 + b_1)...(a_{n-1} + b_{n-1})(a_n))^(1/n) - (a_1 ... a_n)^(1/n) >= 0, since each (a_j + b_j) >= b_j for each j. Differentiating we obtain f'(x) = 1/n [ (a_1 + b_1)...(a_{n-1} + b_{n-1})((a_1 + b_1)...(a_n +x))^(1/n -1) - (a_1 ... a_n)^(1/n - 1) - b_1... b_{n-1}(b_1... b_{n-1} x)^(1/n -1) ] >= (1/n) b_1 ... b_{n-1}[((a_1 + b_1)...(a_n +x))^(1/n -1) - (b_1... b_{n-1} x)^(1/n -1) ] >= 0, since (a_j + b_j) >= b_j for each j. Therefore, f is increasing. Hence f(x) >= 0, for all nonnegative x. So f(b_n) >= 0, as desired. ------------------------------------------------------------------------------ Date: Sat, 13 Dec 2003 18:21:58 +0100 From: Georges Zeller-Meier To: the proof given to you by rrhoades@bucknell.edu for A2 of Putnam2003 is false, the final step is false because 1/n-1<0. For instance with maple : plot(((2+1)*(3+5)*(2+x))^(1/3) -12^(1/3)-(5*x)^(1/3),x=0..20); gives a non-increasing function on R+. ============================================================================== From: marciocohen@superig.com.br (Marcio Cohen) Newsgroups: sci.math Subject: Putnam - Initial 3 Solutions Date: 7 Dec 2003 08:53:41 -0800 [A3] 3. In terms of sin and cos, we have f(x) = |1+(senx+cosx)(1+senx * cosx)| /|senx*cosx|. But, (senx+cosx)^2 = 1 + 2senx * cosx and therefore, for u=sinx+cosx: f(x) = |(u^3+u+2)/(u^2-1)| = |(u^2-u+2)/(u-1)| Now u = senx+cosx = (sqrt(2))*sen(x+pi/4) implies -sqrt(2)<=u<=sqrt(2). Besides, (u^2-u+2)/(u-1) > 0 for u>1 and <0 for u<1. Therefore, the minimum of |f| comes from the minimum of f (be it in (1,oo) or (-oo,1)). Differentiating, one gets f'(u) = 0 => u^2 - 2u - 1 = 0 => u = 1-sqrt(2). And this gives min |f(x)| = 2*sqrt(2) - 1 (obs: f"(u) > 0) Friendly, Marcio ============================================================================== From: Robin Chapman Newsgroups: sci.math Date: Sun, 07 Dec 2003 20:27:26 +0000 > A4 The "right" way to state the condition is |Ax^2 + Bxy + Cy^2| <= |ax^2 + bxy + cy^2|. It's easy if the abc form is indefinite or semidefinite. The only non-trivial cases are (i) ABC indefinite, abc definite. (ii) ABC definite, abc definite. In case (i) one can get the desired inequality by adding the inequalities (b-B)^2 - 4(a-A)(c-C) <=0 and (b+B)^2 - 4(a+A)(c+C) <=0. Case (ii) is neat! Consider the elliptical regions {(x,y): Ax^2 + Bxy + Cy^2 <= 1} and {(x,y): ax^2 + bxy + by^2 <= 1}: the former contains the latter, and their areas are pi/sqrt(AC-4B^2) and pi/sqrt(ac-4b^2). [Typos fixed --djr] ------------------------------------------------------------------------------ From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Date: 7 Dec 2003 21:00:29 GMT [A4] >The "right" way to state the condition is >|Ax^2 + Bxy + Cy^2| <= |ax^2 + bxy + cy^2|. [Note to readers: Robin's notation reverses the original problem's {a,b,c} and {A,B,C}] >It's easy if the abc form is indefinite or semidefinite. >The only non-trivial cases are >(i) ABC indefinite, abc definite. >(ii) ABC definite, abc definite. Both very nicely done, thank you! Your method of solution suggests that the proper generalizations would not be pairs of univariate polynomials (e.g. binary cubic forms) but rather pairs of quadratics involving more variables (e.g. ternary quadratic forms). I didn't think of that. ------------------------------------------------------------------------------ Date: Thu, 11 Dec 2003 02:28:32 -0500 From: rrhoades@bucknell.edu To: rusin@vesuvius.math.niu.edu A4. If |a| = |A|, then this problem can be interpreted as saying that the zeros of the "larger" polynomial are further apart than the zeros of the "smaller" polynomial. Since the spacing squared between the zeros for the polynomials are |(b^2 - 4ac)/a^2| and |(B^2 - 4AC)/A^2|. ============================================================================== From: Robin Chapman Newsgroups: sci.math Date: Sun, 07 Dec 2003 20:27:26 +0000 > A5 Can be blasted by generating functions. Is Richard Stanley on the panel? ------------------------------------------------------------------------------ From: costello@its.caltech.edu (Kevin Costello) Newsgroups: sci.math Date: 7 Dec 2003 17:49:12 -0800 I think this may work for A5: Take a Dyck path of size n with descents {d_1,d_2,...,d_k}. If d_k is even, prefix the path with an upstep, and append a down step to the end. The resulting path has only one descent of size 1+d_k If d_k is odd, d_k-1 is even, place an upstep at the beginning, a downstep at the end of the k-1'st descent. The resulting path has descents of size 1+d_(k-1) and d_k If d_k, d_k-1 are both odd, d_k-2 is even, place an upstep at the beginning and a downstep at the end of the k-2'nd descent, leaving a path with descents 1+d_k-2, d_(k-1), and d_k . . . If all the d_i are already odd, place a up and down step before the path we already have. To go the other direction, drop the first upstep and the first downstep which goes from height one to height zero. It turns out the number of such paths is given by the Catalan numbers, and this problem is part of an exercise in Stanley's enumerative combinatorics book asking for 2,145 bijections between 66 ways of counting the Catalan numbers. (If anyone got this problem by having done the entire exercise already, I say they deserve the points on the Putnam!) ============================================================================== [A6] From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Date: 7 Dec 2003 19:43:28 GMT TYPO ALERT! Another poster's response made me look again at the problem. I had looked straight at the word "nonnegative" and typed "positive" in the top line. My bad. We are to partition the NON-NEGATIVE integers into two sets A, B and count pairs of distinct NON-NEGATIVE integers both lying in A (or both lying in B). The answer is not substantially affected (nor improved, unfortunately!); the partition now begins 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... A B B A B A A B B A A B A B B A ... Sorry for the error. Peut-etre je pensais de "positif" a la Bourbaki. :-) ------------------------------------------------------------------------------ From: Robin Chapman Newsgroups: sci.math Date: Sun, 07 Dec 2003 20:27:26 +0000 This is well-known. It's treated in D. J. Newman's _Analytic Number Theory_ (Springer 1998). The sets are those positive integers with an even/ an odd number of ones in base-2 representation. Most easily done with generating functions. ------------------------------------------------------------------------------ From: "Paul Pollack" To: "Dave Rusin" Date: Sun, 7 Dec 2003 15:35:55 -0500 This problem seems to be drawn from the first chapter of Newman's Analytic Number Theory. He shows that if we let A be the set containing 0, then A and B are uniquely determined, and A is just the set of integers with an even number of 1's in base 2 expansion. The argument is as follows. Let A(z) = sum(z^a, a in A), and B(z) = sum(z^b, b in B). Then r_A(n) = r_B(n) says (1/2) (A(z)^2 - A(z^2)) = (1/2) (B(z)^2 - B(z^2)), or equivalently A(z)^2 - B(z)^2 = A(z^2) - B(z^2). Since `A(z) + B(z) = 1/(1-z), this implies (A(z) - B(z))*1/(1-z) = (A(z^2) - B(z^2)), so A(z) - B(z) = (1-z) (A(z^2) - B(z^2)). Repeatedly replacing z by z^2, z^4, z^8, etc., one finds A(z) - B(z) = (1-z)(1-z^2)*...*(1-z^{2^{n-1}}) (A(z^{2^n}) - B(z^{2^n})). Letting n-> oo and using A(0) = 1, B(0) = 0, one finds A(z) - B(z) = product(1-z^{2^i}) over all nonnegative i, and from this one can read off the elements of A, B. Defining A and B in this manner one can work backwards to check that the initial relation among the generating functions holds, so this A, B gives the (unique) solution. HTH, Paul ------------------------------------------------------------------------------ From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Date: 7 Dec 2003 21:00:29 GMT My answer is at odds with Robin's. I checked and found I had been sloppy in considering all the cases. (I knew that wasn't the way to go!) So I retract my answer. Interestingly I did suspect the binary representations would reveal the answer but the parity pattern did not jump off the page for me. Thanks also to Paul Pollack who sent the same reference and proof as: >This is well-known. It's treated in D. J. Newman's >_Analytic Number Theory_ (Springer 1998). >The sets are those positive integers with an even/ an odd number of >ones in base-2 representation. Most easily done with generating functions. ------------------------------------------------------------------------------ Date: Mon, 8 Dec 2003 09:55:37 -0500 (EST) From: Alexander Ryba To: rusin@vesuvius.math.niu.edu A6. The proof that sets of numbers with an even/odd number of binary digits work has an almost trivial proof without generating functions. (I hope that this is correct, I haven't thought about since proctoring our Putnam students on Saturday.) Given an representation of n as a sum of two distinct integers r and s each with an odd (resp even) number of binary digits, locate the least significant binary digit where r and s differ. Change that digit in both r and s to get r' and s' that have the same sum but now both have an even (resp odd) number of binary digits. This establishes a bijection between the obvious sets with sizes r_A(n) and r_B(n). ------------------------------------------------------------------------------ From: ensato@hotmail.com (N. Sato) Newsgroups: sci.math Date: 7 Dec 2003 18:13:06 -0800 This problem appears, among other places, in "A Problem Seminar" by D. J. Newman. His solution uses generating functions: Let f(x) = \sum_{a \in A} x^a and g(x) = \sum_{b \in B} x^b, and assume 0 is in A. Then f(x) + g(x) = 1/(1 - x), and the given property translates as f^2(x) - f(x^2) = g^2(x) - g(x^2). He then derives that f(x) - g(x) = (1 - x)(1 - x^2)(1 - x^4)(1 - x^8)..., so we get that A is the set of numbers with an even number of 1s in the binary expansion, and B is the set of numbers with an odd number of 1s. There is also a reference in Sloane's sequence database: http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000069 http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001969 ------------------------------------------------------------------------------ From: msmukler@math.uchicago.edu (Micah Smukler) Newsgroups: sci.math Subject: Putnam (A2,A6) Date: 11 Dec 2003 22:59:53 -0800 A6: Let b(n) be the number of 1's in the base-2 expansion of n; let f(n)=(-1)^b(n). Let A=f^{-1}(1), B=f^{-1}(-1). Then clearly A and B partition the set of nonnegative integers. Also, f(2n)+f(2n+1)=0 for all n. Thus \sum_{i=0}^n f(i)=0 if n is odd, and f(n) if n is even. Suppose p+q=n, with p \neq q. If p and q are both in A, then f(p)+f(q)=2; if p and q are both in B, then f(p)+f(q)=-2; if one is in each set, then f(p)+f(q)=0. It therefore suffices to show that \sum_{p+q=n,p \neq q} f(p)+f(q)=0 for all n. If n is odd this sum is just 2\sum_{i=0}^n f(i)=0; if n is even, it is 2(\sum_{i=0}^n f(i)-f(n/2))=2(f(n)-f(n/2)). By construction, f(n)=f(n/2) for all even n; thus this sum is zero. So we are done. ============================================================================== Date: Sun, 7 Dec 2003 17:11:10 -0500 (EST) From: David Kraines To: Dave Rusin here's a shorter proof for B1 {1, x, x^2} and thus {1, 1+x+x^2,1-x+x^2} are lin indep sets of polynomials. Therefore they are not each in the span of the set of two functions {a(x), b(x)}. Set y = 0, 1, -1 in turn to get a contradiction. ============================================================================== [B5] From: Robin Chapman Newsgroups: sci.math Date: Sun, 07 Dec 2003 20:27:26 +0000 Use complex numbers. Let the three points be 1, w and w^2 where w = exp(2pi i/3) and z be the interior point. The three lengths are |1 - z|, |w - z| and |w^2 - z|. These are the sides of a triangle: one whose side-vectors are (1-z), w(w-z) and w^2(w^2-z) as these add to 0. Now the area of a triangle in C with vertices 0, u and w is +-1/2 Im(uw). Using this with the above triangle gives area sqrt(3)(1 - |z|^2)/4. ------------------------------------------------------------------------------ From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Date: 7 Dec 2003 21:00:29 GMT >Use complex numbers. Let the three points be 1, w and w^2 >where w = exp(2pi i/3) and z be the interior point. [...] >Using this with the above triangle >gives area sqrt(3)(1 - |z|^2)/4. In my answer I forget that I was computing 16 Area^2, accounting for part of the difference between Robin's answer and mine. Since his answer is so much shorter I am confident his answer is right; I will try to find the source of my algebra error when I have a chance. ------------------------------------------------------------------------------ From: ensato@hotmail.com (N. Sato) Newsgroups: sci.math Date: 7 Dec 2003 18:13:06 -0800 Assume that A, B, and C are on the circle counter-clockwise. Rotate P 60 degrees clockwise around A, B, and C, to points D, E, and F, respectively. Then triangles APD, BPE, and CPF are all equilateral, with side lengths a, b, and c, respectively. Furthermore, the same rotation around A which takes P to D, also takes C to B, so triangle APC is congruent to triangle ADB, which implies that BD = PC = c. Hence, triangle BPD has side lengths a, b, and c, which proves the first part. Let K be the area of this triangle. As shown, triangle APC is congruent to triangle ADB. Similarly, triangle BPA is congruent to triangle BEC, and triangle CPB is congruent to triangle CFA. Therefore, hexagon ADBECF has twice the area of triangle ABC. But hexagon ADBECF also consists of the three congruent triangles PDB, PEC, and PFA, and three equilateral triangles PAD, PBE, and PCF. Thus, K is a function of a^2 + b^2 + c^2. Then (say, using coordinates), you can work out that a^2 + b^2 + c^2 is a function of OP. I saw essentially this problem on an olympiad last year, but I don't remember which country. ------------------------------------------------------------------------------ From: "Ignacio Larrosa Canestro" Newsgroups: sci.math Date: Mon, 8 Dec 2003 19:03:38 +0100 > [quote of above ... ] But hexagon ADBECF also consists of the three > congruent triangles PDB, PEC, and PFA, and three equilateral triangles > PAD, PBE, and PCF. It last is obvious only if P is inner to the triangle, althougt if P is outer of triangle, but inner to the circle it is also true. If is outer the circle, the hexagon ADBECF can be autocrossing. Then, it can view that the area of the hexagon is the difference of the are of the three triangles of sides a, b an c and the triangle ABC. > Thus, K is a function of a^2 + b^2 + c^2. Then > (say, using coordinates), you can work out that a^2 + b^2 + c^2 is a > function of OP. If OA = r and OP = k, a^2 = k^2 + r^2 - 2k*r*cos(alfa) b^2 = k^2 + r^2 - 2k*r*cos(beta) c^2 = k^2 + r^2 - 2k*r*cos(gamma) a^2 + b^2 + c^2 = 3(k^2 + r^2) - 2k*r(cos(alfa) + cos(beta) + cos(gamma)) But r(cos(alfa) + cos(beta) + cos(gamma)) is the component in the direction of OP of the sum of vectors OA, OB and OC, that is null. Then a^2 + b^2 + c^2 = 3(k^2 + r^2) and (APF) = (2(ABC) - (APD) - (BPE) - (CPF))/3 (ABC) = 3*sqrt(3)r^2/4 (APD) = sqrt(3)a^2/4, ... K = (APF) = (sqrt(3)/4)(r^2 - k^2) If P is out of the circle, K = (sqrt(3)/4)(k^2 - r^2) i.e. K = (sqrt(3)/4)|r^2 - k^2| ------------------------------------------------------------------------------ From: Petr Lisonek To: rusin@math.niu.edu Subject: Putnam B5 - Cayley-Menger determinant The formula for the volume of a simplex in terms of squares of its edge lengths becomes very compact when one uses the Cayley-Menger determinant, which was invented precisely for this purpose. [PL clarified in a later email:] Cayley-Menger determinant is the one that has a row of 1's and a column of 1's. A good reference for this is the book Distance Geometry by L.M. Blumenthal. The squared volume of a simplex is constant times the C.-M. determinant. As for other references for example there is an entry at MathWorld. [Note: see also http://www.math-atlas.org/98/tetrahedral_ineq --djr] ------------------------------------------------------------------------------ Date: Thu, 11 Dec 2003 02:28:32 -0500 From: rrhoades@bucknell.edu To: rusin@vesuvius.math.niu.edu B5. This problem appears in Chapter 1 Section 1 of Mathematical Olympiad Challenges by Titu Andreescu and Razvan Gelca. The first part appears as a worked example, while the second part is excercise 9. ============================================================================== [It appears to me that problem B6 was challenging for many people, not just me! Many interesting ideas were proposed as bases for answers; several of them are complete and presented below. There was considerable further sci.math traffic about this problem, not all preserved here. See the newsgroup archives at groups.google.com , mathforum.edu, etc. --- djr ] ------------------------------------------------------------------------------ Date: Mon, 8 Dec 2003 09:55:37 -0500 (EST) From: Alexander Ryba To: rusin@vesuvius.math.niu.edu B6. Let A and B be the unions of intervals on which f is positive and negative. Let a be the total legth of A and b the total length of B. Let I_A be the integral of f over A and I_B the integral of -f over B. So the RHS is I_A + I_B. The double integral over AxA is 2aI_A and over BxB is 2bI_B. WLOG a>= b. Case 1: I_A > I_B. Here 2aI_A + 2bI_B >= aI_A + bI_B + bI_A + aI_B = RHS. So the part of the LHX integrated over AxA and BxB is already larger. Case 2: I_A <= I_B. Here the double integral over AxB (or BxA) is at least the double integral of -f(x) - f(y) for x in A and y in B which works out as aI_B - bI_a. So the sum of 4 double integrals over AxA, AxB, BxA, BxB is at least 2aI_A + 2bI_B + 2aI_B - 2bI_A = 2I_B + 2(a-b)I_A >= 2I_B >= I_B + I_A. ------------------------------------------------------------------------------ From: Ciprian Pop Newsgroups: sci.math Date: Tue, 09 Dec 2003 11:24:42 -0800 So far it seems that all solutions to B6 were based on a discrete version. Here is a more direct proof: Denote by I the unit interval and let m be the Lebesque measure on the real line. Then th double integral is: \int_{R_+} 2( m(f>t)m(f>-t) + m(ft) + m(f<-t) dt (use Fubini for both). Now, for each t, the first integrand is larger or equal than the second. This is in fact equivalent to: for t larger or equal than 0, m( -t 0 } and { x : f(x) < 0 } respectively, and let mu <= 1/2 be min(mu_p,mu_n). Then int int |f(x) + f(y)| dx dy >= c(mu) int |f(x)| dx, where c(mu) = (1 + (1 - 2 mu)^2). Note that the constant can be seen to be best possible by considering a sequence of functions tending towards the step function which is 1 on [0,mu] and -1 on (mu,1]. Suppose without loss of generality that mu = mu_p. We will prove a strengthened discrete analogue, namely that for real a_1, ..., a_n we have 1/n^2 sum_{i,j} |a_i + a_j| >= c(p/n) * 1/n sum_{i=1}^n |a_i| where p <= n/2 is the number of a_1, ..., a_n which are positive. (In fact, since c(mu) = c(1-mu), this inequality still holds p > n/2.) The discrete analogue implies the continuous result, because for n sufficiently large we may choose our mesh so that the fraction of values of f which are positive is epsilon-close to mu_p; that is, we may choose our mesh so that p/n -> mu as n -> infty. (To see that this is possible, note that f assumes positive values on at least ceiling(n*mu) of the intervals [(i-1)/n, i/n), while it assumes exclusively positive values on at most floor(n*mu) of them.) We will prove following inequality, easily seen to be equivalent to the strengthened discrete analogue: sum_{i < j} | a_i + a_j | >= (n - 1 - 2p + 2p^2/n) sum_i |a_i|. Write r_i = |a_i|, and assume without loss of generality that r_i >= r_{i+1} for each i. Then |a_i + a_j| = r_i + r_j if a_i and a_j have the same sign, and is r_i - r_j if they have the opposite sign. The left-hand side is therefore equal to: sum_i (n - i) r_i + sum_j r_j C_j where C_j is the number #{ i < j : sgn(a_i) = sgn(a_j)} - #{ i < j : sgn(a_i) <> sgn(a_j) . Consider the partial sum P_k = sum{j=1..k} C_j. If exactly p_k of a_1, ... , a_k are positive, then this sum is equal to C(p_k,2) + C(k-p_k,2) - (C(k,2) - C(p_k,2) - C(k-p_k,2)) where C(n,k) = n choose k, and which expands and simplifies to -2 p_k (k-p_k) + C(k,2). For k <= 2p and even, this partial sum would be minimized with p_k = k/2, and would then be equal to -k/2; and for k < 2p and odd this partial sum would be minimized with p_k = (k +/- 1)/2, and would then be equal to -(k-1)/2). Either way, P_k >= -floor(k/2). On the other hand, if k > 2p then -2 p_k (k-p_k) + C(k,2) >= -2 p(k-p) + C(k,2) since p_k is at most p. Let Q_k be -floor(k/2) if k <= 2p and -2 p(k-p) + C(k,2) if k > 2p, so P_k >= Q_k. Note that Q_1 = 0. Partial summation gives sum_j r_j C_j = r_n P_n + sum_{j=2..n} (r_{j-1} - r_j) P_{j-1) >= r_n Q_n + \um_{j=2..n} (r_{j-1} - r_j) Q_{j-1} = sum_{j=2..n} r_j (Q_j - Q_{j-1}) = -sum_{k=1..p} r_{2k} + sum_{j=2p+1..n} (j - 1 - 2p) r_j. It follows that sum_{i < j} | a_i + a_j | = sum_i (n - i) r_i + sum_j r_j C_j >= sum_{i=1..2p} (n-i-[i even]) r_i + sum_{i=2p+1..n} (n-1-2p) r_i = (n-1-2p) sum_i r_i + sum_{i=1..2p} (2p+1-i-[i even]) r_i >= (n-1-2p) sum_i r_i + p sum_{i=1..2p} r_i >= (n-1-2p) sum_i r_i + p (2p/n) sum_i r_i as desired. The next-to-last and last inequalities each follow from the monotonicity of the $r_i$'s, the former by pairing the ith term with the (2p+1-i)th. cheers, Dave (updated address: dsavitt math mcgill ca; still post to usenet from this address because it's already inundated by spam!) ------------------------------------------------------------------------------ Date: Wed, 07 Jan 2004 12:19:44 -0600 To: rusin@math.niu.edu From: David Ullrich Subject: Re: Putnam problem B6 This is only a partial solution - it seems to me that it really should lead to a full solution but I don't see how. Suppose that \int_0^1 f(x) dx = 0. There exists a function g such that |g| = 1 and fg >= 0 (i.e., fg = |f|.) So \int_0^1 \int_0^1 |f(x) + f(y)| dx dy >= \int_0^1 \int_0^1 (f(x) + f(y)) g(x) dx dy = \int_0^1 f(x) g(x) dx = \int_0^1 |f(x)| dx. That's qed _if_ \int_0^1 f(x) dx = 0. It seems to me that the general case "must" follow, but I don't see how. (The case \int_0^1 f(x) dx = 0 seems like it should be the hardest case; for example at the other extreme, if f >= 0 the result is obvious.) ==============================================================================