My comments and solutions to the 1996 Putnam examination, as posted to the sci.math newsgroup. There's an introductory post, answers to everything, and a summary post at the end. Editorial changes noted [djr - like this]. Note that in the summary is a pointer to http://www.math.princeton.edu/~kkedlaya/ where there's a set of solutions fully TeX'd (and fully correct, unlike some of mine). Dan Bernstein also posted such a solution set; I didn't save it. I also didn't save much commentary on the problems or solutions since the key ideas were all contained in either my solutions or the ones at the above URL. A couple of comments by others are at the end. dave ============================================================================== From: rusin@kebnekaise.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Putnam examination problems Date: 8 Dec 1996 11:22:59 GMT Today the annual Putnam examination (contest) was taken by undergraduates in North America. Since the contest ended hours ago (even in Hawai'i) I suppose it's fair game to discuss the questions now. In a separate post I'll give spoilers to the questions I was able to solve. Not all of my answers are satisfactory to me, and there are two I really don't think I can answer (at least not at this hour of the night). I'll try to post the full set of questions if no one else does, but in the meantime perhaps I can get someone else to chime in for the ones I missed: A5. If p is a prime number greater than 3 and k=\floor(2p/3), prove that the sum \binco(p,1) + \binco(p,2) + ... + \binco(p,k) of binomial coefficients is divisible by p^2. (For example, \binco(7,1)+\binco(7,2)+\binco(7,3)+\binco(7,4)= 7+21+35+35=2.7^2.) [Sorry about the transcription. \floor is the greatest-integer function \floor(x) = |_ x _|. \binco(p,q) is the binomial coefficient ( p ) ( q ). Comments: each of the coefficients is a multiple of p, so it amounts to proving that 1 - 1/2 + 1/3 - ... +- 1/k = 0 mod p. For comparison, I note that the condition 1 - 1/2 + 1/3 + ... + 1/(p-1) = 0 mod p is rarely satisfied and of interest in Fermat's Last Theorem.] I also had trouble wrapping my brain around what I'm sure is a standard problem in combinatorics (bipartite graph theory, actually). Presumably this particular instance of the problem is easily handled by a counting argument, but I can't seem to sort my way through it: A3. Suppose that each of twenty students has made a choice of anywhere from zero to six courses from among a total of six courses offered. Prove or disprove: There are five students and two courses such that all five have chosen both courses or all five have chosen neither. [Is is just me or does it seem that the word "either" belongs in the middle of the last sentence?] Comments on the test appreciated. I thought it seemed pretty fair this year. Quite a few problems seem to use induction and calculation; others seem to be more full of niggling details which I didn't always care to flesh out. I thought the questions on the second half were easier to get started on; it's probably better when it's the other way around. A1 - easy A2 - Nice one. Merited a verbal "Hmm!" even as I sit alone in a quiet house. A3 - I must be overlooking something. I know this is a standard problem A4 - Easy but hard to express cleanly. A5 - Hard for me. I note that "Sum( binom(p,i), i=1..p-1) = 0 mod p^2?" is currently unsolved. A6 - not bad, and similar to a USENET problem a month ago! B1 - easy B2 - easy idea, unpleasant technical constructs B3 - interesting. Hope I'm right. B4 - standard B5 - messy computations (must be a better idea I'm missing) B6 - easy ============================================================================== [Solutions to A3, A5 were eventually received, as described below] ============================================================================== From: rusin@kebnekaise.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Putnam exam, some SPOILERS Date: 8 Dec 1996 11:48:14 GMT As promised in a separate post, I am posting my solutions to ten of the twelve Putnam problems this year. In a couple of cases I'm pretty sure I've missed the "right" solution, but otherwise I think my solutions have all the key ideas (some details occasionally omitted). Eventually these files will be stored with other Putnam materials at http://www.math.niu.edu/~rusin/problems-math/ A1. Suppose given two squares with sides of length x and y with x>y. Placing the two squares left and right of each other, we see the optimal rectangle must have dimensions x by (x+y), and so the area is x^2+xy. We must find the minimum value of this subject to x^2 + y^2=1 and x>y>0. Viewing these pairs as points on an arc of the circle, we may write x= cos(t), y=sin(t) for some t in (0, pi/4). We must minimize cos^2(t)+cos(t)sin(t) = (1/2) + (1/2) cos(2t) + (1/2) sin(2t) = (1/2) + sin(2t+pi/4) / sqrt(2). (I seem to be in a trigonometric mood.) But the sine function , on the interval (pi/4 , 3pi/4), clearly has a maximum value of 1, so that the function gets as large as A = (1 + sqrt(2) ) / 2 with the extreme value when x=cos(pi/8), y=sin(pi/8). A2. The points M consitute an annulus of radii 1 and 2 centered midway between the other circles' centers. Draw coordinates at that midpoint, with the centers separated horizontally. View the plane then as the set of complex numbers. Writing cis(t) for the complex number cos(t)+i sin(t), we describe the circles as the sets { -5 + cis(t1), 0 <= t1 < 2pi} and {+5+3cis(t2), 0 <= t2 < 2pi}. In the complex plane the midpoints are simply averages, i.e. M is the set of points of the form cis(t1)/2 + (3/2) cis(t2). Note that for a fixed t1, as t2 varies these points trace out a circle centered at cis(t1)/2 and with a radius of (3/2). This is just the radius necessary to intersect the small circle at the opposite point cis(-t1). The point furthest from the origin (that with t2=t1) is of distance 2 from the origin. As we vary t1, now, the circle just described will rotate around the origin; in all cases it will completely contain the unit circle at the origin, and be contained in the circle of radius 2 at the origin. Clearly the union of the circles will sweep the annulus between these two. A3.? [djr - see a later post, below] A4. The "if-then" phrasing of the problem is not optimal because we must use R. Let me instead show Theorem: there is an embedding f of A into the circle C such that (a,b,c) in S iff f(a), f(b), and f(c) are in clockwise order around C. Proof. By induction on |A|. If |A|<3 there is nothing to prove; define f(x1) and f(x2) arbitrarily in C. Now given a set A, pick a point x_0 in it, and find an embedding f of A'=A-{x0} to C which preserves order. (One must verify that S intersected with the power set of (A')^3 again satisfies axioms 1,2,3.) Pick one point of A' to be x_1; then label the others x_2, ..., x_n according to their order clockwise around the circle from x_1. By assumption, for all i,j,k>0, (x_i, x_j, x_k) is in S iff i 0. We need only verify that the desired property holds for all triples {x_j, x_k, x_0}. But this is done as in the previous paragraph (using Axiom 3). Finally we get the embedding required in the problem: pick a point P not in the image of f, and an homeomorphism h : Circle - {P} --> R which is increasing as we traverse the circle clockwise; then g = h o f is the desired embedding into R. A5. ? [djr - see a later post, below] A6. The behaviour is different for c in [0, 1/4] and for c > 1/4. In the former case, f must be constant. Indeed, if c<1/4, there are two real solutions to x^2+c = x. For any a, there is a sequence x_0=a, x_1, x_2, ... converging to one of these two roots, r , for which either x_(n+1) = x_n^2 + c for all n or else x_(n-1)=x_n^2 + c for all n. It follows from continuity that we must have f(r) = lim f(x_n) = f(a) (since f is in fact _constant_ on this sequence). Thus f is locally constant, and since it's continuous on R, it's constant. If c>1/4, then we may set f to be any continuous function on the interval [0,c] as long as f(0)=f(c). Then define f(x) for all x>0 as follows: let x_0=0 and for n>0 let x_n=(x_(n-1))^2+c. Note that since the quadratic has no real roots, this x_n > x_(n-1) for all n. So the {x_n} are increasing monotonically. They cannot be bounded, since that would mean they converge to a limit r (which would be a root of r^2+c=r). Hence the x_n are unbounded. Thus the ray (0,oo) is the countable union of intervals (x_(n-1), x_n), each of which is carried bijectively to the next under x -> x^2+c. Then the invariance of f implies that the values of f everywhere are determined by their values on the first interval [0,c]. The glueing lemma guarantees that f is continuous. ============================================================================== B1. S selfish => |S| is an element of S. But in addition, S _minimal_ selfish => all other x in S are > n. Indeed if there is an m in S which is < n, then let T consist of m and any other m-1 elements of S; it's also selfish. So the minimal selfish S contained in {1, 2, ..., n} are these: {1} {2} union any singleton in {3, 4, ..., n} {3} union any two-element subset of {4, 5, ..., n} {4} union any three-element subset of {5, 6, ..., n} and so on. Counting them gives 1 + (n-2 choose 1) + (n-3 choose 2) + ... + (n-k choose k-1) where we sum until the terms are zero, i.e., until k > (n+1)/2. I don't believe there is a closed form for this sum; just looking at its largest term shows that it's roughly an exponential function of n. [djr - Aack! The terms are in fact the Fibonacci numbers! Prove by using properties of binomial coefficients to establish the recurrence relation satisfied by the Fibonacci numbers. Sheesh!] B2. What is the area under the curve y= log(2x-1) between x=(e+1)/2 and x=n? Why, it's Integral log(2x-1) dx, of course, an integral which we compute as (1/2) Integral log(u) du = = (1/2) ( u log(u) - u ) ( + C ! I'm giving a calc exam Monday) = (1/2) ( (2n-1) log(2n-1) -(2n-1) ). We show by induction that for all n>1, this area A_n satisfies Sum( log(2k-1), k=1..(n-1) ) < A_n < Sum( log(2k-1), k=1..n ). Since A_2 = (1/2)( 3 log3 - 3) is clearly positive and easily seen to be less than log(3), the inequalities hold for n=2. The inductive step comes from the calculation A_(n+1) - A_n = (1/2)( (2n+1) log(2n+1) - (2n-1) log(2n-1) ) - 1 = n log( (2n+1)/(2n-1) ) + (1/2) (log(2n+1)+log(2n-1)) - 1. = (n-1) log( (2n+1)/(2n-1) ) + log(2n+1) - 1. As log(1+x) < x, this last line is clearly less than log(2n+1). The middle line may instead be rewritten in the similar form = (n+1) log( (2n+1)/(2n-1) ) + log(2n-1) - 1 which is greater than log(2n-1) since log(1 + 2/(2n-1) ) > 1/(n+1). (There may be some trivial way to see this, but I used Taylor series: log(1+x)>x-x^2/2 if 0= 2. Details left to the reader.) Adding these estimates for A_(n+1) - A_n to the inequalities for A_n gives the corresponding inequalities for A_(n+1). Exponentiating then shows Prod( (2k-1), k=1..(n-1) ) < ((2n-1)/e)^((2n-1)/2) < Prod( (2k-1), k=1..n ) for all n>2. Rearranging the inequalities gives the desired conclusion for all n>3; the cases n=1 and n=2 are trivial. NOTE: This is really quite standard and is at the basis of Stirling's approximation for n!. It becomes rather convoluted because of the specific inequalities which were sought. Had they asked us to prove similar inequalities but with an extra factor of sqrt(e) thrown in, the estimates for A_n would be simply the "upper" and "lower" Riemann sums approximating Integral log(2x-1). B3. There are n terms to be added, each at most n(n-1), so we cannot exceed a cubic function of n. In fact, the maximum value (if my calculations are correct) is P(n) = (2n^3-3n^2-11n+72)/6 for n>=3. (P(2)=2.) Observe that the "circular sum" in question is determined by the ordered set {x_1=1, ..., x_n=n} and the permutation f used to write the sum as x_f(1) * x_f(2) + x_f(2) * x_f(3) + ... + x_f(n) * x_f(1). In particular, with fixed x_i, there are only as many sums to consider as there are permutations, and so there is a maximum. It does not occur for a unique f (indeed, the circular sum is really a function of the coset of <(1 2 ... n)> to which f belongs), but it's essentially unique, as we will see by construction. In particular, we will see that the optimal circular sum involves the product x_1*x_2 . For n=2,3, there is really only one circular sum x_1 x_2 and x_1 x_2 + x_2 x_3 + x_3 x_1 respectively. With the given values of x_i these equal P(2)=2 and P(3)=11 respectively. So now by induction suppose that for any permutation of {1, 2, ..., n-1} we know the circular sum to be no larger than P(n-1). I claim that the maximum value of a circular sum for {x_1=2, x_2=3, ..., x_(n-1)=n} is then P(n-1) + n(n-1) + (n-1). Indeed, for any permutation f of these terms, we relate the circular sum for the x_i to the corresponding sum for the y_i=x_i-1 (={1, 2, ..., n-1}): by expanding the former we get y_f(1) * y_f(2) + y_f(2) * y_f(3) + ... + y_f(n) * y_f(1) + 2 * (y_1+...+y_(n-1))*1 + (n-1)*1^2 which is the latter's circular sum plus 2*Sum( i, i=1..n-1 ) + (n-1). [The factor "2" here is absent when n-1 = 2]. By induction, that circular sum is at most P(n-1). Note that by induction we have the additional information that the optimal circular sum of the x_i includes x_1*x_2 = 2*3 as a summand. Now suppose an (optimal) permutation for {1, 2, ..., n} is selected. Writing x and y for the terms multiplying 1, we see the circular sum C is C = 1*x+ 1*y - x*y + S where S is a circular sum of {2, 3, ..., n} formed by adding x*y to the sum of all terms in C not having 1 as a factor. (That is, we "remove the 1 and close the loop".) Since this may be written C = 1 - (x-1)*(y-1) + S, it is clear that C <= 1 - (2-1)*(3-1) + max(S), the last term being the maximum (over all permutations of {2,3,..., n}) of the circular product involving those n-1 numbers. By an earlier paragraph, we know that this maximum is P(n-1) + (n+1)*(n-1). This gives an upper bound of P(n-1) + (n^2-2) to C. Now, we would not know whether this upper bound were ever attained except that we know the optimal circular sum for {2, 3, ..., n} does involve 2*3 as a summand. Thus, replacing this summand by 1*2+1*3 gives a circular summand of {1, 2, ..., n} equal to the established upper bound. It remains only to check that the recurrence relation P(n)=P(n-1)+(n^2-2) P(3)=11 has the solution P(n) = (n^3-n)/3 - (n^2-n)/2 - 2n + 12 = (2n^3-3n^2-11n+72)/6, which is elementary. [djr - well, it would be if I kept my signs straight! Actually it comes out to (2n^3+3n^2-11n+18)/6.] NOTE: The optimal product may be found from this proof: it's 1*3 + 3*5 + 5*7 + ... (top odd)*(top even)+ ... + 8*6 + 6*4 + 4*2 + 2*1 B4. Answer: No. Proof: Diagonalize! If A is similar to a matrix D, then there is an invertible matrix P with A = P^(-1) D P. Then it's a well-known calculation that f(A) = P^(-1) f(D) P for any polynomial function f. Assuming that a sequence of such polynomials f_n gives a convergent sequence f_n(A), it follows that the sequence f_n(D) must also converge; in this way we see we may assume f is any limit of polynomials, e.g. a power series. (The stated problem seems to gloss over the whole matter of convergence; I suppose it's to be assumed the infinite sum converges in the Euclidean metric, all because of the adjective "usual".) Very well, if A is similar to a diagonal matrix D=diag(d1, d2), then sin(A) = P^(-1) sin(D) P for some matrix P. But clearly sin(D) = diag(sin(d1), sin(d2)), so that sin(A) would be diagonalizable. That's not true for the given assumed value for sin(A) (its only eigenvalue is +1, and it has only a 1-dimensional eigenspace.) So A is not diagonalizable. But that means it's similar to (i.e. has Jordan canonical form qual to) D = ( d 1 ) ( 0 d ) for some (possibly complex) d. Now, it's easy to check by induction that D^n = ( d^n n d^(n-1) ) ( 0 d^n ) and thus to conclude (after manipulating the power series) that sin(D) = ( sin(d) cos(d) ) ( 0 sin(d) ). Now, is it possible that such a matrix (for some d) is equal to to the assumed value for sin(A)? Well, comparing the eigenvalues (or trace, if you prefer) we see this would need sin(d) = 1. But this forces cos(d)=0, so that sin(D) is the identity matrix, which is not similar to anything but the identity matrix. Thus we see that no A exists with sin(A) as shown (nor indeed with sin(A) equal to any matrix ( 1 x ) ( 0 1 ) except the identity matrix). B5. I'm not particularly pleased with my analysis, and in fact I'm not sure I haven't slipped in the calculation, but these ideas should be workable. Note that by swapping all X's and O's, we see there are just as many balanced strings beginning with X as there are beginning with O. So what are the balanced strings of length n beginning with X? We break them down into disjoint subsets: (a) If they begin XO, then what follows must be balanced and cannot start with OO; conversely, if w is a balanced string not starting with OO, then XOw is balanced. Let A(n) be the number of balanced strings of length n beginning XO; then A(n) = number of balanced strings of length n-2 not beginning OO. (b) If they begin XX, then they must follow with O. If the next term is another O, then what follows must be balanced and begin with X; conversely, if w is balanced and begins with X, then XXOOw is balanced. Let B(n) be the number of balanced strings of length n beginning XX. Then B(n) is half the number of balanced strings of length n-4. (c(k)) If they begin XXOX, then the next term must be O; moreover, if an X follows that, it must be followed by O as well. Continuing the pattern shows the sequence begins XXO(XO)^kO... for some n>0. What follows, as usual, must be balanced, and cannot begin with O; conversely, if w is balanced and begins with X then XXO(XO)^kOw is balanced. Let C(n,k) be the number of balanced strings of length n beginning XXO(XO)^kO. Then this number is half the number of balanced strings of length n-4-2k. These formulas must be treated carefully when n is small. In particular, C(n,k)=1 if n-4-2k=-1 or -2, except that C(n,k)=0 when n<4. So if D(n) is the total number of balanced strings of length n, we may summarize the preceding paragraphs with these formulae: D(n) = 2( A(n) + B(n) + Sum( C(n,k), k=1, 2, ...) ) A(n) = D(n-2) - (B(n-2) + Sum( C(n-2,k), k=1,2,... ) ) B(n) = (1/2)( D(n-4) ) C(n,k) = (1/2)( D(n-4-2k) ) So A(n) = (1/2) D(n-2) + A(n-2) (for n>2) and C(n,k)=C(n-2,k-1); upon subtracting, we see that D(n)-D(n-2) = D(n-2) + [D(n-4)-D(n-6)] + D(n-6) or simply D(n)=2 D(n-2) + D(n-4) (The derivation assumes n>4 but in fact this is true for smaller n as well.) We also have the initial conditions D(n)=2, 4, 6, 10, 14, 24, 34,... for n =1, 2, 3, 4, 5, 6, 7,... (the last few best found by computing A(n), B(n), and the C(n,k) separately). Thus the values of D(n) for even and odd n are separate solutions of a recurrence relation with corresponding polynomial (x^2-2x-1). These may be written as linear combinations of powers of the roots of that polynomial, but since it does not have rational roots, it seems rather pointless to do so. [djr - others' solutions show that the correct recurrence is D(n)= 2D(n-1) + 2, so I guess I goofed. Too bad, because _this_ recurrence is easier to solve: D'(n)=D(n)+2 satisfies D'(n+2)=2D'(n), and so is a power of two.] B6. Consider the function f(x,y) = Sum( x^a_i y^b_i ), that is, f(x,y) = Sum exp (a_i log x + b_i log y); then this function is defined on the open first quadrant of the plane. Since all terms are positive, there is no cancellation. In particular, since there exist a_i of different signs, the function blows up both as x -> 0 and as x -> oo. Likewise, since there are both positive and negative b_i, the function is unbounded as y-> 0 and as y-> oo. Thus given a point p in the first quadrant, there exists a compact set around p outside which f only takes on values greater than f(p). Since f is clearly continuous, f must attain a minimum on this compact set, which is then a minimum on the entire first quadrant. Since f is everywhere differentiable and the domain open, the minimum must occur at a point where grad(f) vanishes. The coordinates of this point are the desired x and y. [Almost nothing is used of the convexity assumption nor of the statement that (0,0) is in the interior.] dave ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Putnam exam, last SPOILER Date: 9 Dec 1996 04:18:11 GMT I received mail from axa190@psu.edu (Aravind Asok) regarding the Putnam problem A3. Spoiler follows. >Date: Sun, 08 Dec 1996 11:49:57 -0500 >Notice also that the problem said disprove, check 6C3 = 20 and you should >come out with a counterexample.. Indeed, this shows there need _not_ be five students and two courses meeting the given condition. If the 20 students select each possible set of three courses, then given any set of five students and any pair of courses, there will not be agreement in those students' enrollment in those courses. Given that a student has chosen those two courses, there are 4 ways to complete the selection of three courses. In other words, there are precisely 4 students who have chosen those two courses -- agreement among 5 is impossible. Dually, given any two courses, there are precisely 4 students who have chosen neither of those courses, so again no set of 5 students agreeing with this choice can be found. Interestingly I considered this arrangement several times as I tried to attack the problem; I kept rejecting it because of a logical flaw. Just goes to show, I guess, that one must always keep a clear head when doing these problems. dave ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Putnam examination problems Date: 9 Dec 1996 01:19:09 GMT In article <58e8ej$fnm@gannett.math.niu.edu>, Dave Rusin wrote: >there are two I really don't think I can answer Others, evidently, found these easier than I did. Solution for Putnam problem A5 follows. I just received this mail from Bogdan Georgescu >Date: Sun, 08 Dec 1996 11:17:30 -0800 > >if you look deeper: >1-1/2 +...1/k =1+1/2+1/3+1/4+ 1/p-1= 1+.....+ (p-1) >... well in Z_p > >just use p-k =k and elementary algebra. which is sufficient to finish Putnam problem A5. I would flesh his ideas into a proof as follows: Writing each binomial coefficient \binco(p,i) as p(p-1)(...)(p-i+1) ------------------ 1 2 ... i we see (as is well known) that this coefficient is a multiple of p and that (1/p)\binco(p,i) is, in the field Z/pZ of cardinality p, the element (-1)(-2)(...)(-[i-1]) --------------------- 1 2 3 ... i which simplifies to (-1)^(i-1) / i. Thus the sum in question is p times an integer which, reduced mod p, is 1 - (1/2) + (1/3) - ... +- (1/k). Next note that for any i we have - 1/(2i) = + 1/(2i) + 1/(p-i) in Z/pZ. Thus we may replace the negative fractions in the sum above to get 1 + (1/2) + ... + 1/(p-1). (One should check carefully that each fraction near 1/k shows up precisely once. This is fine if p=+-1 mod 6; it fails for p=3.) Now we are summing the reciprocals of all nonzero elements of Z/pZ. These reciprocals are again precisely the set of all nonzero elements of Z/pZ, so that the sum above is congruent (mod p) to 1 + 2 + 3 + ... + (p-1). Of course this sum is equal to p(p-1)/2, and is for p>2 a multiple of p. Therefore the original sum is for p>3 a multiple of p^2, as desired. dave ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Putnam -- pointers to the questions, and some comments. Date: 9 Dec 1996 04:54:48 GMT Since I seem to have taken the floor here regarding the Putnam contest let me offer some corrections and general comments. First things first: I put off typing up the questions hoping that someone else would do it, and sure enough I found a pointer to them already: URL: http://www.math.princeton.edu/~kkedlaya/ As an added bonus, you'll find there complete solutions, all nicely TeXed. Usually there are some clever variant solutions for some of the problems. I noticed a couple in the above file, but I was surprised to note that for the most part, the key ideas for solving the problems seemed to be the same (at least for me and for the authors of the solutions cited above). I freely confess that, as I had feared, I goofed up a few of the calculations and other details; in particular, I am dumbfounded that I failed to notice that the numbers I computed for B-1 were in fact the Fibonacci numbers. I received mail pointing out that one of the questions which stumped me (A3) is in fact a recycled competition problem. Compare this question from an old Math Olympiad: >Suppose >1 - 1/2 + 1/3 ... - 1/1318 + 1/1319 = p/q >p and q are natural numbers. >Prove that p can be divided by 1979. I found it interesting to note that there was very little newsgroup traffic this year regarding the Putnam exam. dave ============================================================================== Self-scoring: Well, I missed A3 and A5 altogether, and I flubbed the calculations of B3 and B5. I missed the punchline of B1 and I suppose I could be accused of supplying insufficient detail in (at least) A4 and B6. Still, I suppose I would rank in the top few dozen with this kind of paper -- not bad for an old geezer, eh? [and yes, I did it alone and in roughly the 6 hours alloted]. ============================================================================== Date: Wed, 11 Dec 1996 16:39:24 -0500 To: rusin@math.niu.edu (Dave Rusin) From: asok@math.psu.edu (Aravind Asok) Subject: Re: Putnam examination problems Here is a solution to the Putnam problem A5, this is from George Andrews.. A number theorist here... Let H(n) = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n n Let P(n) = 1 - 1/2 + 1/3 - 1/4 +.... + (-1) /n Then the Putnam problem reduces (as you have pointed out) to showing that for any odd prime p>3, p divides the numerator of P([2p/3]), where [x] is the greatest integer function. First we observe that p divides the numerator of H(p-1) because 2H(p-1) = (1 + 1/(p-1)) + (1/2 + 1/(p-2)) + (1/3 + 1/(p-3)) +...+ (1/(p-1) + 1) = (p/(p-1)) + (p/(2p-4)) + (p/(3p-9)) + ... + (p/(p-1)) Consequently we have a weak version of Wolstenholme's theorem: namely, p divides the numerator of H(p-1) for any odd prime p. We now consider 2 cases: CASE I. p = 3n+1, a prime. Hence [2p/3] = 2n. So we must show that p divides the numerator of P(2n). Now H(3n) - P(2n) = 2(1/2 + 1/4 + ... + 1/(2n)) + 1/(2n+1) + 1/(2*n+2) + ... + 1/(3n) = (1 + 1/2 + ... + 1/n) + 1/(2n+1) + 1/(2n+2) +...+ 1/(3n) = (1 + 1/(p-1)) + (1/2 + 1/(p-2)) + ... + (1/n + 1/(p-n)) 2 = (p/(p-1)) + (p/(2p-2)) + ... + (p/(np-n )). Hence p (which we recall is 3n+1) divides the numerator of both H(3n) and the numerator of H(3n)-P(2n). Hence p divides the numerator of P(2n), and we are done for case I. CASE II. p = 3n+2, an odd prime. Hence [2p/3] = 2n+1. So we must show that p divides the numerator of P(2n+1). Now H(3n+1) - P(2n+1) = 2(1/2 + 1/4 + ... + 1/(2n)) + 1/(2n+2) + 1/(2*n+3) + ... + 1/(3n+1) = (1 + 1/2 + ... + 1/n) + 1/(2n+2) + 1/(2n+3) +...+ 1/(3n+1) = (1 + 1/(p-1)) + (1/2 + 1/(p-2)) + ... + (1/n + 1/(p-n)) 2 = (p/(p-1)) + (p/(2p-4)) + ... + (p/(np-n )). Hence p (which we recall is 3n+2) divides the numerator of both H(3n) and the numerator of H(3n+1)-P(2n+1). Hence p divides the numerator of P(2n+1), and we are done for case II. Thus we have proved that for any prime p > 3 the numerator of P([2p/3]) is divisible by p and this then solves the Putnam problem. -- Aravind [.sig deleted] ============================================================================== Date: Thu, 12 Dec 1996 08:50:42 +0000 From: Robin Chapman To: Dave Rusin Subject: Re: Putnam exam, some SPOILERS Some additions to and comments on Dave Rusin's solutions A3. There are 20 3-element subsets of the courses. If each student takes a different 3-element subset then there are exactly four students taking each pair of courses, and four talking neither from a given pair. 21 students is impossible. Let there be N students. Count the number of pairs (P, S) where P is a pair of courses, and S is a student taking either both of the courses in P or neither of them. exactly one course from P. Then for each S there are at least 6 of these (P, S)s. But for each P there is at most 8 admissible S, and so 6N <= 8.15 pr N <= 20. If N = 20 this argument shows that each student takes 3 courses, otherwise there would be more than 6 admissible P for some S. A natural question, which I can't see an easy answer to is whether is this case the students must take all possible 3-course combinations. > A4. The "if-then" phrasing of the problem is not optimal because we must > use R. Let me instead show > > Theorem: there is an embedding f of A into the circle C such that > (a,b,c) in S iff f(a), f(b), and f(c) are in clockwise order around C. > > Proof. By induction on |A|. If |A|<3 there is nothing to prove; > define f(x1) and f(x2) arbitrarily in C. > > Now given a set A, pick a point x_0 in it, and find an embedding > f of A'=A-{x0} to C which preserves order. (One must verify that > S intersected with the power set of (A')^3 again satisfies axioms 1,2,3.) > Pick one point of A' to be x_1; then label the others x_2, ..., x_n > according to their order clockwise around the circle from x_1. By > assumption, for all i,j,k>0, (x_i, x_j, x_k) is in S iff > i > How shall we define f(x_0)? If (x_1, x_i, x_0) is not in S for > any i, choose f(x_0) in the arc from x_1 to x_2; if it's in S > for every i, choose f(x_0) in the arc between x_n and x_1. > > If (x_1, x_i, x_0) is in S for some i, then I claim (x_1, x_j, x_0) > is, too, for every j < i. Indeed, axioms 1 and 2 show that > (x_1, x_j, x_i) and (x_i, x_0, x_1) are in S; then axiom 3 shows > that (x_0, x_1, x_j) is too, which by axiom 3 is equivalent to my claim. > Thus there is an i such that (x_1, x_j, x_0) is in S iff j Choose f(x_0) in the arc from x_(i-1) to x_i. > > This construction guarantees that f has the desired property for any > triple {x_1, x_0, x_j}. Also by induction we know f has the > desired property for all {x_j, x_k, x_l} as long as j,k,l > 0. We > need only verify that the desired property holds for all triples > {x_j, x_k, x_0}. But this is done as in the previous paragraph (using > Axiom 3). > > Finally we get the embedding required in the problem: pick a point P > not in the image of f, and an homeomorphism h : Circle - {P} --> R > which is increasing as we traverse the circle clockwise; then > g = h o f is the desired embedding into R. These axioms are the familiar axioms for a "cyclic order". If we pick a in A, and define a relation R on A - {a} by (b, c) in R iff (a, b, c) in S, then it's easy to check that R is a strict total order and (b, c, d) in S iff (b, c) and (c, d) are in R. Embed the ordered set A - {a} in R, and then throw in a either above or below the other elements of A. A5. for 0 < j < p it's easy to see that (1/p) (p choose j) is congruent to (-1)^(j-1)(1/j) modulo p (interpreting fractions with no factor of p in the denominator in the natural way). It's conveneient to split into two cases, if p = 3r + 1 then 1/p times our sum is congruent to 1 - 1/2 + 1/3 - 1/4 + ... + 1/(2r-1) - 1/2r = 1 + 1/2 + .... + 1/2r - ( 1 + 1/2 + .... + 1/r) which is congruent to = 1 + 1/2 + .... + 1/2r + ( 1/(p-1) + 1/(p-2) + .... + 1/(2r+1) ) and this is congruent to zero (since 1/a + 1/(p-a) always is). The other case p = 3r +2 is similar. > > B1. S selfish => |S| is an element of S. But in addition, > S _minimal_ selfish => all other x in S are > n. Indeed if there is > an m in S which is < n, then let T consist of m and any other > m-1 elements of S; it's also selfish. > > So the minimal selfish S contained in {1, 2, ..., n} are these: > {1} > {2} union any singleton in {3, 4, ..., n} > {3} union any two-element subset of {4, 5, ..., n} > {4} union any three-element subset of {5, 6, ..., n} > and so on. Counting them gives > 1 + (n-2 choose 1) + (n-3 choose 2) + ... + (n-k choose k-1) > where we sum until the terms are zero, i.e., until k > (n+1)/2. These are the Fibonacci numbers! Another way of seeing this is to note that the mininal selfish subsets of {1, 2, ..., n} not containing n are those of {1,2,..., n-1} while those containg n have the form (1+A) union {n} where A is a mininal selfish subset of {1, 2, ..., n-2} and 1+A is the set got by adding one to all elements of A. > B4. Answer: No. Proof: Diagonalize! A slicker proof goes as follows. As for scalars we have (sin A)^2 + (cos A)^2 = I. This would give (cos A)^2 as the matrix with entries (0, -3992, 0, 0). But this matrix isn't a square. (It's nilpotent so it's the square of a nilpotent, but if B is an n by n nilpotent then B^n = 0.) This is a disappointingly trivial use of the number 1996. B5. Let's just count the number of balanced strings beginning with X. Replace each block adjacent Xs and Os with the number of symbols in the block. (e.g. XXOXOOXX -> 21122 etc.) Then the condition of balance is that only 1s and 2s appear, and that between each pair of 2s there are evenly many 1s. Let n = 2m be even. Thus each admissible sequence can be obtained from 2222...2 or 1222...1 by replacing some of the 2s by 11s, but the all-1 sequence can be got from both. Thus there are 2^m + 2^(m-1) - 1 admissible sequences and so 2(2^m +2 ^(m-1) - 1) balanced sequences. If n = 2m+1 is odd we instead get 2(2^(m+1) - 1) balanced sequences. > B6. Consider the function f(x,y) = Sum( x^a_i y^b_i ), that is, > f(x,y) = Sum exp (a_i log x + b_i log y); then this function is defined on > the open first quadrant of the plane. Since all terms are positive, there > is no cancellation. In particular, since there exist a_i of different > signs, the function blows up both as x -> 0 and as x -> oo. Likewise, > since there are both positive and negative b_i, the function is > unbounded as y-> 0 and as y-> oo. > > Thus given a point p in the first quadrant, there exists a compact set > around p outside which f only takes on values greater than f(p). > Since f is clearly continuous, f must attain a minimum on this > compact set, which is then a minimum on the entire first quadrant. > > Since f is everywhere differentiable and the domain open, the minimum > must occur at a point where grad(f) vanishes. The coordinates of this > point are the desired x and y. > > [Almost nothing is used of the convexity assumption nor of the statement > that (0,0) is in the interior.] I'm not quite convinced by the first part of the argument. If (0,0) isn't in the interior of the convex hull of the points (a_i, b_i) (this is the natural condition) then there will be a sequence of points (x, y) tending to the "boundary" of the positive quadrant with f(x,y) bounded. I found it convenient to consider instead g(u, v) = Sum exp (a_i u + b_i v) on all of R^2. Since (0,0) is in the interior of the convex hull of the (a_i, b_i), then there is a positive constant delta, such that for all non-zero (u, v) there's an i such that the angle between (u, v) and (a_i, b_i) is at most pi/2 - delta in absolute value. Thus there is K > 0 such that for each (u, v) of length R > 0 there is an i with a_i u+ b_i v > KR. This shows that |R| -> infinity implies g(u,v) -> infinity. As before at a minimum of g, the gradient vanishes and letting x = e^u, y = e^v gives the required solution. If (0,0) isn't in the interior of the convex hull, there is a line through the origin having the convex hull on one side. Taking (u,v) on the ray through the origin perpendicular to this, and on the opposite side of the convex hull, then g(u,v) is bounded, and if (0,0) isn't in the convex hull at all, then g(u,v) -> 0 as (u,v) goes to infinity on this ray. Robin Chapman -- Robin J. Chapman Department of Mathematics "But there are full professors University of Exeter, EX4 4QE, UK in this place who read nothing rjc@maths.exeter.ac.uk but cereal boxes." http://www.maths.ex.ac.uk/~rjc/rjc.html Don Delillo--White Noise