Spoilers to the Putnam '94 exam follow. Last year I commented that the questions were harder than usual; this year I think the reverse is true. I note in particular a paucity of geometry questions (which tend to be elementary but difficult) and of advanced undergraduate course questions (which tend to be easy if you've taken the right course). I think for typical undergraduates this test was pretty appropriate. I won't comment here on generalizations or connections with interesting theorems, although there are a number of interesting points to make. I posted solutions to sci.math for all but A6 and B4. I've incorporated responses from several other people as well as independent solutions from Dan Bernstein (who posted a complete set) when these improved or corrected mine. I adjusted the exposition a bit from the original post, but I'm not claiming these are either the clearest or the slickest proofs. --- dave rusin@math.niu.edu A1. Let S_n = a_{2^n}+...+a_{2^(n+1)-1}. Then the series is the sum of all the S_n. The given inequalities, added together, imply S_n < S_{n+1}. Hence the sum is larger than a sum of infinitely many a_1's, which diverges. A2. Apply a linear transformation which transforms the ellipse to a circle: f(x,y) = (x/3, y) will do. This also carries lines through the origin to other such lines; the lines in question go to y=(3/2)x and y=(3m) x respectively. The effect on all areas is to multiply them by det(A)=(1/3), but in particular equal areas stay equal.So the question is how to make the lines y=(3/2)x and y=(3m)x subtend equal portions of a circle with the two axes. Clearly (interchanging x and y) the second line ought to be x=(3/2)y, i.e. y=(2/3) x. So it would appear that m=2/9 is needed. Noam Elkies adds: Simpler yet: apply the linear transformation g(x,y)=(3y,x/3). This preserves areas, preserves (x^2)/9+y^2 and thus the ellipse, switches the x and y axes, and takes y=3x/2 to the desired line all in one step. A3. (The solutions I posted was faulty but in the right direction. This correction is based on Bernstein's posted solution.) Suppose not. Then there is a coloring with 4 colors in which all the points of each color lie strictly closer than D=2-sqrt(2) apart. Consider the three vertices v1 (where the 90-degree angle is), v2, and v3. Let the points p2 and p3 be as follows: p_i is on the line segment joining v_i to v1, and is of distance D from v_i. Likewise let q_i be the points on the hypotenuse of distance D from v_i Many pairs of these are of distances at least D apart and so are of different colors. In particular, the vertices must be of three different colors, say colors 1, 2, and 3 at v1, v2, and v3 respectively. The point p2 is too far from v2 or v3 to have the same color as those points, and so is of color 1 or 4. The same is true of p3, but d(p2, p3) = D, so these two are of different colors, say, p2 is of color 1 and p3 is of color 4. By the same reasoning q2 and q3 are of colors 1 or 4, but since d(p2, q2) = D [proof: v2, p2, q2, and p3 form a rhombus] the choice must be such that p2 has the same color (1) as q2. Now we have a contradiction since v1 and q2 are too far apart to have the same color. A4. Let f(r)=det(A+rB). This is a quadratic polynomial in r. Now, since A+rB is integral with integral inverse, for several r, it follow the determinants of these matrices have the same property, i.e. are +1 or -1. But by pigeonhole principle, at least one of these values must be obtained 3 times or more, which is impossible for a non-constant polynomial of degree <=2. Hence f(r) is constant, i.e. identically +1 or -1. Either way, we then have (A+rB)^-1 = f(r)^-1. adj(A+rB), which is another integral matrix; this applies to all r, including of course r=5. A5. For any integer N >= 1, let S_N be the set of all sums of N r_i's; S_1994 is the set S of the problem. We will show each S_N has the desired property, by induction on N. For N=1 this is trivial: if b<0 then any (a,b) doesn't meet S_1 at all; if b>0 then by passing to a subinterval we may assume a>0 too. Then there are only finitely many r_i greater than a, so among all of these let d = max (r_i - a). Then (a,b) contains the interval (a, min(b,d) ) which does not meet S_1. Now assume S_N has the desired property and assume (a,b) is given. Find in it an interval (c,d) not meeting S_N. Let e = (c+d)/2 and consider the right half-interval (e,d). No number in here can be written as a sum of N+1 r's in which the last one is very small (less than d-e), since that would require the sum of the first N terms to be in S_N and in (c,e), contrary to the construction of (c,d). Now, it is quite possible that (e,d) meets S_{N+1} by containing sums the last term of which is one of the remaining r's which happen to be larger than (d-e), but there are only finitely many such r's to consider. Within (e-r1, d-r1), for example, we find by induction an interval (x,y) not meeting S_N; then (e'=x+r1, d'=y+r1) is a subinterval of (e,d) not containing any sums in S_{N+1} in which the last term happens to be r1. Repeating likewise we find a subinterval (e'', d'') of that containing no elements of S_{N+1} in which the last term is either r1 or r2. Iterating likewise for all the r_i's larger than e-d, we arrive at an interval containing no elements of S_N in which the last term is larger than e-d and, as we have already shown, none with last term less than e-d either. Noam Elkies adds: The key is to use that a finite union of nowhere-dense sets in R is nowhere dense to prove that if A is nowhere dense and r_n->0 then A+{r_n} is nowhere dense. In particular it follows by induction that B+B+B+...+B (1994 times) is nowhere dense where B={r_n}. (Noam is referring to the Baire Category Theorem) A6. W Jose Castrellon G solves as follows: A-6 - By contradiction. If there are two compositions that work with both e_10 = 0 and 1 then f_10 must map A to itself. Continue by induction for f_9... Then they all leave A fixed, so the combination in the hyp couldn't exist. So for each pair, one of them doesnt work, i.e. at most 512 D. J. Bernstein' solution clarifies the conclusion better, I think: ...So every f_i maps A to A. If 0 is in A, select not in A; it is impossible for a composition of f_i's to take 0 to n. If 0 is not in A, select n in A; it is again impossible for a composition of f_i's to take 0 to n. B1. If n is any positive integer, find the least square a^2 which is within 250 of it, that is, a^2 >= n-250 but (a-1)^2 < n-250. Then n is in the solution set of this problem if and only if (a+14)^2 <= n+250 but (a+15)^2 > n+250. [We are assuming a>1 here. If a=0, the second inequality has to be dropped, but no solutions n exist with a=0 anyway, since the last inequality would require 225 > n + 250, and we are given that n is positive.] Subtracting appropriate pairs shows that if n is a solution then 28a+196 <= 500 and 32a+224 > 500 which, for integral a, mean 9<= a <= 10. Taking a=9 shows that n must satisfy the inequalities n<=331, n>314, n>=279, and n<326, that is, n=315,...,325. Likewise, taking a=10 shows the corresponding values of n to be n=331,..., 350. Thus the complete solution set is n=315, ..., 325, 331, ..., 350. B2. We concentrate on the related question, for which values of p does f(x) = x^4 + 2p x^2 + q x + r have four distinct roots for some q and r. Clearly, if p<0, then we can choose q=0 and r a positive number less than |p|^2; then f has the four distinct roots +- sqrt( |p| +- sqrt( |p|^2 - r ) ). On the other hand, if p>=0 then the slope s(x)=4x^3+4px+q is increasing (s'(x)=12x^2+4p>=0) and so never takes the same value twice; if there were three roots, we would be able to apply Rolle's theorem twice to find two zeros for s. Thus, for such p, our f has at most 2 roots. The same reasoning works with quartics with non-zero coefficients of x^3, but it is easier to use a translation left or right to reduce to the previous case. Thus the polynomials g(x)=x^4+9x^3+cx^2+qx+r (with c fixed) include some with four distinct roots iff the g(x-9/4)=x^4+(c-243/8)x^2+... do. From the preceding paragraph this requires precisely that c<243/8. It is clear that finding such a g is equivalent to finding a line meeting the given quartic in 4 distinct points, so for the original problem the answer is again c < 243/8. [Other solutions allow some variety in determining when a quartic has four roots. Variants of the Mean Value Theorem, roots of the second derivative, Descartes' Rule of Signs, Sturm sequences, and so on could be used.] B3. The k's in question are the k<1. Suppose that k<1 and that f is as stated. Then f>0 so we can consider g=ln(f) - x, also differentiable for all x, and having g'(x) = f'(x)/f(x)-1>0. Thus g is increasing, and so must cross the graph of any straight line with negative slope. Hence if k < 1, then for all x's larger than some N (depending on g and k of course) we will have g(x) > (k-1)x, which means ln(f(x)) > k x, which is the desired conclusion. Now suppose k >=1; we can build on the previous example and take g to increase to the horizontal axis, say g(x) = -e^(-x). Then f(x) = exp(x-e^(-x)) has f'(x) = f(x).[ 1 + e^(-x) ] > f(x) but f(x)> e^(kx) requires x-e^(-x) > kx = x + (k-1)x, which is not true for any positive x. B4. Adapted from solutions by W Jose Castrellon G and D. J. Bernstein: First observe by induction that all powers are of the form A^n= [m p] [2p m] We will find integers x and y so that either m+1 = 2x^2 , m-1= y^2 and p = xy, or m+1 = x^2, m-1= 2y^2 and p = xy. The first condition will hold for the even powers of A (starting with x=3, y=4 for A^2), the other condition for the odd powers (starting with x=2, y=1 for A^1). It is awkward to determine a pattern for x and y, because the conditions alternate with the powers of A. However, there is a linear pattern for the x and y needed for _every other_ power of A: indeed, if x'=3x+2y and y'=4x+3y, then from m+1=2x^2, m-1=y^2, p=xy we obtain 2(x')^2 = 17m+24p+1 = m'+1 (y')^2 = 17m+24p-1 = m'-1 (x')(y')= 12m+17p = p' where m' and p' are the entries in the top row of A^(n+2). A similar pattern holds when we begin with m+1=x^2, m-1=2y^2, p=xy. Since x, y >0 we have by induction that x>0, y'>3y>0, so that the set of such elements y increases without bound. On the other hand, it is clear that y divides all four entries m-1, p, 2p, and m-1 of A^n. Thus the gcd's go to infinity. [Remark: I found it hard to start this problem. The key observation is that det(A)=1 => det(A^n)=1, so m^2=2p^2+1, i.e., (m-1)(m+1)=2p^2. Then unique factorization shows such x and y must exist, and moreover shows that the gcd in question is either y or 2y. Knowing that a linear recurrence for x and y ought to exist, it's easy to find what coefficients to choose.] B5. [Write A for \alpha]. Take A = e^(-1/n^2). Note that if 0< r <=1, 1-r+r^2/2 > e^(-r) > 1-r, so that in particular if 0 < k <= n we have n^2(1-k/n^2 + k^2/(2n^4)) > A^k n^2 > n^2(1- k/n^2). The ends simplify to n^2 - k + (1/2)(k/n)^2 and n^2-k respectively. The latter is an integer and the former exceeds it by at most 1/2, so since A^k n^2 lies between them, the greatest integer therein is indeed n^2-k. Thus the second inequalities hold. On the other side, note A(n^2-k) > (1-1/n^2)(n^2-k) = n^2-(k+1)+k/n^2 is greater than n^2-(k+1), but (as A<1 ) is less than n^2-k, so the greatest integer here is n^2-(k+1). By induction we get the inequalities on the left. B6. Given this congruence mod 10100, the same congruence holds mod 100; but mod 100, n_a =a, so the resulting congruence may be written a+b = c+d (mod 100). Likewise reading mod 101 we get 2^a+2^b = 2^c+2^d (mod 101). Now, 101 is prime so (using Fermat's congruence) the first of our conclusions implies 2^(a+b) = 2^(c+d) mod 101, i.e. 2^a.2^b =2^c.2^d. Thus the pairs { 2^a, 2^b} and {2^c, 2^d} (mod 101) have the same sums and products, and so are roots of the same quadratic equation. Since again Z/101 is a field, that means these pairs of roots must be equal. Fortunately (since neither 2^50 nor 2^20 = 1) 2 is a primitive root mod 101, so these congruences say the pairs {a,b} and {c,d} are equal mod phi(101)=100. Since 0 <= a b c d < 100, these congruences may be read as actual equalities among integers. Dan Bernstein included the computations I skimmed over: modulo 101, 2^10=1024=14, 2^20=196=-6, 2^40=36, and 2^50=36.14=504=-1.