1990 Putnam exam problems and solutions. [Solutions were taken from USENET posts at the time, and have been laboriously retyped, Nov 2001, by a bored rusin@math.niu.edu since electronic copies seem to have vanished from the planet. Please alert me to typos etc. If anyone can accurately recover attributions I would be happy to add them. --djr] Problem A-1 Let T_0 = 1, T_1 = 3, T_2 = 6, and for n >= 3, T_n = (n + 4)T_{n-1} - 4n T_{n-2} + (4n - 8)T_{n-3}. The first few terms are 2, 3, 6, 14, 40, 152, 784, 5168, 40576, 363392. Find, with proof, a formula for T_n of the form T_n = A_n + B_n, where (A_n) and (B_n) are well-known sequences. Let U_n = T_n - n T_{n-1}. Then the U's satisfy U_n - 4U_{n-1} + 4U_{n-2}/ A linear recurrence with constant coefficients is easily handled using power series; we see U_n = a 2^n + b n2^n for some constants a and b. Our a and b are 1 and -1/2 respectively. We can recover the T's from T_n = U_n + n U_{n-1} + n(n-1) U_{n-1} + ... + n!/1! U_1 + n! T_0, which telescopes to 2^n + n! (T_0 - 2^0) = 2^n + n! . Problem A-2 Is \sqrt{2} the limit of a squence of numbers of the form \root3{n} - \root3{m}, (n, m = 0, 1, 2, ...)? Justify your answer. The set of differences \root3{n} - \root3{m} is dense in all the reals, and indeed, m can be taken to be a perfect cube, m = K^2. One way to believe this -which can be made rigorous- is to note that if we let n move *continuously* from K^3 to (K+1)^3, it passes through some 3K^2 + 3K + 1 integer values; that is, a numebr v_K of values going to infinity with K. As this happens, the cube root of n goes from K to K+1. So the inverse images of those v_K values give rise to a lot of differences \root3{n} - \root3{m} in [0,1]. Alternate solution: Let n = f(m), with f(m) monotonically increasing. Several f(m( will work, for instance f(m) = m + [3\sqrt{2}m^(2/3)], where [] is the greatest integer function. Using Taylor expansion for \root3{f(m)-\root3{m} and the fact that lim{n->infinity} [an-an = 0 for irrational an gives the desired limit. Problem A-3 Prove that any convex pentagon whose vertices (no three of which are collinear) have integer coordinates must have area >= 5/2 [Solution not posted I think. Also not so elegant. --djr] I will show certain configurations have area >= 5/2. then show others can be reduced to those. (a) There exists an interior lattice point (b) There exist two or more lattice points within a single edge In each case [see non-existent picture :-) ] there is a decomposition of the pentagon into 5 triangles with lattice vertices; then simply recall that each triangle with lattice vertices has area at least 1/2. OK, now in general, label the vertices counterclockwise as A,B,C,D,E. One may translate the figure so that A is at the origin and then B is at some point (x,y). If d = gcd(x,y) we may write d = r x + s y for some integers r and s; then the matrix ( r s ) M = ( ) ( -y/d x/d ) describes a linear transformation preserving areas and orientations as well as the integer lattice, which carries the original pentagon to one with B = (d, 0). If d > 2, then we are done by case (b), so we may assume d <= 2. If d = 2, let X = (1,0). Then the decomposition of the pentagon into triangles EAX, XBC, CDE, and XCE shows the area to be at least 5/2 unless the y-coordinates of E and C are exactly 1, and then that the y-coordinate of D is equal to 2. Even then, if the area is less than 5/2, this would require EC to be of length 1, making the "pentagon" a triangle with AED collinear (or making it non-convex), which is contrary to assumption. So we may assume d = 1, i.e. the coordinates of B are relatively prime. By symmetry we may assume the coordinates of E are also relatively prime. Considering the decomposition into EAB, EBC, ECD shows the y-coordinate of E is at most 2. Then by applying a shear transformation (x,y)->(x+a y,y), we may assume its x-coordinate is 0 or 1 or -1. Again using the previous paragraph and shears, we see that we may assume E = (0,1) or (-1,2). If E=(0,1), then by convexity and non-collinearity, we see (1,1) is an interior lattice point; similarly if E=(-1,2) then (0,1) is an interior lattice point. In either case we are finished by (a). Problem A-4 Consider a paper punch that can be centered at any point of the plane and that, when operated, removes from the plane precisely those points whose distance from the center is irrational. How many punches are needed to remove every point? Another problem from _A_Problem_Seminar_! This is the third year in a row that a problem has been taken straight from Newman's book (three-coloring the plane in 1988, and the uncountable family of almost disjoint sets in 1989). This is starting to get ridiculous. Wallace pointed out, three punches are indeed necessary and sufficient. The first two punches can be represented by (0,0) and (0,1) by appropriate scaling and rotation, these leave points with a subset of points with rational x coordinates. A third punch on the x-axis at pi or even \sqrt{2} [giving 2\sqrt{2}x + 2 = rational => x irrational] removes these. Problem A-5 If A and B are square matrices of the same size such that ABAB = 0, does it follow that BABA = 0 ? No. A simple solution is to use linear transformations on 5 dimensional space. Number the dimensions 1, ..., 5 and have A map the dimensions as follows: 1 -> 2 and 3-> 4 (all others are in A's kernel) Have B map 2 -> 3 and 4-> 5 (all others are in B's kernel) Then ker(BABA) is the orthocomplement of dimension #1, and #1 is mapped to #5. And ABAB (apply B first, then A, then B, finally A) collapses everything. Alternate solution: By example. Let A = [ [0,0,0], [0,1,0], [0,0,1] ] and B = [ [0,1,0], [0,0,1], [0,0,0] ]. Alternate solution: Everyone seems to agree that this is a ridiculously easy problem, but i'd just like to point out that there's no need to "find" a counterexample. tha is, you can just take a generic counterexample, in a certain restricted context. consider the free non-unital, nilpotent of degree 5, associative algebra on two generators a dn b. it has the obvious finite basis, and the two-sided ideal generated by abab is obbiously one-dimensional, so in the quotient algebra abab=0 but baba#0. the quotient algebra is not a faithful module over itself, but you can repair that difficulty by adjoining an identity element, so then you're done. Problem A-6 If X is a finite set, let |X| denote the number of elements in X. Call an ordered pair (S,T) of subsets of {1, 2, ..., n} admissible if s > |T| for each s in S, and t > |S| for each t in T. How many admissible ordered pairs of subsets of {1, 2, ..., 10} are there? Prove your answer. Solution: Let $a_n$ be the number of admissible ordered pairs of subsets of {1, 2, ..., n}. We claim a_n = F_{2n+2} for n >= 0. When n=10, this evaluates to 17711. Here F_n is the n-th Fibonacci number (F_0 = 1, F_1 = 1, F_n = F_{n-1} + F_{n-2} for n >= 2). We prove a_n = F_{2n+2} by induction on n. The asserion is easily checked for n = 0, 1. For n>=2, there are a_{n-1} admissible pairs (S, T) of {1, 2, .., n} with n not in S, n not in T. a_{n-1} admissible pairs (S, T) of {1, 2, .., n} with n not in S a_{n-1} admissible pairs (S, T) of {1, 2, .., n} with n in T a_{n-1} admissible pairs (S, T) of {1, 2, .., n} with n in S and n in T Each of these equalities is proved by exhibiting a one-one correspondence. To prove the second, for example, use (S, T) <==> (S', T') where S' = S \ {n}, T' = T-1 = { t-1 : t in T }. Once all are proved, we have the recurrence a_n = 3 a_{n-1} - a_{n-2}. This is the same recurrence satisfied by the alternate Fibonacci numbers. Alternate solution: (Sketch Proof:) We solve the general problem for admissible pairs of subsets of {1, 2, ..., b}. The summation which gives the answer here is: -- -- n - a n - b > > ( ) ( ) -- -- b a a>=0 b>=0 x -- -- n - i n - x + i = > > ( ) ( ) (substituting x = 1+b, i = a) -- -- x i x>=0 i=0 -- 2n - x + 1 = > ( ) (this follows from well-known -- x identities, or combinatorially) x>=0 = f(2n+2), then 2n+2'nd fibonacci number (since diagonal numbers of Pascal's triangle give fibonacci numbers) Hence in our case, the anwer is f(22). Yet another solution: The easiest way to do this problem is let a_n be the numebr of admissible ordered pairs of subsets of {1, 2, ..., n}. Write a_n as a double sum in the obvious way (corresponding to choices of |S| and |T|) then evaluate the generating function \sum_n a_n x^n. It reduces to 1/(1-3x+x^2) which gives a_n = F_{2n+2}, the Fibonacci number. (I could be off slightly -- I haven't checked this carefully.) Problem B-1 Final all real-valued continuously differentiable functions f on the real line such that for all x, (f(x))^2 = \int_0^x ( (f(t))^2 + (f'(t))^2 )dt + 1990. Formally, we differentiate w.r.t. x to see 2 f f' = f^2 + (f')^2 i.e. (f - f')^2 = 0, so that f = f' and f(x) = C e^x. Then C^2 e^{2x} = \int_0 ^ x (2 C^2 e^{2t}) dt + 1990 = C^2 ( e^{2x} - 1 ) + 1990 shows C = +- sqrt(1990). Thus f(x) = sqrt(1990) e^x and f(x) = -sqrt(1990) e^x are the only solutions. Rather a silly question, which probably means that the graders will insist on dtails like mentioning that the derivative of an integral of f is equal to f only if f is continuous. Problem B-2 Prove that for |x| < 1, |z| > 1, oo ----- 2 (j - 1) \ j (1 - z) (1 - z x) (1 - z x ) ... (1 - z x ) 1 + ) (1 + x ) ---------------------------------------------- = 0. / 2 3 j ----- (x - z) (z - x ) (z - x ) ... (z - x ) j = 1 Problem B-3 Let S be a set of 2 by 2 integer matrices whose entries a_ij (1) are all squares of intergers and, (2) satisfy a_ij <=200. Show that if S has more than 50387 (=15^4 - 15^2 - 15 + 2) elements, then it has two elements that commute. {a=x^2 and a<=200} => {|x| <= 14}, so there are 15 possible values for each a_ij, giving 15^4 matrices altogether. Among these are the matrices of the form [ [ a, b ], [ b, a ] ] any two of which commute. So if S does _not_ have two commuting elements, it has at most one of these 15^2 matrices. Likewise there is the commuting family of 15^2 diagonal matrices of the form [ [ a, 0 ], [ 0, b ] ] Note that this family and the previous family have in common only the 15 scalar matrices [ [ a, 0 ], [ 0, a ] ] So a maximal set with no commuting pairs includes one from each of these families (but not a scalar matrix) and then one from the complement of the two. Here inclusion-exclusion counts the complement as 15^4 - 2*15^2 + 15. So I get an upper bound of 15^4 - 2*15^2 + 15 + 2 = 50192 without working particularly hard. More generally any set of matrices of the form { a I + b J ; a, b in Z } is a commuting family, no matter what the matrix J is. So it is possible to consider more families than just the two above (which correspond to the choices J=[[0,1],[1,0]] and J=[[1,0],[0,0]] respectively). Perhaps this is how an improved upper bound can be obtained. Problem B-4 Let G be a finite group pof order n generated by a and b. Prove or disprove: there is a sequence g_1, g_2, g_3, ..., g_{2n} such that (1) every element of G occurs exactly twice, and (2) g_{i+1} equals g_i a or g_i b, for i = 1, 2, ..., 2n. (Interpret g_{2n+1} as g_1 ). This problem which looks like a group theory problem is actually a graph problem. Since G is generated by a and b, it can be represented as a connected directed graph, with each node (element of G) having two paths out (a and b) and two paths in (a and b inverse). Euler's directed path travelling theorem gives an affirmative answer to the question. Problem B-5 Is there an infinite sequence a_0, a_1, a_2, ... of nonzero real numbers such that for n - 1, 2, 3, ... the polynomial p_n = a_0 + a_1x + a_2 x^2 + ... + a_n x^n has exactly n distinct real roots? The Talyor series for a number of periodic functions has the desired quality; for instance, sin(x). Except that sin(x) has only odd terms. And 0*x^2 + x - 0 doesn't have two real roots, only one... However, I (think!) that sin(x)+cos(x) works well. On paper it seemed to work thru about 7 terms, but I couldn't prove that it would work. One clever fellow came up with a non-constructive proof: Start with an n-th order polynomial with n roots. Let L be some closed bounded interval containing all of the roots (and a little more on each side). Then, add in A*x^(n+1), wherer A is just small enough that no roots are lost. You can do this because x^(n_1) is also bounded on this interval -- let its maximal value be N. Then let M be the minimum value of all of the extremum; the letting N < M/2 guarantees that all n roots are preserved. But further out towards infinity, another root will spring up, since x^(n+1) has different parity than x^n (one will slope up and the other down on one side). Alternate solution: Yes. It follows immediately from this lemma. Lemma: Suppose p() is a polynomial of degree n-1 and having exactly k-1 real roots. For any non-zero number E whose absolute value is sufficiently small, the polynomial q(x):= E x^n + p(x) has at least k real roots. Proof. Enumerate the roots of p as r_1 < ... < r_(k-1) and let r_0 and r_k denote minus and plus infinity. Pick reals x_1 ... x_k such that r_(i-1) < x_i < r_i and so that as i foes from 1 to k, (*) the values p(x_i) alternate sign. Just pick E to be so small that (**) the values q(x_i) alternate sign. But lim_{x\to +infinity} x^n and lim_{x\to +infinity} x^{n-1} have the same sign and lim_{x\to -infinity} x^n and lim_{x\to -infinity} x^{n-1} have opposite signs. So adding the Ex^n terms to p bends p's graph back across the axis again, introducing a new real root. This root will be left of x_1, if the high order coefficients of p and q have same signs; if they have different signs, the new root will be right of x_{k-1}. Problem B-6 Let S be a closed bounded conves set in the plane. Let K be a line and t a positive numebr. Let L_1 and L_2 be support lines for S parallel to K, and let \overbad{L} be the line parallel to K and midway between L_1 and L_2. Let B_S(K,t) be the band of points whose distance from \overbar{L} is at most (t/2)w, where w is the distance between L_1 and L_2. What is the smallest t such that S \cap \bigcap_K B_S(K,t) \ne 0 for all S? (K runs over all lines in the plane.) [ picture deleted ] I believe that t = 1/3 is the answer. For any convex shape S there is a t <= 1/3 such that for all lines K, the (closed) band B_S(K