The following is an email message (actually, a concatenation of two messages) I sent out after the 1993 Putnam. It includes more or less complete solutions of all of the problems, but I make no claims for readability (nor for my alleged "alternate" solution of A5). ------ A1: Find t > 0 such that \int_{0}{t}{f(x) - f(t) dx} = 0, where f(x) = 2x - 3x^3. The solution comes out to be t = 2/3, and c = f(t) = 4/9. A2: Since the terms are nonzero, we can define a_n = (x_{n+1} + x_{n-1})/x_n for n \geq 1. It suffices to show a_1 = a_2 = \cdots. But x_{n+1}^2 - x_nx_{n+2} = 1 = x_n^2 - x_{n+1}x_{n-1} x_{n+1}(x_{n+1} + x_{n-1}) = x_n(x_n + x_{n+2}) x_{n+1}(a_nx_n) = x_n(a_{n+1}x_{n+1}) a_n = a_{n+1} since x_n, x_{n+1} \neq 0. The result follows by induction. A3: The functions f biject to tuples (j, S_{j+1}, \dots, S_m) such that S_{j+1} \subseteq \cdots \subseteq S_m. The bijection is, j is the minimum value of f and S_{i} for j+1 \leq i \leq m is the intersection of all sets A such that f(a) \leq i. But for fixed j, those in turn biject to functions from {1, \dots, n} to {j+1, \dots, m+1}. The bijection is, the function gives the smallest i such that n \in S_i, or m+1 if i \notin S_m. And the number of such functions is (m-j+1)^n. Summing that gives the desired result. A4: Don't you love it when they give problems you've seen at MOP? (Very same problem, MOP 1990.) Anyway, assume W/oLOG that the sum of the x_i is less than or equal to the sum of the y_i. (I'm not going to use the numbers 19 or 93, so it's okay. In fact, I'll write p and q since I can't remember whether the x's are less than 19 or 93. So x_1, \dots, x_p \leq q and y_1, \dots, y_q \leq p.) For m = 0, \dots, p, let f(m) be the largest n such that x_1 + \cdots + x_m - y_1 - \cdots - y_n is nonnegative. Let g(m) be the value of this difference. (Note: f(0) = g(0) = 0.) We claim g(m) < p for all m. Indeed, f(m) < q, because the sum of all the x's is less than the sum of all the y's. So x_1 + \cdots + x_m - y_1 - \cdots - y_n - y_{n+1} < 0 by assumption. But y_{n+1} \leq p; adding that to both sides gives g(m) < p. So for each of 0, 1, \dots, p, g(m) takes a value in \{0, \dots, p-1\}. By the Pigeonhole Principle, there are m < m' such that g(m) = g(m'). But now x_{m+1} + \cdots + x_{m'} = y_{g(m)+1} + \cdots + y_{g(m')}. A5: The key is that the upper and lower limits of integration are related by the transformation x -> 1/(x-1). (Remember this transformation has period 3.) Moreover, x^3 - 3x + 1 is basically preserved by this (up to a power of x-1, but in the integral, you get 4 powers of x-1 from the numerator and 2 from dx, clearing the 6 from downstairs.) First solution: Use the transformation to combine all three integrals into one integral from, say, -100 to -10, of some quartic over (x^3 - 3x + 1)^2. Then discover this happens to work out nicely. (I don't recall to what, as I didn't do this.) Second solution (mine): Let $f(x) = (x^2 - x)^2 / (x^3 - 3x + 1)^2$, $P(x) = x^3 - 3x + 1$, $Q(x) = 1/(x-1)$. Let r_1, r_2, r_3 be the roots of $P$; note Q permutes them. In particular, the Galois group of Q(r_1, r_2, r_3) (that's Q the rationals, of course) is cyclic. More on this later. Let $g(x)$ be an antiderivative of $f$ and let $h(x) = g(x) + g(P(x)) + g(P(P(x)))$. We claim $h$ is a rational function with rational coefficients (up to a constant of integration), which will solve our problem. Write f in its partial fraction decomposition A/(x - r_1) + B/(x - r_2) + C/(x - r_3) + D/(x - r_1)^2 + E/(x - r_2)^2 + F/(x - r_3)^2. Observe that g(x) = A log x - r_1 + B log x - r_2 + C log x - r_3 - D/(x - r_1) - E/(x - r_2) - F/(x - r_3) (where I have to make some arbitrary choice about where not to define log on the complex plane; no matter). That means h(x) = (A + B + C)(log x - r_1 + log x - r_2 + log x - r_3) + (D + E + F)(1/(x - r_1) + 1/(x - r_2) + 1/(x - r_3)). (I've long since dropped the constant of integration.) But A + B + C = 0 from the partial fraction decomposition (A + B + C is the coefficient of x^5 in the numerator of f(x)). So h(x) = (D + E + F)(1 /(x - r_1) + 1/(x - r_2) + 1/(x - r_3)). The inside is just P'(x) / P(x), which is clearly a rational function with rational coefficients. So we need only show D + E + F is rational. We could actually just compute it, but why bother? When you apply an automorphism t of Q(r_1, r_2, r_3) to the coefficients of f, they're unchanged. But t(D) becomes the coefficient of, say, 1/(x - r_2)^2, so t(D) = E and similarly. The point is, D, E, F are conjugates, so the trace of D, which is rational, is just D+E+F. And I'm done. (Whew! The point is, my solution works for any quartic function in the numerator of the integrand.) A6: Keep in mind I was guided through this solution by previous knowledge of problems of this ilk. Maybe you'll see what I mean in a moment. The fact that $n = 1 + [rm]$ gives precisely the locations of the 2's in the sequence is equivalent to the following fact: [rn] - [r(n-1)] = 3 if n = 1 + [rm] for some m 4 otherwise. (The point is that the locations of the 2's are just 1 + [rn] for n = 0, 1, 2, \dots.) This in turn is equivalent to the following pair of facts: (i) 3 < r < 4 and r is irrational; (ii) r(n-1) - [r(n-1)] < 4-r iff n = 1 + [rm] for some m. Again we rewrite the second condition to say: There exists an integer s such that 0 < r(n-1) - s < 4-r iff there exists an integer m such that 0 < rm - (n-1) < 1, that is, such that 0 < (4 - r)rm - (4 - r)(n-1) < 4-r. To find such r, we might as well just try setting r(n-1) - s = (4 - r)rm - (4-r)(n-1) which is to say 4(n-1) = s + (4 - r)rm. And we claim here s is an integer iff m is an integer. Well, that's guaranteed if (4 - r)r = 1, that is, r^2 - 4r + 1 = 0. (We choose 1 instead of -1 so that 3 < r < 4). The larger root of this is 2 + \sqrt 3 (NOT 2 + \sqrt 7, as I stupidly wrote while finishing this up in the last two minutes!) and by the equivalences, that r satisfies the claim. B1: The smallest such n is 3987. (Why can't I add? Just like last year, I add 1993 and 1994 and get 3997. At least I was consistent about it.) n can be no smaller because 1992/1993 < k/n < 1993/1994 must be soluble for some k. Put j = n - k; then 1/1994 < j/n < 1/1993, which implies 1993j < n < 1994j. That's insoluble for j = 1, so j must be at least 2, hence n is at least 3987. On the other hand, one can show for 0 < m < 1993, m/1993 < (2m+1)/3987 < (m+1)/1994. B2: A never wins with perfect play by B. The simple reason is that B can always guarantee that A will not win on the immediately following move. Why? B holds one more card than A, and each of A's cards can cause only one of B's cards to be a fatal play. Hence B has at least one safe play. (Of course, B wins on the last move if not at any earlier point since the sum of all cards is n(2n+1).) B3: The closest integer to x/y is even iff 0 < x/y < 1/2 or (4n-1)/2 < x/y < (4n+1)/2 for some integer n \geq 1. The former occurs inside the triangle (0,0), (0,1), (1/2, 1), whose area is 1/4. The latter occurs inside the triangle (0, 0), (1, 2/(4n-1)), (1, 2/(4n+1)), whose area is 1/(4n-1) - 1/(4n+1). So the total area, which is the same as the probability in a uniform distribution, is 1/4 + 1/3 - 1/5 + 1/7 - 1/9 + \cdots. But we know \pi / 2 = 1 - 1/3 + 1/5 - 1/7 + cdots. (Say, from the series expansion of arctan x. Yet ANOTHER place where Kiran made a calculation error, dropping the 2 here.) So the final answer is 1/4 + (1 - \pi / 2) = 5/4 - \pi/2. B4: No one seems to have solved this. Noam Elkies claimed a solution afterwards, but I didn't follow it. The idea is to consider the linear operator Tf(x) = \int_{0}^{1}{f(y)K(x,y) dy}. Life is MUCH easier if K(x, y) = K(y, x); because then this operator is self-adjoint under the usual inner product (f,g) = \int_{0}^1{f(x)g(x) dx}. But that's too much to ask for. B5: All solutions involve diddling with some sort of modulus, mostly mod 8 (since all odd squares are 1 there). My method: write out the three cosines at one of the points in terms of the lengths. Then relate them using the cosine addition formula cos A+B = cos A cos B - sin A sin B. The sine terms give you a humongous radical, but you can show that the two terms under the radical are congruent to 3 mod 16, so the product is congruent to 9 mod 16, and so the square root, which must be an integer as it turns out, is +-3 mod 8. That ends up being a contradiction. Aforementioned nice solution (due to Manjul Bhargava, the aforementioned score of 7): Recall the formula for the volume of a tetrahedron in terms of its six edges. (Or derive it. It comes to, V^2 is a five by five determinant with fairly well-behaved entries. I think everything in there is a square.) Then just prove mod 8 that the determinant is nonzero, so the volume is nonzero, and the four points are not coplanar. B6: No idea, sorry. The trouble is, some moves are reversible. Worse, you can't always win just by making nonreversible moves. (From 1, 2, 4, you must make the reversible move to 2, 2, 3 to win.) Argh! Enjoy... Kiran P.S. I should point out the reverse of the first bijection in A2. Given j, S_{j+1}, \cdots, S_n, let f(A) be the maximum i such that S_i \subseteq A. (Set S_j = the empty set to make this work in all cases.) Also, I should point out why B4 is easy if K is symmetric. That makes T self-adjoint. But since K is positive, T is positive definite with respect to the given inner product, so all its eigenvalues are positive. However, T(f - g) = g - f. Thus f - g = 0 otherwise f-g would be an eigenvector of value -1, which is not allowed. (I'm actually not so sure about the positive definiteness. Hmm. Let me get back to you all on that.) ------ I've just learned these solutions to B4 and B6. (Both solutions devised shortly after the exam.) B4: Let T be the operator I alluded to earlier. Notice that if h is nonnegative and not identically zero, then Th is positive everywhere. Now consider the expression f - rg. Clearly T^2(f - rg) = f - rg. Let r be the smallest real such that f - rg is nonnegative; that means it has a zero somewhere. But T(f - rg) is strictly positive unless f - rg = 0, so T^2(f - rg) = f - rg is too, contradiction. So f - rg = 0. That means Tf = Trg = rTg = rf, and T^2f = r^2f = f. So r^2 = 1, and since r >= 0, r = 1, and we're done. (Sorry. I meant r is the biggest real such that f - rg is nonnegative. Clearly r >= 0.) B6: I haven't sorted this out yet. But the idea is to show that, assuming we never reach a zero doing this, that if two of x, y, z are divisible by 2^n, we can reach a state where two are divisible by 2^{n+1}. Since x + y + z is fixed, this will give a contradiction. Clearly we can assume x+y+z is odd (otherwise just move to make all three even and pretend we're working with half the numbers involved, and repeat), and that two of x,y, z start out even (just move two odd ones otherwise). So we start with n = 1. Lemme see if I remember this. The result is trivial if both of the multiples of 2^n are divisible by 2^{n+1}, or if neither is (they both will be after one move on them). So assume one is a multiple of 2^{n+1} and the other is not. So mod 2^{n+1}, the numbers are 0, 2^n, x, where x is some odd number. Move on the 0 and x until the 0 is larger. (This happens sooner or later since it isn't ACTUALLY zero, and clearly as long as the 0 is smaller the congruence mod 2^{n+1} is preserved.) Then move on them once more to get 2x, 2^n, -x (still modulo). If the 2^n is larger than the -x, we move them to 2^n + x and -2x. Repeated moves now on 2x and -2x eventually produce 0, 0 (regardless of which is bigger!). So suppose the 2^n is less than the -x. Move them anyway to get 0, 2^n - x (remember 2^n = -2^n mod 2^{n+1}). So we have 0, 2x, 2^n - x. Move the 0 and the 2^n - x until the 0 is bigger, then move once more to get -2x, 2x, 2^n + x. Again move 2x and -2x until both become 0, and the induction follows. (Both solutions due to Dylan Thurston, who, like everyone else, seems to have solved about six questions.) Kiran Come to think of it, I'm no longer convinced my A5 actually works. Certainly the claim I make in the middle about the integrand coming out to that nice pair of terms when you put in x, 1/(1-x) and 1 - 1/x is false. I still believe the result holds with any quartic polynomial on top (of course you need only check five examples to prove or disprove this) but I don't claim to have a full proof of that. So that means my score should most properly be pegged at "9-something", namely A1, A2, A3, A4, A6, B1, B2, B3, B5, maybe some scraps on A5, and nothing on B4 or B6. Kiran