Here are some answers to the Putnam exam 1999. Most of this material comes from a post I made to the USENET newsgroup sci.math just after the test; follow-up posts by others are inserted where appropriate. There is a section of general comments at the end of this file. Thanks to Richard Carr for finding some typos (fixed here). It seems to be the optimal results for B4 are not yet obtained. I have saved some of the relevant correspondence in a sister file http://www.math.niu.edu/~rusin/problems-math/putnam.99B4 ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: 1999 Putnam Exam -- some SPOILERS Date: 5 Dec 1999 07:12:40 GMT ============================================================================== A-1. Solution: We try linear polynomials. The roots of f and g must be the points where the right-hand side is not differentiable, and sums and differences of their slopes must yield the other slopes (0, 3, and -2), so I get f(x)=(3/2)(x+1), g(x)=(5/2)x, and then compute h(x)=-x+(1/2). Comment: I mis-read the problem at first and thought we needed all solutions. What's the easiest way to see the polynomials _must_ be linear? [From: Robin Chapman [Newsgroups: sci.math [Subject: Re: 1999 Putnam Exam -- some SPOILERS [Date: Mon, 06 Dec 1999 08:54:23 GMT [ [If you make the fairly reasonable assumption that on the three [intervals from left to right, |f| - |g| equals -f + g, f + g and f - g [respectively then this answer just drops out. [Date: Tue, 07 Dec 1999 12:28:25 -0800 [To: rusin@math.niu.edu [From: Colin Percival [ [To see that the polynomials must be linear, note that everywhere that the [second derivative exists, it is zero. And, incidentally, the solution is [unique; if you want I can send you my proof. [[Remark: he means "unique up to sign" in the case of f and g.]] ============================================================================== A-2. Solution: If p is everywhere non-negative, its real roots must be of even multiplicity, so we write p = q^2 * Prod( (x - r)(x - rbar) ) where {r, rbar} range over the conjugate pairs of complex roots, taken according to multiplicity. Let s(x) = Prod( (x-r) ) = t(x) + i u(x), say, where t and u are real polynomials. Clearly the product Prod( (x - rbar) ) is then sbar = t(x) - i u(x), so that p = q^2 * ( t + i u ) * ( t - i u ) = ( q t )^2 + ( q u )^2, a sum of the desired form with k = 2. Comments: The question implies p has real coefficients; I took that degree of casualness to suggest I could be a bit breezy with details (e.g. that the roots appear in cojugate pairs with equal multiplicity). There will likely be some complaints about the level of rigor in the phrasing of the questions. Also note that this question has appeared fairly recently in the newsgroups, which gives USENET readers a certain edge... Matthew P Wiener (mwiener@m-s-g.com) reminds me that: [ By the way, problem A-2 is a special case of the Artin-Shreier theorem [ (=Hilbert Problem 17). ============================================================================== A-3. Solution: Let's use partial fractions: factor 1 - 2x - x^2 = (1 - a x) (1 - b x) to see the expansion is that of (1/(a-b)) ( a/(1-ax) - b/(1-bx) ) = (1/(a-b)) Sum( (a^(n+1)-b^(n+1))x^n ) that is, we have a "closed form" expression a_n = (a^(n+1)-b^(n+1))/(a-b) with which to work. Clearing denominators from the hoped-for equation we see we need (a^(n+1)-b^(n+1))^2 + (a^(n+2)-b^(n+2))^2 = (a-b)(a^(m+1)-b^(m+1)) for some m. Well, this is really just a little algebra. We need only note a*b = -1 so that (ab)^(n+1) + (ab)^(n-1) vanishes and we get a^(2n+2)+b^(2n+2) + a^(2n+4)+b^(2n+4) = a^(m+2)+b^(m+2) + a^m + b^m which is obviously true if m = 2n+2. Comment: After having done A-2 I wondered if there is a way to do this involving the complex number a_n + i a_(n+1) in some way. Any takers? Another solution: [From: Chen [Newsgroups: sci.math [Subject: Re: 1999 Putnam Exam (tentative A3 solution) [Date: Mon, 06 Dec 1999 10:43:10 GMT [ [We can set 1=(1-2x-x^2)*power series [Then we have a0=1, a1=2 and a_n+2=2a_n+1+a_n for all n>=0 [Of course, this gives a recurrence relation with a solution given by [standard techniques, so you get a_n=c1*(1+sqrt(2))+c2*(1-sqrt(2)) for [some constants c1 and c2, which you could substitute the initial [conditions to solve for. From here, the problem is pretty easy: write [a_n^2+a_n+1^2 and do a little factoring; from small cases it is easy [to conjecture that m=2n+2, and this can be proven directly with the [explicit formula for a_n. Another solution: [From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik) [Newsgroups: sci.math [Subject: Re: 1999 Putnam - SPOILER A3 semi-solution [Date: 5 Dec 1999 22:50:15 -0500 [ [I tried 2-by-2 matrices: [ [The difference equation for a_n is [ [a_0 = 1, a_1 = 2, a_(n+2) = 2 * a_(n+1) + a_n [ [This gives, after some fiddling around: [ [Define the matrix (companion matrix of the equation) [ [A = [ [[ 0 1 ] [[ 1 2 ] [ [Then by declaring for consistency a_(-1) = 0, a_(-2) = 1, we get [ [A^n = [ [[ a_(n-2) a_(n-1) ] [[ a_(n-1) a_n ] [ [and you just express (A^(n+1))^2 in two ways. [From: smiley@saturn.math.uaa.alaska.edu [Newsgroups: sci.math [Subject: Putnam A3 followup [Date: Mon, 13 Dec 1999 18:59:17 GMT [ [Actually [ [a(m+n) = a(m)a(n) + a(m-1)a(n-1) [ [not just [ [a(2n+2) = [a(n+1)]^2 + [a(n)]^2 [ [And... it's an oldie. See Neil's A000129, or Eric's "Pell Number" [ [Len Smiley [Date: Thu, 9 Dec 1999 03:42:50 -0800 [To: rusin@vesuvius.math.niu.edu (Dave Rusin) [From: robjohn9@idt.net (Rob Johnson) [Subject: Re: Putnam solutions [ [Multiplying both sides by 1 - 2x - x^2 and equating coefficients, we get [ [ a_0 = 1 [ a_1 = 2 [ a_n = 2 a_{n-1} + a_{n-2} for n >= 2 [ [A simple inductive proof shows that [ [ a_{n+k} = a_{k+1} a_{n-1} + a_k a_{n-2} [ [Setting n = k+2 gives [ [ a_{2k+2} = a_{k+1}^2 + a_k^2 ============================================================================== A-4. Let S be the sum, i.e. the doubly infinite sum of the terms (m/3^m)^2 (n/3^n) / (n/3^n + m/3^m) which we simply write x_m^2 x_n / (x_n + x_m) for brevity, where x_n = n/3^n. Interchange the order of summation and swap the names of the dummy variables to see S is also equal to the sum of x_m x_n^2 / (x_n + x_m) . Thus 2S is the double sum of the sum of these two, which simplifies to x_m^2 x_n / (x_n + x_m) + x_m x_n^2 / (x_n + x_m) = x_m x_n (x_n + x_m) / (x_n + x_m) = x_m x_n i.e., S = (1/2) (Sum x_n)^2. This is a well-known sum, which is usually evaluated like this: let F(t) = Sum( x_n t^n , n >= 1 ); we want F(1). Well, since x_n = n/3^n, we note that it's worth considering G(t) = Sum( (1/3^n) t^n, n >=1 ), whose derivative is G'(t) = Sum( (n/3^n) t^(n-1), n>=1) = (1/t) F(t). On the other hand, G is a geometric series with sum (t/3) / (1-t/3) = t/(3-t) = -1 - 3/(t-3), so that G'(t) = 3/(t-3)^2 , F(t) = 3t/(t-3)^2, and our sum is F(1) = 3/4. So the original sum is S = (1/2)(3/4)^2 = 9/32. Comment: The problem looked too goofy for me to work on in the short time before I went to lunch, where Y.C.Kwong suggested to me both the simplification and the averaging over the symmetry group; the rest is just details. ============================================================================== A-5. Solution: We are asked to show that there is a constant C such that |p(0)| <= C \integral( |p(x)|, -1 <= x <= 1) The set of all polynomials of a given degree is a finite-dimensional vector space, which we give a norm defined by |p| = integral( |p(x)| ) (the integral done over the interval [-1,1] ). That it really is a norm is easily checked, the most interesting part (to me) being the observation that |p| can only be zero when p is, a consequence of the fact that the vector space contains only continuous functions. Note that on the one-dimensional subspaces this is essentially the ordinary norm: | c.p | = |c|.|p| for real c and polynomial p. I seem to recall that something like this alone is enough to show this norm is equivalent to the ordinary ones, e.g. if p(x) = Sum( a_n x^n ) then sqrt( Sum( a_n^2 ) ) <= C1 |p| for some C1. This would then suffice, since p(0) = a_0 is at most sqrt( Sum( a_n^2 ) ). But is that really true? What is it that we need to prove norms equivalent? (And what is acceptable as a proof on the Putnam?) [From: Robin Chapman [Newsgroups: sci.math [Subject: Re: 1999 Putnam Exam: A5, B4 comments. [Date: Sun, 05 Dec 1999 21:42:19 GMT [ [All norms on a finite-dimensional real vector space are equivalent. [Also every linear functional on a finite-dimensional space is [continuous. [ [The usual proof comes down to compactness. You might as well take the [space to be R^n and denote the L^1 norm || ||. It's easy to see that [there's a constant C with || || <= || ||_1, i.e., [||(a_1, a_2, ..., a_n)|| <= C(|a_1| + |a_2| + ... + |a_n|). [This implies || || is continuous wrt the L^1 norm. Now consider [its behaviour on the L^1 sphere {x : ||x||_1 = 1}. It attains [a maximum and minimum on this L_1 compact set..... [ [This Q is probably too trivial with this analytic machinery to be good. I considered merely letting C be the maximum value of the evaluation function p -> p(0) , restricted to the sphere |p| = 1; by compactness, such a C exists, and then by the linearity of the integral we would have the desired inequality for any p by applying it first to the polynomial p/|p| which lies on the unit sphere (with respect to this norm). But I think this begs the question, since the compactness of the sphere and the continuity of evaluation are more or less the same issue as the equivalence of norms. I know there are many integral inequalities which I keep forgetting (e.g. Hoelder's) although these seem a little wrong if too abstract (it's kind of critical we have bounded-degree polynomials). But we have |p(0)| <= max( |p(x)|, x in [-1,1] ) = ess sup (|p|), so what we're asked to prove is just an application of a comparison between the L-\infty and L-1 norms on this space of functions. This is the appropriate pair, right? ("1/p + 1/q = 1" and all that...) But I'm away from my books and too lazy to get them. I think I don't need to make much use of the fact that the space consists of polynomials of bounded degree, although standard bell curves make it clear that something is necessary: change the "1999" to something larger and you will need to change C. I ran a check on polynomials which vanish at all points of the form x=i/1000, -1000 <= i <= 1000, except 0. In that case p(0) is larger than the integral by 4 or 5 orders of magnitude. [From: rusin@vesuvius.math.niu.edu (Dave Rusin) [Newsgroups: sci.math [Subject: Re: 1999 Putnam Exam: A5, B4 comments. [Date: 6 Dec 1999 20:41:23 GMT [ [Here is a proof I received in email from "Jim" (whose email I will not [post unless "he" tells me to); I've tweaked the presentation but added [no new ideas. This applies to every case of polynomials of degree < N. [ [It suffices to get a (concrete) lower bound on the integrals of polynomials [with p(0)=1; bounds for the others may then be obtained by scaling, except [for those with p(0)=0, for which there is nothing to prove anyway. [So we assume p(0)=1. Observe that this means p may be written [ p(x) = Product( 1 - s_k x ) [for some N-1 complex s_k . [ [First note we may as well assume s_k is real. If s_k = t_k + i u_k, [then the two conjugate factors give (1 - s_k x)(1 - \bar{s_k} x) = [(1 - t_k x)^2 + (u_k x)^2 >= (1 - t_k x)^2. So a lower bound for the [integral of Prod( 1 - t_k x ) applies to P, too. [ [Cover the interval [-1,1] with N closed intervals of length 2/N. [There myst be one not containing the reciprocal of any t_k. [Remove from this interval the subintervals of length 1/(N+1) from [each end, leaving an interval J of length 2/(N(N+1)) in the middle. [The key is that each point x of J is a distance at least 1/(N+1) [>from each of the 1/t_k, so that for all nonzero t_k we have [ | 1 - t_k x | = |t_k| | x - 1/t_k | >= |t_k| / (N+1). [ [We use this inequality whenever t_k is _large_, meaning say whenever [|t_k| >= 1 - 1/(N+2). In that case, we now have a lower bound on [| 1 - t_k x | : it's at least 1/(N+2) for any x in J. [ [In the case t_k is _small_, the bound is even easier: since |x| <= 1, [whenever |t_k| < 1 - 1/(N+2), we again have [ | 1 - t_k x | >= 1 - |t_k| |x| >= 1 - ( 1 - 1/(N+2) ) = 1/(N+2) [ [So either way, we have a bound on the factors of P, and thus on P itself: [for all x in J, |P(x)| >= 1/(N+2)^(N-1) . The integral across J is [then at least 1/(N+2)^(N-1) * 1/(N(N+1)) > 1/(N+2)^(N+1), and of [course the integral across [-1,1] is at least this large. [ [This method give an inequality |p(0)| < C integral( |p| ) with [C = 2001^2000. That's a bit extravagant; I'm sure 10^10 is plenty... [From: Tal Kubo [To: rusin@vesuvius.math.niu.edu [Subject: Re: 1999 Putnam Exam: A5, B4 comments. [Date: Mon, 6 Dec 1999 21:19:00 -0500 [ [>We were trying to show that there is a constant C such that for every [>polynomial p of degree less than N=2000 we have [> | p(0) | <= C integral( |p(x)|, -1 <= x <= 1 ) [> [>We have noted that such a C must exist on general principles, and I [>have commented that it must be fairly large, as is shown by examples [>like p(x) = Product( x^2-(i/N)^2, 1 <= i < N ). [ [p(0) is a fixed linear combination of integrals of p(x)x^k over [-1,1], [for k=0,1,...deg(p). Let C be the absolute sum of the coefficients. [To get the coefficients, invert a Hilbert matrix 1/(1+i+j), which [is standard (minors are Hilbert matrices, so there is enormous [cancellation in the final result). ============================================================================== A-6. Solution: Divide by a_(n-1) and express in terms of the sequence c_n := a_(n+1)/a_n . I get c_(n+1) = 6 c_n - 8 c_(n-1) which is a linear recurrence associated with the first few terms c_1 = 2, c_2 = 12 and characteristic polynomial X^2 - 6 X + 8 = (X-2)(X-4). Having already dealt with the theory in A-3 and A-4 let me just summarize the generating-functions conclusion to observe this means c_n = 4^n - 2^n (which is easily checked by induction anyway). Thus a_n = Prod( c_k, 1 <= k < n) = Prod( 4^k - 2^k , 1 <= k < n) . Note that (by Fermat's little theorem), a prime p divides c_k if k is a multiple of p-1. In particular, p^r divides a_n if n > r*(p-1). This is certainly this case if n is a multiple of p^r, so that a_n is divisible by each of the primes dividing n (to at least an equal exponent), and thus by n itself. ============================================================================== B-1. Solution: I avoid fractions by writing theta = 2 u. Then since ACD is an isosceles triangle with repeated side of length 1, the base CD has length 2 sin(u). Also note angle ACD measures pi/2 - u, so ECD measures u. This leaves pi - 3 u for angle DEC. So now by the law of sines, segment EC has length (sin(2u) / sin(pi - 3 u)) (length CD) = 2 sin(u) sin(2u)/ sin(3u). Now we can toss all the marks associated with D (and B) and view the remaining trapezoid. It's helpful to drop a perpendicular from F to AC, meeting the latter at G, say. Then we know the length of FG, giving AG a length (length CE)/tan(2u), and leaving EF with length |EF| = 1 - 2 sin(u) cos(2u) / sin(3u) As u -> 0, this approaches 1 - 2/3 = 1/3. [Date: Thu, 9 Dec 1999 03:42:50 -0800 [To: rusin@vesuvius.math.niu.edu (Dave Rusin) [From: robjohn9@idt.net (Rob Johnson) [Subject: Re: Putnam solutions [ [Since < BAC = theta and DAC is isoceles, < ACD = pi/2 - theta/2. That [leaves < BCD = theta/2. < CDE = theta, so by the law of sines, [ [ |DE|/|CE| = sin(theta/2)/sin(theta) -> 1/2 as theta -> 0. [ [Because DAC is isoceles, < ADC = pi/2 - theta/2 as well. This leaves [< BDE = pi/2 - theta/2. Since ABC is a right triangle, we also have [< DBE = pi/2 - theta. Again by the law of sines, [ [ |BE|/|DE| = sin(pi/2-theta/2)/sin(pi/2-theta) -> 1 as theta -> 0 [ [Thus, |BE|/|CE| -> 1/2, which means that |BE|/|BC| -> 1/3. [ [Because ABC is similar to FBE, we also have |DE|/|AC| -> 1/3. Since [|AC| = 1, that means that |DE| -> 1/3. ============================================================================== B-2. Solution: We are to show P has either is a power of a single linear factor, or has no repeated roots, so let us suppose (for contradiction) that it has a repeated root; composing with a linear translation for convenience, we will assume P has a root at 0 of multiplicity n > 1, that is, P = x^n R for some polynomial with R(0) nonzero. Likewise write Q = x^m S with S(0) nonzero; we have m=0, 1, or 2. Now we have x^n R = P = Q P'' = (x^m S)( n(n-1) x^(n-2) R + 2n x^(n-1) R' + x^n R''). Divide by x^(n-2+m) and get (*) x^(2-m) R = S ( n(n-1) R + 2n x R' + x^2 R''). Since R(0) and S(0) are nonzero, when we evaluate (*) at 0 we get a contradiction if m < 2 , unless n(n-1) = 0, i.e., unless this root of P is simple. If m=2, then evaluation of (*) at 0 shows S(0) = 1/ n(n-1), but when m=2, S is (this) _constant_, so we have some cancellation in (*) and then conclude -2n R' = x R'', which can only be true if R' = is a multiple of x^(-2n). This cannot be true if R is a polynomial and n>1, unless R'=0. Thus R is constant, and P = constant multiple of x^n. In this case P does not have two distinct roots. [Thanks to Brian R. Hunt for alerting me of a sign error! Fixed here.] Another solution: [Newsgroups: sci.math [From: thorine@math.purdue.edu (Thomas Horine) [Subject: Re: 1999 Putnam Exam [Date: Sun, 05 Dec 1999 16:38:42 GMT [ [For P quadratic, the result is obvious, so assume n = deg(P) > 2... so P'''(x) [is not identically zero. [ [Anyways, [P(x) = Q(x) P''(x) [P'(x) = Q'(x)P''(x) + Q(x)P'''(x) [P''(x) = Q''(x)P''(x) + 2Q'(x)P'''(x) + Q(x)P''''(x) [ [>From here on, denote the i^th derivative of P as P^{i}. [Now, Q quadratic implies that all derivatives of Q beyond the second will be [zero. So, continually taking derivatives, we get [ [P^{i}(x) = c_i * Q''(x)P^{i}(x) + d_i * Q'(x)P^{i+1}(x) + Q(x)P^{i+2}(x) [for some positive integers c_i, d_i (i >1). [Furthermore, note that (from the construction of the c_i, d_i) that [c_(i+1) = c_i + d_i [and [d_(i+1) = d_i + 1 [So, in paticular the c_i are strictly increasing. [ [Now suppose that P has a root r of multiplicity 1 < k. [Thus P(r) = P'(r) = ... = P^{k-1}(r) = 0 [yet P^{k}(r) is nonzero. [ [P^{k-2}(r) = c_(k-2)*Q''(r)P^{k-2}(r) + d_(k-2)*Q'(r)P^{k-1}(r) + Q(r)P^{k}(r) [ = 0 [ [P^{k-1}(r) = c_(k-1)*Q''(r)P^{k-1}(r) + d_(k-1)*Q'(r)P^{k}(r) + Q(r)P^{k+1}(r) [ = 0 [ [P^{k}(r) = c_(k)*Q''(r)P^{k}(r) + d_(k)*Q'(r)P^{k+1}(r) + Q(r)P^{k+2}(r) [ nonzero. [ [The P^{k-2} equation implies that Q(r) = 0. Combining this with the P^{k-1} [equation implies that Q'(r) = 0. Combining this with the P^{k} equation gives [Q''(r) = 1/c_k. [Now, [ [P^{n}(r) = c_(n)*Q''(r)P^{n}(r) + d_(n)*Q'(r)P^{n+1}(r) + Q(r)P^{n+2}(r) [ [Obviously, the last two terms are zero. So, since P^{n}(r) is not zero, [Q''(r) = 1/c_n. [However, this implies k = n !! [ [(It seems a bit long-winded, but I think that is mostly due to the notation [involved.) Another solution: [To: rusin@math.niu.edu [Date: Tue, 07 Dec 1999 10:01:39 -0800 [From: " " [ [ [P(x) has degree at least 2 since it has at least two distinct roots. If [P(x) = R_1(x)*(x-a)^k where k>=2 and R_1(a) /= a, then [P''(x) = R_2(x)*(x-a)^{k-2} where R_2(a) /= a. (Proof is easy but must be [supplied.) So P(x)/P''(x) = R_3(x)*(x-a)^2 where R_3(x) is a rational [function with R_3(a) /= 0. But we know that P(x)/P''(x) is quadratic, [hence R(x) is a constant and Q(x) = C*(x-a)^2. Knowing this, we find that [C*R_1(x) = R_2(x). Writing R(x) = R_1(x) = R_2(x)/C and differentiating [the expresion P(x) = R(x)*(x-a)^k twice, we find [(1-Ck(k-1))*P''(x) =(x-a)^{k-1}*[(x-a)*R''(x) + 2k*R'(x)]. Now P''(x) has [a zero of order exactly k-2 at a, so the only way this equation is [possible is k(k-1) = 1/C and R'(x) = 0. But then R(x) is a constant A, [which means that P(x) = A*(x-a)^k ahd hence P(x) does not have two [distinct roots---a contradiction. ============================================================================== B-3. Solution: Just what is (1-xy^2)(1-x^2y) S(x,y) ? We can expand it into a sum and difference of terms x^i y^j S(x,y) = Sum( x^(m+i) y^(n+j) ), leading to a grand collection of multiples of monomials x^r y^s. The coefficient of this monomial is the sum of +1, if r <= 2s and s <= 2r and r > 0 and s > 0 -1, if r-1 <= 2(s-2) and s-2 <= 2(r-1) and r-1 > 0 and s-2 > 0 -1, if r-2 <= 2(s-1) and s-1 <= 2(r-2) and r-2 > 0 and s-1 > 0 +1, if r-3 <= 2(s-3) and s-3 <= 2(r-3) and r-3 > 0 and s-3 > 0. Now, each of these conditions is _roughly_ the statement that r/s is between 1/2 and 2, which is to say they tend either to pass or not, in unison; in those cases, the sum of the contributions is +1-1-1+1 = 0. So the nonzero summands are those where the conditions are NOT equivalent to " 2s and s <= 2r and r > 0 and s > 0 " -- roughly, the edge of this region. More precisely (and I could do this more convincingly with an illustration) we find that the coefficients are "+1" for all points (r,s) in a V-shaped region of the first quadrant; add "-1" in the region formed by scooting the region out 3 units along either edge, and then add "+1" in the intersection. (The "V" includes its boundary but not its vertex, if you get my drift.) The result is that the sum is zero at all points except it's "+1" at those with 2r-3 < s <=r and 2s-3 < r <= s, a diamond containing only the lattice points (r,s) = (1,1), (1,2), (2,1), and (2,2); and it's "-1" at (3,3). So the product (1-x^2y)(1-xy^2)S(x,y) is xy + xy^2 + x^2y + x^2y^2 - x^3y^3 exactly. The limit as x and y increase to 1 is obviously 3. Comment: I take it from the statement of the problem that we are to be somewhat cavalier about order of summation and the questions of convergence. [Robin Chapman commented, [No problem, since all the terms are positive. I find this slightly [easier to visualize if I take 1 + S(x,y) instead of S(x,y). [Date: Tue, 07 Dec 1999 10:01:39 -0800 [From: " " [ [ [Your solution is valid, but long winded. Noting that 1/2 <= m/n <= 2 if [and only if m <= 2n and n <= 2m, S(x,y) + T(x,y) + T(y,x) = [sum_{m,n>=1} x^m*y^n = xy/(1-x)(1-y) where T(x,y) = sum{m,n>=1} [x^m*y^{2m+n} = (xy)^2/(1-x)(1-xy^2). Thus S(x,y) = xy/(1-x)(1-y) - [(xy)^2/(1-x)(1-xy^2) - (xy)^2/(1-y)(1-yx^2). A little algebraic [manipulation and you find the required result. ============================================================================== B-4: [From: bhunt@noJUNKipst.umd.edu (Brian R. Hunt -- delete noJUNK to reply) [Newsgroups: sci.math [Subject: Putnam B4 solution [Date: 6 Dec 99 21:34:53 GMT [ [Here my solution, it seems simpler than any other I've seen, though a [more clever solution can yield a stronger bound on f'/f. (Since the [solution below yields a bound of exactly 2, I suspect it's more or [less what the problem writer had in mind.) The basic idea is that if [f'/f is too large at some point, then moving to the left of that point [we can force either f or f' to 0. [ [------ [We make repeated use of the fact that if g(0) = h(0) and g'(x) <= [h'(x) for x <= 0 then g(x) >= h(x) for x <= 0. [ [To prove f'(x) < 2f(x) for a particular x, we can assume without loss [of generality that x = 0 (by translating f) and that f(0) = 1 (by [scaling f). Let a = f'(0) and b = f''(0); we want to prove a < 2. [ [Since f is an increasing function, f'''(x) <= f(x) <= f(0) = 1 for x [<= 0, we have f''(x) >= f''(0) + x = b + x for x <= 0, and hence 0 < [f'(x) <= f'(0) + bx + (1/2)x^2 = a + bx + (1/2)x^2 for x <= 0. [ [Thus the polynomial a + bx + (1/2)x^2 has no nonpositive roots, and [since a and b are positive it has no positive roots either. Since it [has no real roots, its discriminant b^2 - 2a must be negative. [ [Similarly, since f'' is increasing, f''(x) <= f''(0) = b for x <= 0, [whence f'(x) >= f'(0) + bx = a + bx and then 0 < f(x) <= f(0) + ax + [(b/2)x^2 = 1 + ax + (b/2)x^2 for x <= 0. As above, a^2 - 2b < 0. [ [Since a^2 < 2b and b^2 < 2a, we have a^4 < 4b^2 < 8a; therefore a^3 < [8 and a < 2 as desired. [------ [ [Notice that the only place the hypothesis f'''(x) <= f(x) is used [above is to assert that f'''(x) <= f(0) for x <= 0, which is why the [bound obtained on f'/f is significantly suboptimal. [Date: Thu, 9 Dec 1999 03:42:50 -0800 [To: rusin@vesuvius.math.niu.edu (Dave Rusin) [From: robjohn9@idt.net (Rob Johnson) [Subject: Re: Putnam solutions [ [For t > 0, consider the quotient [ [ [f(x) - f(x-t)] - [f'(x) + f'(x-t)]t/2 [ F = -------------------------------------- [1] [ t^3 [ [Notice that both numerator and denominator vanish when t = 0. Using the [mean value theorem, yields for some s in (0,t) [ [ f'(x-s) - [f'(x) + f'(x-s)]/2 + f''(x-s) s/2 [ F = -------------------------------------------- [ 3 s^2 [ [ [f'(x-s) - f'(x)]/2 + f''(x-s) s/2 [ = ---------------------------------- [ 3s^2 [ [Again, both numerator and denominator vanish when t = 0. Using the mean [value theorem, yields for some r in (0,s) [ [ -f''(x-r)/2 + f''(x-r)/2 - f'''(x-r) r/2 [ F = ---------------------------------------- [ 6r [ [ f'''(x-r) [ = - --------- [2] [ 12 [ [Combining [1] and [2] gives that, for some r in (0,t) [ [ [f(x) - f(x-t)] - [f'(x) + f'(x-t)]t/2 = -f'''(x-r) t^3/12 [ [Since f''' < f, we get [ [ [f(x) - f(x-t)] - [f'(x) + f'(x-t)]t/2 > -f(x-r) t^3/12 [ [Since f > 0 and f' > 0, we get [ [ f(x) - f'(x) t/2 > -f(x) t^3/12 [ [A little algebraic manipulation results in [ [ f'(x) < f(x) (2 + t^3/6)/t [3] [ [Setting t = 6^(1/3) in [3], yields [ [ f'(x) < (9/2)^(1/3) f(x) < 1.651 f(x) [ [Note that the only property of f''' we used was that f''' < f; we used [neither f''' > 0 nor f'' > 0, yet we got a constant better than 2. At the time of the exam, my own comments were limited to just these two paragraphs: We are asked to show that if f, f', f'', f''' are all positive everywhere and if f''' <= f everywhere, then f' < 2 f everywhere. Clearly a function like f(x)=exp(x) will have the desired properties, but f'(x) = 1*f(x), so it seems the "less than two times" might be more profitably thought of as saying "is roughly equal to". I developed this idea in a subsequent post, but didn't actually finish (indeed, a month later I'm still sure there's much better stuff to be said): From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Putnam B4 solution Date: 7 Dec 1999 07:35:38 GMT I decided to get my hands dirty with this one. I think you can actually get some fairly strong results by using the tools you'd resort to if you really had to study f. I did not complete the analysis enough to actually solve the problem -- I can't imagine this is an appropriate way to solve a Putnam problem! -- but I think one could, so I'll show what analysis I did finish. Let's first note that f(t) = exp(k t) satisfies the given conditions if 0 < k <= 1, so we take the perspective that our goal ought to be to see how closely f must resemble exp(kt). After some experimentation I decided to use this transformation: let H(t) = f(t) / f'(t) which is defined and twice-differentiable on the whole real line. The conditions given are equivalent to the statements H > 0 , H' < 1, H^3 > -H H'' + (1-H')(1-2H') > 0 everywhere, and what we want to prove is that H > 1/2 everywhere. Maybe even H >=1 almost everywhere or something? (Our prototype functions have H=1/k>=1, H'=H''=0.) We may write epsilon(t) for the expression (-H H'' + (1-H')(1-2H') )/H^3, so that epsilon is a well-defined number which is to vary between 0 and 1. Now, if epsilon we pre-defined -- e.g. epsilon=(1/2) (a constant) say -- then the equation defining epsilon would be a second-order differential equation we could use to solve for H. This suggests the following device, which can be used when one really must solve such a differential equation. Let (x,y) = (H(t), H'(t)) be the curve traced out (in the "phase plane") as t varies over the reals. The image of this curve has a slope, when defined, equal to dy dy/dt H''(t) [(1-H')(1-2H') - epsilon H^3]/H -- = ----- = ------ = ------------------------------- = dx dx/dt H'(t) H' (1-y)(1-2y) - epsilon y^3 = ------------------------- x y which is to say the curve is consistent with the initial assumptions iff it stays in the region x > 0, y < 1, and has a slope of the form shown at each point, for some epsilon in (0,1). Conversely, given such a curve, we can recoup H (and thus f = exp(integral(1/H dt)) too) as follows: locally at least, we view the curve as the graph of a function y = K(x). We need to write x as a function H of t in such a way that K(H(t)) = H'(t). Well, look instead for t as a function of x: the condition which is to be satisfied is that (dt/dx) = 1/(dx/dt) = 1/H'(t) = 1/y = 1/K(x) so we simply take t to be an antiderivative of 1/K, that is, H is recovered from the curve by decreeing that t = \integral_{x0}^{H(t)} dx / y Warning: the functions we have suggested for comparisons do not yield a curve at all: since H is constant, the "curve" traced out in these cases is just a single point. But these are the only such bad examples. So here is the method for producing all other functions meeting the given initial conditions. At each point in the quadrant x>0, y<1 draw a mark whose slope is [(1-y)(1-2y) - epsilon x^3]/(xy) for some epsilon in (0,1). Connect up with a smooth curve. View as the graph of a function K(x). Compute an antiderivative of 1/K, and let H be its inverse. Then 1/H is the logarithmic derivative of a function f meeting the desired conditions. This is supposed to make it sound easy to create lots of solutions f. There is a major caveat, however: we are supposed to have f defined over all of R, which means H must be as well, which means its inverse must yield all of R as its codomain. Thus the integral of 1/K(x) must blow up at left and right endpoints of the domain of 1/K (in either case it's sufficient that 1/K have a domain which is unbounded on that side, provided the antiderivative of 1/K grow to infinity). This is particularly interesting since there is one special case in which we may perform all the calculations explicitly: if we set epsilon to be the constant 0, then the curve is to be a solution to a _separable_ differential equation y dy / ((1-y)(1-2y)) = dx / x whose solutions are x = K (1-y)/sqrt(|1-2y|) for arbitrary positive constant K. These curves all cross the horizontal axis roughly as sqrt(x+constant). In particular, the integral of 1/K(x) stays _bounded_ on the left. In other words, the functions f we create in this way can only be defined on the half-line. So the original problem comes down to this: show that, however the vector field is chosen (consistent with the assumed bounds on epsilon), the curves passing sufficiently far to the left will cross the horizontal axis fast enough that the integral of dx/y stays bounded in that region. Presumably this is a consequence of the fact that the vector field must be vertical at all points on the x-axis, irrespective of choice of epsilon. "Details left to the reader" (i.e., I'm tired now and I want to quit :-) [Remarks not posted: those particular level curves having epsilon=0 correspond to the solutions f(t) = quadratic polynomials of the original problem. Other correspondences are perhaps of interest, e.g. f(t) = exp(t/2) + exp(t/3) corresponds to the portion of the parabola (x-2)(x-3)/6 crossing the x-axis at x=2 and x=3. I think it's true that f'(x) <= f(x) everywhere, as suggested by this analysis, but I didn't finish that proof. It may be possible to show that every such f is a positive linear combination of the functions f(x)=exp(kt) for k<=1, but I'm not even really sure what the right conjecture is, since we must presumably allow infinite sums too, that is, f(t) = integral( R(k) exp(kt) d k, 01 [Let p_i be the smallest prime dividing x_i. [Let p be the squarefree part of the product of the p_i. [Note that 1 < p_i | (x_i,p) for all i, so we must have that, for some i, [(x_i,p) = x_i ... in other words, x_i | p. [ [WLOG, assume i = 1. [So write x_1 = q_1 * ... * q_r where the q_i are distinct and {q_i} is a [subset of the {p_j}. [Let q be the maximum of the q_i. Say q = p_k. Then p_k is the smallest prime [dividing x_k, and the largest prime dividing x_1. [ [Consider (x_1,x_k). If d | (x_1,x_k), then it must be a product of primes both [dividing x_1 and x_k. Thus d is a power of p_k. However, d | x_1, which is a [product of distinct primes, so d | p_k. Hence, we see that (x_1,x_k) = q = [p_k,... a prime. Another solution: [From: FGD [Newsgroups: sci.math [Subject: Re: 1999 Putnam Exam -- some SPOILERS [Date: Mon, 06 Dec 1999 22:29:25 GMT [ [> What the heck does S "look like"? Any S containing prime will [> work. Note that this is really a semigroup / poset question, not [> number theory. [ [You're right, no number theory in there: strictly combinatorics, [families of multisets and intersection properties. Here's a short proof [I came up with which "hides" all the combinatorics just like the [question. [ [Let q be the least positive integer which is not relatively prime with [any element of S. (q exists since, for example, the product of all [elements of S is not relatively prime with any element of S.) Then there [must be a s in S such that s|q (i.e. gcd(q,s) = s). Now let p be any [prime divisor of s (and hence of q). Since q/p < q, there must be a t in [S which is relatively prime with q/p. Now t is not relatively prime with [t, so we must have gcd(q,t) = p. Since p|s|q, it follows that gcd(s,t) = [p. Whence s, t are elements of S with gcd(s,t) prime. [Date: Tue, 07 Dec 1999 10:01:39 -0800 [From: " " [ [ [Let q be the least positive integer which is not relatively prime with any [element of S. (The existence of q is guaranteed by the wellordering [principle the fact that the product of all elements of S is an example of [a positive integer which is not relatively prime with any element of S.) [Using the given property of S, we can find s in S such that s|q [(i.e. gcd(s,q) = s). Now since s > 1, there is a prime p|s|q. As q/p < q, [there is a t in S such that gcd(q/p,t) = 1 by the definition of q. But t [is not relatively prime with q, so we must have gcd(q,t) = p the only [other possibility being gcd(q,t) = 1. But then gcd(s,t) = p since [p|s|q. Hence s,t are elements of S with gcd(s,t) prime. Comment: This really has not a lot to do with the integers per se. For a fixed finite set S we may let P be the set of primes dividing the elements of S, and then associate to each integer n the vector (|n|_2, |n|_3, |n|_5, ..., |n|_p) of exponents needed to write n as a product of powers of these primes, times an integer n' coprime to P. Define a partial ordering on the set of lattice points in Euclidean space (having non-negative coordinates) by setting u <= v if u_i <= v_i for each i. Define the meet of two vectors by meet(u,v)_i = min(u_i,v_i). Then the problem is this: show that if a finite set S of a lattice has this property: (*) for all v in the lattice there is either a u in S with meet(u,v) = 0 or a u in S with u <= v then it also has this property: there exist (u,v) in S whose meet is one of the basis vectors in R^n ============================================================================== ============================================================================== GENERAL REMARKS: I get to cheat a little bit: these solutions took me somewhat more than the allotted six hours to think through and write up. Moreover, I use a machine to check my calculations, which is not allowed on the test. But if I were young and focused, I could probably have done as well this year as on most recent exams. There were quite a few problems for which I can scarcely conceive of an alternative solution (taking a liberal definition of "same idea", of course). I mean, what can you do in B-2, for example, besides assume a double root, plug in, and get a contradiction local to the root? (It's not even a _polynomial_ question, really; smooth local functions work just the same.) Not a lot of geometry or visualization this year. Part A especially seemed sort of heavy on series and other pretty elementary material, as opposed to group theory or some analysis of games or something. I expect to see some grousing this year about the wording of the questions. Maybe it's just me, but "is a polynomial" seems sort of vague when the choice of coefficient ring will make a difference in the problem. Just what can be assumed with no loss of credit -- well-known series, famous theorems, details regarding convergence -- will always be a source of some confusion, but I saw more than the usual number of examples today. Problem B6 sounds odd ("E x (p v q)" rather than "(E x p) v (E x q)"). But the _students_ here did not complain about any wording on the test. A few questions (e.g. A-5, A-2) are actually sort of important. I hope it's possible for people to get credit for thinking a little more broadly about what's going on in the non-trick problems.