PUTNAM 2005 --- 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. (Commentary includes items for problems || || A-1, A-3, A-4, A-5 (several nice ideas), B-2, B-3, B-4, B-5. || || The only posted solution to A-6 is contained in Dan Berenstein's set || ========================================================================== From: rusin@cs.niu.edu (David Rusin) Subject: Putnam 2005 -- some answers [SPOILER ALERT] Date: Sun, 4 Dec 2005 09:17:18 +0000 (UTC) Newsgroups: sci.math I posted the Putnam problems earlier this evening. I have only had time to work on some of the questions, so there is no answer here (yet) to the following problems: A-3, A-4, A-6, B-4, B-5. As always I will keep copies of solutions at http://www.math.niu.edu/~rusin/problems-math/ dave A-1. Proof by induction on n. When n is even it suffices to double such a representation of n/2 ; when n is odd, it suffices to let 3^k be the largest power of 3 less than or equal to n and then add 3^k to a representation of n' = n - 3^k. Note that by construction the representation of n' involves only even integers, none of which divide 3^k. If, conversely, 3^k divides one of the summands for n', then n' >= 2 3^k, which would mean n >= 3^k + 2 3^k = 3^(k+1), violating the definition of k. When I asked Richard Blecksmith where I had seen this problem before, he pointed out I had critiqued for him the paper "$3$-smooth representations of integers" (Amer. Math. Monthly 105 (1998), no. 6, 529--543) that he wrote with Selfridge. The Math Reviews item about this paper contains further links to the literature. A-2. Let B_n be the number of rook tours which end at the bottom point (n,1). Also let T_n be the number of such tours that end at the top point (n,3) . A tour that does not end at (n,3) must pass through it, connecting to (n-1,3) and (n,2). Using such reasoning, together with the fact that tours are _connected_ (in the topological sense), we find that the tours ending at (n,3) must consist of a path passing through (k,3) (for some k <= 1), then to (k+1,3), ..., (n,3), then to (n,2), (n-1,2), ..., (k+1,2), and then to (k+1,1), ..., (n,1). In particular, we have B_n = T_{n-1} + T_{n-2} + ... + T_1 . In the same way a path ending at (n,3) must be the concatenation of such an "S"-shaped curve, following a path which ended at some (k,1), including the degenerate case k = 0, that is, the whole path is one long S . Thus we have T_n = B_{n-1} + B_{n-2} + ... + B_1 + 1 For the first few values we notice B_1 = 0, B_2 = 1, B_3 = 2, and T_1 = 1, T_2 = 1, T_3 = 2. In particular, the recurrence relations then shows that T_n = B_n for all n > 1, from which a trivial induction argument shows B_n = 2^(n-2) for all n > 1. I didn't see an obvious way to show every tour of width n somehow gives rise to precisely two tours of width n+1. A-3. No idea. Note that "z^{n/2}" is not well defined except locally (and not at z=0 of course). Of course this doesn't matter, really, since the condition " g'(z) = 0 " can be expressed without reference to square roots, but it's really kind of an awkward thing to put on the test. A-4. Not sure. Obviously H is for Hadamard, who studied things of this type. I'm sure the answer is going to be some sort of Cauchy-Schwarz inequality. (I just gave this as an exam question: use the inner product < A, B > = trace( A^t B ) and the identity matrix for B to relate tr(A) and tr(A^2) when A is symmetric.) A-5. Maple gives an answer with dilogarithms and things like that but the answer seems to be pi log(2) / 8 . Substitute the Taylor series ln(x+1) = x - x^2/2 + ... into the integral to get - sum_{n>=1} (-1)^n/n J_n where J_n = \int_0^1 x^n/(x^2+1) dx . (In order to justify term-by-term integration we could, for example, replace the Taylor series by the Taylor polynomial and note that the remainders go to zero. In fact, I will be working below with a partial sum of the series with the J's anyway, and then take the limit.) Clearly J_n + J_{n+2} = \int_0^1 (x^n + x^{n+2})/(x^2+1) dx = \int_0^1 x^n dx which is just 1/(n+1). We also dredge up ancient memories to compute J_0 = arctan(1) = pi/4 J_1 = 1/2 log( 1^2 + 1) = log(2)/2. So we have formulas J_{2i} = (-1)^i [ pi/4 - sum (-1)^j/(2j+1)] (sum over 2j+1 < 2i ) J_{2i+1} = (-1)^i [ln(2)/2 - sum (-1)^j/(2j) ] (sum over 2j < 2i+1 ) So the Nth partial sum for our series for the integral expands to -pi/4 sum_{2i<=N} (-1)^i/(2i) + ln2/2 \sum_{2i+1<=N} (-1)^i/(2i+1) + sum_{2i<=N, 2j+1 <=N} (-1)^{i+j}/( (2i)(2j+1) ) (In the last sum, the summands with the odd factor smaller than the even one come from a J_even and the others come from a J_odd. I wrote out a few more intermediate steps when doing this by hand but I'm a lazy typist.) That last double sum then factors into ( \sum_i (-1)^i/(2i) )( \sum_j (-1)^j/(2j+1) ) and each of those factors duplicates another factor already shown, i.e. we have something of the form AB + CD + BD, which I write as (A+D)B + (C+B)D - AD : ( -pi/4 + ( \sum_j (-1)^i/(2i+1) ) ) sum_{2i<=N} (-1)^i/(2i) + ( ln2/2 + ( \sum_j (-1)^i/(2i) ) ) sum_{2i+1<=N} (-1)^i/(2i+1) - ( \sum_i (-1)^i/(2i) )( \sum_j (-1)^j/(2j+1) ) Now as we let N -> oo we have "A+D" and "C+B" both tend to zero, so only the rest remains, which of course tends to (-A)(-C) = (ln2/2)(pi/4) . A-6. Well, I thought I had this worked out but my answer reduces, for n=4, to a number less than 1, which is unfortunate since no quadrilateral can consist of 4 non-acute angles except rectangles (which are a subset of measure zero). I'll try again later. B-1. We just need a polynomial which vanishes at all the lattice points ([a], [2a]). These are clearly just the points (n, 2n) and (n, 2n+1) for integer n. They lie on the lines y = 2x and y = 2x+1 respectively, so that P = (2x - y)(2x+1 - y) vanishes in either case. This has to be the single easiest Putnam problem I have ever seen. Note that we just the other day had a sci.math request for proof that any finite set of points in the plane lies in an algebraic curve. The short answer is "interpolate!" but there are problems if multiple points have the same x-coordinate. At the time I got around this with a perturbation of the points, but I could have proceeded as in this example and suggested partitioning the points into several curves and then multiplying together their defining equations. B-2. Sort the k_i into ascending order. Then we can find all the sets of k_i with a given initial sequence e.g. (k1, k2, k3). Equation (R) : sum 1/k_i = 1 then either gives a lower bound on the remaining k_i, or else forces n to equal the length of the current initial segment. In the first case we then usually get a contradiction to equation (S): sum k_i = 5n - 4. because the left side is too large. (And in the other case we get a contradiction or confirmation that we have a solution.) For example, starting with (k1,k2)=(2,4) we find that if k3=4 then (R) makes n=3, which contradicts S. If instead k3=5 then (R) shows each other k_i >= 20, so that sum k_i >= 11 + 20(n-3) > 5n-4 since n>3. This leaves only k3 >= 6, so that sum k_i >= 6 + 6(n-2) > 5n-4, again contradicting (S). So there is no solution with (k1,k2) = (2,4). That's a straightforward argument, and it's pretty clear at the outset that this procedure is sure to succeed, but actually carrying it out seems to have more steps than a Putnam answer should have, so maybe I'm missing something slick. (Or maybe I'm just belaboring the exposition!) When k1=1, (R) shows n=1, and we find a unique solution: {1}. When k1=k2=2, (R) shows n=2, but then (S) fails. If instead k1=2, k2=3, then (R) makes k3 >=6. Indeed {2,3,6} is a solution. There are no solutions starting with (2,3,7-or-more) since these all contradict (S). We treated the case (2,4) above. There are no solutions (2,k2) with k2>=5 since the sum of the k_i would be at least 2 + 5(n-1) = 5n-3 > 5n-4. Solutions starting with (3,3) would appear to include (3,3,3) but this violates (S). The other solutions permitted by (R) would begin (3,3,4,12) or (3,3,5-or-more), both of which violate (S). Solutions starting (3,4,4) must have the other k_i >=6 by (R), and other solutions starting (3,4) have k_i >=5. In both cases, as usual, the sum of the k_i is too large to agree with (S). Same with (3,k2) for any k2 > 4. Solutions with k1=4 do exist: (4,4,4,4). Otherwise solutions have say m<4 4's and the other n-m terms at least equal to 5; then the sum of the k_i is at least 5n-m, which is too large since m < 4. Final tally: three solutions, namely {1}, {2,3,6}, {4, 4, 4, 4}. Note that the equation (R) is common in many (maybe unexpected) places in mathematics. For example the groups generated by 3 involutions whose products have orders k1, k2, k3 are very different depending on whether sum 1/k_i is <1, =1, or >1 . Similarly the solution sets to the Diophantine problems x1^k1 + x2^k2 = x3^k3. So these solutions to (R) (not all of which satisfy (S) ) are well known. B-3. Power functions f(x) = k x^r all work except when r=0 or r=1. (f(x) = x also works). I believe those are the only such functions. To prove this, let's change them to linear functions. That is, let g(y) = log(f(exp(y))), so f(x) = exp(g(log(x))). Then f'(x) = exp( g(log(x)) ) g'(log(x)) / x, and so f'(a/x) = exp( g( b - log(x) ) ) g'(b - log(x)) exp( log(x) -b) where b = log(a). If f is a solution to the problem, this will equal x/f(x) = exp( log(x) - g( log(x) ) ). So I believe the condition on f gives this condition on g: for some real b, g'(b - log(x)) = exp( b - g(b-log(x)) - g(log(x)) ) for all x > 0. Better: if there is such a b, then let y = log(x)- b/2 ; then for all real y we will have g'( b/2 - y ) = exp( b - g(b/2 - y) - g(b/2 + y) ) Thus if we define h(y) = g(b/2 + y) we have h'( -y) = exp( b - h(-y) - h(y) ) But the right side is an even function, so the left side must be too. But if h' is an even function, then h is an odd function, so the right side is _constant_. So h' is constant, so h is linear, and since it's also an odd function, it must be h(y) = m y for some m. Now work backwards: g is also linear, and thus f is a power function. B-4. Not sure. I can start a recursive expression which can _calculate_ f(m,n), and at the end I will see that it's symmetric. But surely they had in mind that we would define some set of objects and count its elements in two ways, one yielding f(m,n), the other giving f(n,m). For example, the set can be naturally seen as the set of lattice points in an L^1-ball in R^n; perhaps each of its points can be paired off with a path through the ball in R^m, each step of the path passing to an adjoining shell (i.e. increasing sum |x_i| by one each time)? I couldn't make this work. B-5. Dunno. It's true for n=1 since (a) makes P linear, and there are not many linear functions divisible by x^2 ! B-6. This is fun. Let J be the nxn matrix filled with 1's. Let f(x) = det( J - lambda I ) where lambda = 1-x (that is, f(x) = p(1-x) where p is the characteristic polynomial of J .) Clearly J is of rank 1, and has n as an eigenvalue (the eigenvalue is (1, 1, ..., 1) ), so p(x) = (-1)^n x^(n-1) ( x - n ). Now integrate f(x) over [0,1]. This is \int_0^1 p(lambda) d lambda = (-1)^n \int_0^1 (lambda^n - n lambda^(n-1) ) = (-1)^n( 1/(n+1) - n/n) = (-1)^(n+1) n/(n+1). That's the right side of the equation to be proved. To get the other side, compute f(x) straight from the definition. We're computing the determinant of the matrix whose diagonal entries are x and the others are 1. So the determinant is the signed sum over all permutations of x^k 1^(n-k) where k is the number of diagonal entries used in the n-fold product. Clearly this is nu(pi) as defined in the problem. So f(x) = sum sigma(pi) x^nu(pi), and thus its integral over [0,1] is clearly sum_{pi in S_n} sigma(pi)/(nu(pi)+1). It helps to have just taught the definition of determinants a few weeks ago! ============================================================================== A-1 From: Woeginger Gerhard Subject: Re: Uniqueness in 2005 Putnam A1 Newsgroups: sci.math Date: 06 Dec 2005 10:51:53 GMT Peter L. Montgomery wrote: # The representation need not be unique -- for example # 11 = 8 + 3 = 9 + 2. Another example is # 385 = 256 + 81 + 48 = 144 + 96 + 81 + 64 = 243 + 72 + 54 + 16. # Are there examples with arbitrarily many representations? Yes. This question and related questions are discussed in Michael Avidon On Primitive 3-smooth Partitions of n Electronic Journal of Combinatorics 4(1), 1997 http://www.combinatorics.org/Volume_4/v4i1toc.html ------------------------------------------------------------------------------ From: israel@math.ubc.ca (Robert Israel) Newsgroups: sci.math Subject: Re: Uniqueness in 2005 Putnam A1 Date: 5 Dec 2005 21:10:39 GMT > The representation need not be unique -- for example >11 = 8 + 3 = 9 + 2. Another example is >385 = 256 + 81 + 48 = 144 + 96 + 81 + 64 = 243 + 72 + 54 + 16. Also 313 = 16 + 81 + 216 = 16 + 54 + 243 = 9 + 48 + 256 = 6 + 64 + 243 >Are there examples with arbitrarily many representations? Yes. Suppose x has n representations, and take b large enough that none of the summands is divisible by 3^b. Then 16*x + 11*3^b has at least 2n representations: take any representation of x, multiply all summands by 16, and add either 8*3^b + 3^(b+1) or 3^(b+2) + 2*3^b. ============================================================================== A-3 From: rusin@cs.niu.edu (David Rusin) Date: Sun, 4 Dec 2005 10:20:36 +0000 (UTC) Newsgroups: sci.math Is this what Rolle's theorem looks like when wrapped around the unit circle? A polynomial like p, all of whose roots lie on the unit circle, is (the numerator of) a composite f( (1-ti)/(1+ti) ), with f a (multiple of a) real polynomial and t ranging over the real line. (This is just the Moebius transfomation taking the real line to the unit circle.) This gives one real root of f' between consecutive pairs of roots on the real line, so that p' must have a root on the unit circle between any two roots of p. But I can't seem to turn this into the desired equation. Maybe it's just getting late. ------------------------------------------------------------------------------ From: "D. J. Bernstein" Date: Sun, 4 Dec 2005 10:42:46 +0000 (UTC) Newsgroups: sci.math David Rusin wrote: > But I can't seem to turn this into the desired equation. The real part of (z+r_i)/(z-r_i) is positive for |z|>1. Sum over i. ============================================================================== A-4 From: pin...@gmail.com Date: 4 Dec 2005 02:37:51 -0800 Newsgroups: sci.math A4. We have a rows and b columns, say the upper-left of our matrix to help with visualization, filled with 1's. Any two rows must agree in precisely n/2 columns, thus any two of our a rows must agree in n/2 - b of the remaining n - b columns. Thus in the upper-right a*(n-b) section, we need exactly (aC2)*(n/2 - b) = a*(a-1)*(n-2b)/4 agreements. Any set of a numbers either +1 or -1 must have at least 2*(a/2 C 2) = a(a-2)/4 agreements, and there are n-b columns, thus there are at least a(a-2)(n-b)/4 agreements in the upper-right. Thus a*(a-1)*(n-2b)/4 >= a*(a-2)*(n-b)/4; which reduces to n >= ab. ============================================================================== A-5 From: matthew_folz@hotmail.com Date: 4 Dec 2005 13:52:50 -0800 Newsgroups: sci.math Perhaps cleaner solutions to A5, B2, which I arrived at during the contest: A5: The trick is to add a parameter to the integral Put I(A)=\int^1_0 log(Ax+1)/(x^2+1)dx, so that I'(A) = \int^1_0 x/[(Ax+1)(x^2+1)dx. This can be integrated by partial fractions or otherwise, so that I'(A) = - log(A+1)/[A^2+1] + \pi/4 * A/(A^2+1) + log 2/2 * 1/(A^2+1) We can integrate w.r.t A over [0,1] to get, via the fundamental theorem of calculus I(1) - I(0) = -I(1) + \pi/4 * log 2 Since I(0)=0, we get 2I(1) = \pi/4 * log 2, or I(1) = \pi/8 * log 2 ------------------------------------------------------------------------------ From: "Steven Taschuk" Date: 4 Dec 2005 14:39:31 -0800 Newsgroups: sci.math Integration by parts reduces the problem to evaluating I_1 = int_0^1 (arctan x)/(x+1) dx Substitute t = arctan x. int_0^{pi/4} (t sec^2 t)/(1 + tan t) dt Multiply and divide by 2 cos^2 t. int_0^{pi/4} 2t/(2 cos^2 t + 2 sin t cos t) dt Apply double-angle identities. int_0^{pi/4} 2t/(1 + cos 2t + sin 2t) dt Call this integral I_2. Now comes the trick (such as it is): substitute s = pi/4 - t. Then ds = -dt, but also the bounds are reversed; those two effects cancel each other. In the denominator, cos and sin trade places (by the complementary angle identities). Thus I_2 = int_0^{pi/4} (pi/2 - 2s)/(1 + cos 2s + sin 2s) ds = (pi/2) int_0^{pi/4} 1/(1 + cos 2s + sin 2s) ds - I and so I_2 = (pi/4) int_0^{pi/4} 1/(1 + cos 2s + sin 2s) ds Now undo the operations that led from I_1 to I_2; when you get back to the analogue of I_1, the arctan is gone and life is easy. ------------------------------------------------------------------------------ From: abhishekasth...@gmail.com Date: 4 Dec 2005 19:15:00 -0800 Newsgroups: sci.math The trig substituion x = tan(a), transforms the the integral to: I = Int^(0,pi/4) log(tan(a) + 1) da. Then a-->pi/4 - a gives I = Int^(0,pi/4) log(tan(pi/4 - a) + 1)da = int^(0,pi/4) log(2) da - I (by noting that tan(pi/4 - a) = (1 - tan a)/(1 + tan a) And so 2I = pi/4*log(2) so I = pi/8*log(2) ------------------------------------------------------------------------------ From: rob@trash.whim.org (Rob Johnson) Date: Mon, 05 Dec 2005 10:52:58 -0800 Newsgroups: sci.math I came up with a couple of methods that rely on cancelling parts that are not indefinitely integrable (at least not that I know of). Method 1 -------- Define |\1 log(1+tx) I(t) = | --------- dx \| 0 1+x^2 Then I(0) is 0 and I(1) is the integral we seek. Also, I'(t) |\1 x dx = | ------------- \| 0 (1+tx)(1+x^2) 1 |\1 x+t t = ----- | ( ----- - ---- ) dx 1+t^2 \| 0 1+x^2 1+tx 1 1 pi = ----- ( - log(2) + -- t - log(1+t) ) 1+t^2 2 4 So |\1 log(1+x) | -------- dx \| 0 1+x^2 = I(1) |\1 = I(0) + | I'(t) dt \| 0 |\1 1 1 pi = 0 + | ----- ( - log(2) + -- t - log(1+t) ) dt \| 0 1+t^2 2 4 pi pi |\1 log(1+t) = -- log(2) + -- log(2) - | -------- dt 8 8 \| 0 1+t^2 pi = -- log(2) - I(1) 4 Solving for I(1), we get |\1 log(1+x) pi | -------- dx = -- log(2) \| 0 1+x^2 8 Method 2 -------- Let x = tan(u): |\1 log(1+x) | -------- dx \| 0 1+x^2 |\pi/4 = | log(1+tan(u)) du \| 0 |\pi/4 = | ( log(cos(u)+sin(u)) - log(cos(u)) ) du \| 0 |\pi/4 1 = | ( log(cos(u-pi/4)) + - log(2) - log(cos(u)) ) du \| 0 2 |\pi/4 1 = | - log(2) du \| 0 2 pi = -- log(2) 8 ============================================================================== A-6 The answer is (n^2-2n)/2^{n-1}. The only solution posted to the sci.math newsgroup was contained in Dan Bernstein's TeX file of all solutions. (Links to this are also available at this site). ============================================================================== B-2 From: Gerhard Woeginger Date: Sun, 04 Dec 2005 20:06:23 +0100 To: rusin@cs.niu.edu Subject: Putnam B-2 The Cauchy-inequality yields (5n-4)*1 >= n^2, and hence (n-1)*(n-4)<=0. This implies 1<=n<=4. For n=1 and n=4, the Cauchy-inequality holds with equality. This yields n=1 and k_1=1, or n=4 and k_1=k_2=k_3=k_4=4 as solutions. For n=2, 1/k_1+1/k_2=1. This implies k_1=k_2=2, which does not satisfy k_1+k_2=6. No solution in this case. For n=3, 1/k_1+1/k_2+1/k_3=1 implies that the largest k_i, say k_1, is <=3. k_1=1 is impossible, and k_1=3 leads to k_2=k_3=3, which is no solution. Finally, k_1=2 leads to 1/k_2+1/k_3=1/2 and k_2+k_3=9. With k_2<=k_3, the possible cases are (k_2,k_3)= (2,7), (3,6), (4,5). Only (3,6) works out. Hence, n=3 and k_1=2, k_2=3, k_3=6 (plus all permutations) is a solution. ------------------------------------------------------------------------------ From: matthew_folz@hotmail.com Date: 4 Dec 2005 13:52:50 -0800 Newsgroups: sci.math Perhaps cleaner solutions to A5, B2, which I arrived at during the contest: B2: Expand the fraction and homogenize to get \sum_i x_i (\sum_i \prod_{j\not=i} x_i) = (5n-4) \prod_i x_i By the AM-GM inequality, the LHS is \geq n^2\prod_i x_i Since n^2\leq 5n-4 iff 1\leq n\leq 4, we see that the possible values of 1,2,3,4, and by the equality case of AM-GM, we get equality for n=1,4 iff all x_i's are equal If n=2, we get 1/x_1+1/x_2 = 1, x_1+x_2=6. No solutions If n=3, we get 1/x_1+1/x_2+1/x_3=1, x_1+x_2+x_3=11. The minimal x_i is \leq 3 by the first equation, and is not three by the second. So WLOG x_1=2. Then we get 1/x_2+1/x_3 = 1/2, x_2+x_3=9. Only solution in integers is x_2=3,x_3=6. Of course any permutation of 2,3,6 is a solution. We get 8 solutions in total. ============================================================================== B-3 From: "Harry Altman" Date: 4 Dec 2005 14:28:41 -0800 Newsgroups: sci.math A quicker solution I found for B3: Let g(x)=f(x)f(a/x). Then g'(x)=-af(x)f'(a/x)/x^2+f'(x)f(a/x)=-a/x+a/x=0. So we can write f(x)f(a/x)=b for some b, f(a/x)=b/f(x). Now differentiate *this* with respect to x; -af'(a/x)/x^2=-bf'(x)/f(x)^2, a/xf(x)=bf'(x)/f(x)^2, a/x=bf'(x)/f(x). So the left side is the derivative of a*log(x), the right side of b*log(f(x)), so writing a*log(x)+c=b*log(f(x)), we get f(x)=kx^r with k=exp(c/b), r=a/b. Obviously k,r>0; in the case r=1, the original relation gives us k=x/kx=1/k, so k=1 and we have the identity function. So it must be one of those. ============================================================================== B-4 From: pin...@gmail.com Date: 4 Dec 2005 02:37:51 -0800 Newsgroups: sci.math B4. As he said, there's a recursion. f(m,n) = f(m-1,n) + f(m-1,n-1) + f(m,n-1), and thus it's symmetric since f(1,x) = f(x,1) = 2x+1. To prove this recursion, for each n-tuple, define S as sum(|x_i|) (i.e. our restriction is that S =< m. If S= 0, call it Group B, and if S=m and x_n < 0, call it Group C. Group A n-tuples are exactly those counted by f(m-1,n). For every Group B n-tuple, x1,x2...x_{n-1} is counted by f(m,n-1). To go from a tuple in f(m,n-1) with sum S to one in f(m,n), let x_n = m-S (this will be nonnegative). For every Group C n-tuple, x1...x_{n-1} is counted by f(m-1,n-1). To go from a tuple in f(m-1,n-1) with sum S to one in f(m,n), let x_n = S-m (this will be negative). I got this by first figuring out f(4,5)=f(5,4)=681 before realizing it'd be fairly big, trying smaller numbers, noticing a potential pattern and seeing that it gave me 681 for f(4,5), so it was probably right. ------------------------------------------------------------------------------ From: "Steven Taschuk" Date: 4 Dec 2005 15:04:22 -0800 Newsgroups: sci.math Quoth David Rusin: > B-4. [...] But surely they had > in mind that we would define some set of objects and count its elements > in two ways, one yielding f(m,n), the other giving f(n,m). Here's one (somewhat clunky) way to do approximately what you propose here. Start with this simpler problem: count the number of n-tuples (x1,...,xn) such that x1 + ... + xn = m where x1,...,xn are nonnegative integers. Take m asterisks and n-1 pipes, and arrange them in some sequence. For m=7 and n=6, for example, we might have * | | * * * | | * | * * Treat the |s as separating values x1, x2, etc., those values given by the number of *s in their section. This arrangement corresponds to the tuple (1, 0, 3, 0, 1, 2) To get the number of solutions for the inequality x1 + ... + xn <= m but still with the requirement that x1,...,xn be nonnegative integers, just use n |s and don't associate the *s after the last | with any value in the tuple. (Those *s take up the slack.) To get the number of solutions for the inequality |x1| + ... + |xn| <= m where x1,...,xn are integers of any sign, attach a sign to every nonempty run of *s that occurs before the last |. For m=7 and n=5, for example, we might have (monospace font) + - - * | | * * * | | * | * * which corresponds to the tuple (1, 0, -3, 0, -1). To establish f(m,n) = f(n,m), take one of the signed */| sequences counted by f(m,n) and proceed as follows: Shift each sign from its run of *s to the subsequent run of |s. + - - * | | * * * | | * | * * Reverse the sequence. - - + * * | * | | * * * | | * Exchange * and |. - - + | | * | * * | | | * * | Here's one of the sequences counted by f(n,m); in this instance, the one corresponding to the tuple (0, 0, -1, -2, 0, 0, -2). (Note that in this example there is no slack; we happen to have =, not <.) This procedure is invertible (indeed, it is its own inverse), so it gives the desired bijection. (There are, of course, many details to take care of, but that's the idea.) ------------------------------------------------------------------------------ From: garretbf@mailbox.sc.edu Date: Mon, 5 Dec 2005 10:55:53 -0500 To: rusin@math.niu.edu Subject: Another solution to Putnam B4 Hi, I was searching the web for answers to the latest putnam and came across your website (http://www.math.niu.edu/~rusin/problems-math/). The proof of B4 I came up with while taking the test was different from any I saw on your page, so I thought I'd share: First, we'd like to model f(m,n) as the way to put m balls into n boxes, since there is a nice formula for this situation, namely (m+n)!/(m!*n!). Unfortunately this doesn't work since each non-empty box can be assigned either a positive or negative sign. Let k then represent the number of non- empty boxes. Obviously 0 <= k <= min(n,m) (since, you can't have more non-empty boxes than boxes and you can't have more non-empty boxes than balls). For a given k, there are (n Choose k) ways to select which boxes are non-empty. Each of the k non-empty boxes must have at least 1 ball in it. If we place one ball in those k boxes, that leaves (m-k) balls to be distributed among the k boxes. As we said earlier (and can be shown by the considering permutations of the form **||*|***|*), the number of ways to do this is (m-k + k)!/((m- k)!*k!) = m!/((m-k)!*k!) = (m Choose k). Now note that there are k boxes, each with two possible states, meaning there are 2^k ways to assign the signs. Thus, for a given k, the total number of possible states is (n Choose k)*(m Choose k)*2^k. Now we simply sum over all possible k's to find f(m,n). Simply, f(m,n) = SUM[k=0,min(n,m)] (n Choose k)*(m Choose k)*2^k. Now the symmetries make it abundantly clear that f(m,n) = f(n,m). That is: f(m,n) = SUM[k=0,min(n,m)] (n Choose k)*(m Choose k)*2^k = SUM[k=0,min(m,n)] (m Choose k)*(n Choose k)*2^k = f(n,m) -Ben Garrett ------------------------------------------------------------------------------ Newsgroups: sci.math From: Thomas Mautsch Date: 6 Dec 2005 01:24:08 +0100 > B4. For positive integers m and n, let f(m,n) denote the number of > n-tuples (x_1, xs_2, ..., x_n) of integers such that >|x_1| + |x_2| + ... + |x_n| <= m. Show that f(m,n) = f(n,m) . [ ... ] This can be solved by proving that the generating series F(x,y) := Sum_{m,n >= 1} f(m,n) x^m y^n converges on a certain domain of x's and y's, and is symmetric in x and y. This is quite straightforward: For fixed n, F_n(x) := Sum_{m >= 1} f(m,n) x^m is equal to F_n(x) = (1+2x+2x^2+...)^n (1+x+x^2+...) - 1 = ((1+x)/(1-x))^n/(1-x) - 1 (for |x|<1) Then: Sum_{n >= 1} F_n(x) y^n = x*(1+y)/(1-x-y-x*y)/(1-y) - x/(1-x) (for |x|,|y|<<1) x y (3 - x - y - x y) = ------------------------------------ (1 - x - y - x y) (1 - y) (1 - x) Hence, this term is the generating function F(x,y). From this F(y,x) = F(x,y) is obvious, and f(n,m) = f(m,n) follows immediately. ============================================================================== B-5. From: "D. J. Bernstein" Date: Sun, 4 Dec 2005 10:42:46 +0000 (UTC) Newsgroups: sci.math The only one bugging me at this point is B5. The example a x_1^3 x_2 x_3 + b x_1 x_2^3 x_3 + c x_1 x_2 x_3^3 shows that the multiply-and-differentiate matrix on the obvious basis doesn't necessarily have any zeros. Bigger examples show that the diagonal doesn't necessarily dominate. A nice factorization of the determinant doesn't leap out at me, although I haven't really tried examples. ------------------------------------------------------------------------------ From: "Igor Khavkine" Newsgroups: sci.math Date: 5 Dec 2005 09:10:26 -0800 First, note that the Laplacian maps homogeneous polynomials into homogeneous polynomials, reducing the degree by 2. If P(x) is not homogeneous, then it can be written uniquely as a sum of homogeneous ones. It is easy to convince oneself that the condition Lap(P(x))=0 can be imposed on each homogeneous part separately. Thus, WLOG assume that P(x) is homogeneous of degree k. Since R(x) = x_1^2 + ... + x_n^2 divides P(x), we can write P(x) = Q(x) R(x)^m, where Q(x) is homogeneous of degree k-2m and is no longer divisible by R(x). Use the Leibnitz rule to expand the Laplacian of P(x): Lap(P) = [ Lap(Q) R + 2 grad(R).grad(Q) + (4m(m-1)+2mn)Q ] R^(m-1), where I've used the fact that Lap(R) = 2n and grad(R)^2 = 4R. Note the combination grad(R).grad(...), expanded in coordinates it is 2(x_1 d/dx_1 + ... + x_2 d/dx_2). All homogeneous polynomials are eigenvectors of this operator, acting on Q it reduces to multiplication by 2(k-2m), twice the degree of Q. Requiring the Laplacian of P to vanish, we get the condition: [ Lap(Q) R + (4(k-2m) + 4m(m-1) + 2mn) Q] R^(m-1) = 0. It implies that, unless the coefficient in front of Q vanishes, Q must be divisible by R. But that is only possible if Q = 0. However, the said coefficient cannot vanish, since it is always positive (n>0 and m>=1, k>=2m). This is sufficient to show that P = 0. ==============================================================================