Solutions to the Problems of the 1994 William Lowell Putnam Mathematical Competition by Kiran Kedlaya (kedlaya@math.harvard.edu) Disclaimer: These are mostly the solutions I submitted, with occasional replacements when I found out about something prettier. I've used TeX-style notation, but the file isn't TeX-ready. (A lot of dollar signs are missing, for one thing.) A1: Let s_1 = a_1, s_2 = a_2 + a_3, s_3 = a_4 + a_5 + a_6 + a_7, etc. Since all terms are positive, the sum a_1 + a_2 + ... can be rewritten as s_1 + s_2 + .... But for any n, s_n = a_{2^{n-1}} + ... + a_{2^n - 1} <= (a_{2^n} + a_{2^n + 1}) + ... + (a_{2^{n+1} - 2} + a_{2^{n+1}-1} = s_{n+1}. Since s_1 = a_1 > 0, the terms of s_n aren't going to 0, so the sum diverges. A2: Remember that area ratios are preserved by affine projection. In particular, let x' = x/3, y' = y. Then the problem is to find m such that the area of the region in the first quadrant bounded by the line y' = 3x'/2, the x'-axis, and the circle x'^2 + y'^2 = 1 is the same as the area of the region in the first quadrant bounded by the line y' = 3mx', the y'-axis, and the circle x'^2 + y'^2 = 1. By the symmetry of the diagram, it's clear that the slopes should be reciprocal; i.e. 3m = 2/3, so m = 2/9. A3: Suppose such a coloring exists; let A be the right-angle vertex and B, C the other two vertices. Choose D on side AB so that BD = x, where hereafter x = 2 - \sqrt 2; choose E on side AC so CE = x. You can easily check that also DE = x. It follows that any two of B,C,D,E are at distance at least x, so they are of four different colors, say 1,2,3,4, respectively. A must be one of these colors; but AB = AC = 1 > x, so A is colored 3 or 4. Without loss of generality say A is colored 3. Put F on side BC so that BF = x; then BDEF is a parallelogram, so EF = x, and clearly CF > x. Thus C can't be colored 1, 2 or 4, so C is colored 3. But A and C have the same color and AC is at least the altitude from A, which is \sqrt{2} / 2 > x. Contradiction. Aside: this coloring can be completed so that no two points of the same color are at distance strictly greater than x. Draw a disk of radius x around B; use color 1 for its intersection with the triangle. Do the same around C in color 2. Color triangle ADE (minus points D and E) in 3, and the rest in 4. A4: First recall that an integer matrix A has an integer inverse if and only if det A = +- 1. Proof: clearly if A^{-1} has integer entries, then 1 = det AA^{-1} = det A det A^{-1} so det A divides 1. Conversely, if det A = +- 1, A^{-1} equals 1/det A times the signed cofactor matrix of A, which has integer entries. So let f(n) = det A + nB. Clearly f is a quadratic polynomial in n with integer coefficients (just write it out in terms of the entries); our claim is that if f(i) \in {1, -1} for i = 0, 1, 2, 3, 4, then f(n) = +- 1 for all n. Note that since f has integer coefficients, x - y divides f(x) - f(y) for any integers x and y. (If f(x) = a_nx^n + ... + a_0, then f(x) - f(y) = a_n(x^n - y^n) + a_{n-1}(x^{n-1} - y^{n-1}) + ... and each term is divisible by x - y.) But if x and y both belong to {0, 1, 2, 3, 4} and |x-y| > 3, then |f(x) - f(y)| \leq |f(x)| + |f(y)| = 2, so f(x) - f(y) must be 0. Using this, we conclude f(3) = f(0) = f(4) = f(1) (apply what I just said to the two sides of each equality). Thus the quadratic polynomial f(n) - f(1) has four zeroes; that's too many, so it must be the zero polynomial, and f(n) = f(1) = +- 1 for all x. Aside: A, ..., A+3B is not enough: put A = -1 1 and B = 1 0 1 -2 0 1. A5: Let A be the set of all numbers representable as a sum of 1994 OR FEWER distinct elements of the sequence. I claim A is the closure of S. Proof: Given a sequence of tuples (i_1, ..., i_1994) such that r_{i_1} + ... + r_{i_{1994}} converges, either the sequence of values of i_1 takes some value infinitely often, or each value only occurs finitely often, so the sequence of r_{i_1} values converges to 0. In the former case, pass to a subsequence for which i_1 is constant, in the latter case keep the same sequence. Repeat this operation for i_2, ..., i_{1994}. The result is a sequence with r_{i_1} + ... + r_{i_{1994}} converging to the same limit, but each term either is constant or goes to 0. So the limit is clearly the sum of the constant r_{i_k} terms, so belongs to A. (Conversely, every element of A is the limit of terms of S, but I don't need that.) But A is a countable set, and (a, b) is uncountable. Thus some point c in (a, b) is not in A; that means that some small interval around c contains no points of S. Take d > c inside that interval; then (c, d) is what we want. A6: Let F_i = the "set" of functions f_i^{e_i} \circ ... \circ f_10^{e_10}. Assume more than half of F = F_1 fixes some set A. We shall prove the following statements simultaneously by induction: P_i: f_i maps A to A. Q_i: More than half of F_i fixes A. The implication will be Q_1 -> P_1 -> Q_2 -> ... -> P_10, where Q_1 holds by assumption. So first we assume Q_i. By the pigeonhole principle, there are two functions in F_i that differ only in their value of e_i. Call them g and f_i \circ g. Then f_i(A) = (f_i \circ g)(g^{-1}(A)) = (f_i \circ g)(A) = A, so P_i holds. Now assume P_i and Q_i. Since f_i(A) = A, if f_i^{e_i} ... f_{10}^{e_{10}} maps A to A, so does f_{i+1}^{e_{i+1}} ... f_{10}^{e_{10}}. Since every function of the latter form comes from exactly two functions of the former form, and more than half of F_i fixes A, more than half of F_{i+1} fixes A also. Hence all the f_i fix A. But then if 0 is in A, no composition of the f_i will map it to anything not in A, and vice versa. Contradiction. Aside: A does not have to be finite as long as it is not all integers. Equality occurs for f_1(n) = n+1, f_2(n) = n-1, and the rest are the identity function. (Or f_1 maps 0 -> 1 -> -1 -> 2 -> -2 ... and the rest are the identity map.) B1: What a mess! First note that if m >= 11, then (m + 14)^2 - m^2 = 28m + 196 >= 308 + 196 > 500. So no number can be within 250 of 15 squares if the smallest one is 11^2 or greater. Hence all "good" numbers are at most 10^2 + 250 = 350. Now just count: 0 <= n <= 250: within 250 of 0^2, ..., 15^2 and maybe more. No good. 251 <= n <= 299: within 250 of 7^2, ..., 22^2 and maybe more. No good. 299 <= n <= 314: within 250 of 8^2, ..., 23^2. No good. 315 <= n <= 325: within 250 of 9^2, ..., 23^2. Good. 326 <= n <= 331: within 250 of 9^2, ..., 24^2. No good. 331 <= n <= 350: within 250 of 10^2, ..., 24^2. Good. So the good n are 315, ..., 325, 332, ..., 350. B2: The desired c are all those less than 243/8. First note that a necessary condition is that the second derivative is not everywhere nonnegative, or else the graph is convex and any line meets it at most twice. So the polynomial 12x^2 + 54x + 2c has negative discriminant, i.e. 54^2 > 4(24 c), which reduces to c < 243/4. In that case the second derivative has two distinct zeroes, corresponding to inflection points of the curve. Draw the line through these two points. Note that the slope decreases between the two points (since the curve is concave there) and equals the slope of the line somewhere in the middle (by the Mean Value Theorem). Hence the slope of the curve is greater than that of the line at the first point, and less at the second. This means the curve lies below the line just before the first point and just after the second; by continuity, the curve must intersect the line again before the first point and after the second. B3: The desired k are those less than 1. First we show that k < 1 all work. We have f'(x)/f(x) > 1 for all x. Integrating from 0 to 1 gives log f(x) - log f(0) > x, so log f(x) > x + log f(0). Clearly this eventually exceeds kx for fixed k < 1, so for large x, f(x) > e^{kx}. Now we show that k = 1 (and hence anything larger) does not work. Let f(x) = exp (x - g(x)), where g(x) is everywhere positive and decreasing. (I used g(x) = e^{-x}.) Then f'(x) = (1 - g'(x)) exp (x - g(x)). Since g'(x) < 0 for all x, f'(x) > exp (x - g(x)) = f(x). However, since g(x) > 0 for all x, f(x) < e^x for all x. B4: By induction one easily shows that A has the form a_n b_n 2b_n a_n for all n, where a_n is odd. And a_n^2 - 2b_n^2 = det A^n = (det A)^n = 1. Thus (a_n + 1)(a_n - 1) = 2b_n^2. The greatest common divisor of the terms on the left divides their difference, namely 2. For the same reason, one of the terms on the left is divisible by 2 but not by 4. Dividing that term by 2 leaves two relatively prime integers whose product is b_n^2, a perfect square. Hence each of the two is a perfect square. That means either \sqrt{a_n - 1} or \sqrt{(a_n - 1)/2} (depending on which term the 2 came out of) is an integer and a divisor of b_n. So d_n >= \sqrt{(a_n - 1)/2} -> infinity. Aside: one can show (as I did) that a_{2n}-1 and b_{2n} are divisible by b_n, and that a_{2n-1}-1 and b_{2n-1} are divisible by 2 b_n - a_n. I do this by solving a recurrence relation for a_n and b_n. In fact, a_n + b_n \sqrt{2} = (3 + \sqrt{2})^n. B5: Notation: [a] denotes the greatest integer less than or equal to a. It turns out alpha = 1 - 1/(n^2) works. One checks that for k = 1, ...,n^2, [k alpha] = [k - k/n^2] = k-1, so f^k (n^2) = n^2 - k, as desired. We also want to show that [alpha^k n^2] = n^2 - k, i.e. n^2 - k <= (1 - 1/n^2)^k n^2 and (1 - 1/n^2)^k n^2 < n^2 - k + 1, or 1 - k/n^2 <= (1 - 1/n^2)^k and (1 - 1/n^2)^k < 1 - (k-1)/n^2 for k= 1, ..., n. The first inequality follows from Bernoulli's inequality: if x > -1 and k > 1, then (1 + x)^k >= 1 + kx. This is because (1 + x)^k is a convex function and y = 1 + kx is the tangent to the curve at x=0. Apply Bernoulli to x = -1/n^2 to get what we need. The second inequality follows from a sort of reversed Bernoulli's inequality: if 0 < x < 1 and k > 1, then (1 - x)^k < 1 - kx + k(k-1)x^2/2. (All I did was pull out the first three terms of the power series.) I have no better proof of this than calculus: define f(x) = 1 - kx + k(k-1)x/2 - (1-x)^k; then f'(x) = k(k-1)x - k + k(1 - x)^{k-1} f''(x) = k(k-1) - k(k-1)(1-x)^{k-2} > 0 since 1 - x < 1. Moreover f(0) = f'(0) = 0. Since f''(x) > 0, f'(x) is increasing. It starts at 0, so it must be positive. Thus f(0) is increasing, and it too starts at 0, so it must be positive. Putting in x = 1/n^2 gives (1 - 1/n^2)^k < 1 - k/n^2 + k(k-1)x/(2 n^4) < 1 - k/n^2 + k^2 /n^4 <= 1 - k/n^2 + 1/n^2 = 1 - (k-1)/n^2, as desired. B6: Notation: a = b (c) means a is congruent to b modulo c, i.e. c divides a-b. Lemma: 2 is a primitive root mod 101 (which is prime). That means that every number not divisible by 101 is congruent to some power of 2 mod 101. Equivalently, 2^n = 1 (101) if and only if 100 | n. Proof of Lemma: 100 | n implies 2^n = 1 (101) by Fermat's Little Theorem. Conversely, define d as the order of 2 mod 101, the smallest positive integer such that 2^d = 1 (101). Then if 2^n = 1 (101), write n = qd + r where 0 <= d < r (simple division). Then 2^r = 1 (101) also, but r is smaller than the smallest positive integer such that 2^d = 1 (101). So r is not positive, it's zero, and d divides n. In particular, we know d | 100 since 2^100 = 1 (101). So to find d we compute 2^d (101) for d = 1, 2, 4, 5, 10, 20, 25, 50, 100. It turns out only the last is 1; we'll need that 2^50 = -1 (101) later. Thus 2^n = 1 (101) implies 100 | d. (Actually not a hard computation: for example, 2^10 = 1024 = 14 (101) so 2^20 = 14^2 = 196 = -6 (101), and 2^25 = 2^5 2^20 = -6(32) etc.) Now suppose n_a + n_b = n_c + n_d (10100). Since 100 and 101 divide 10100, this also holds mod 100 and 101, giving [1] a + b = c + d (100) [2] 2^a + 2^b = 2^c + 2^d (101). Define polynomials f(x) = (x - 2^a)(x - 2^b) = x^2 - (2^a + 2^b)x + 2^{a+b} and g(x) = (x - 2^c)(x - 2^d) = x^2 - (2^c + 2^d)x + 2^{c+d}. By Little Fermat again, [1] implies 2^{a+b} = 2^{c+d} (101), so f(x) = g(x) (101) for all integers x. In particular, 0 = f(2^c) = (2^c - 2^a)(2^c - 2^b) (101), and the product of two integers is divisible by the prime 101 only if one of them is. Suppose 2^a - 2^c = 0 (101). Then 2^{a-c} = 1 (101), and by the lemma, a = c (100), which implies b = d (100). (Similarly, if 2^c - 2^b = 0 (101), then b = c (100) and a = d (100).) But since a,b,c,d are all between 0 and 99, these last congruences are equalities so {a,b} = {c,d}.