Answers for 1993 putnam exam culled from Usenet group sci.math. Answers here are (sometimes slightly modified or corrected) versions of first correct responses received at this site. Exam ended Sat 4 Dec 17:00:00 CST in the Chicago area (which I think is Sat Dec 4 1993 23:00:00 GMT), a little later to the west. Solutions appeared beginning almost immediately, finally completed Thu Dec 9 19:00:00 GMT. Statements of the problems are in a separate file. dave rusin, rusin@math.niu.edu ============================================================================== From: cs93156@assn015.cs.ualberta.ca (Cheng Howard Chi Ho) Date: Sun, 5 Dec 1993 01:24:35 GMT A1. c=4/9 A2. First prove that some real number a exists for n = 1. Suppose that this number a works for n=k, and another real number "b" works for n=k+1, show that a-b=0. ie. a=b. By induction, this shows that this number "a" works for all n >= 1. ============================================================================== A3 From: dsavitt@unixg.ubc.ca (David Savitt) Date: 5 Dec 93 09:09:08 GMT First, note that is A is a subset of B then f(A)<=f(B). Now, pick f(S), where S is the entire set {1,2,..,n}, and suppose f(S)=k. Let S_i denote the set S-{i}. Then we have at most k possibilities for f(S_1), k for f(S_2), etc., i.e. k^n choices for the ordered S_i. Now, note that, if a_1,..,a_j are the elements of S *not* in a set A, then A=S_(a_i) intersect S_(a_2) ... intersect S_(a_j), since A is contained in all the S_(a_i) and no element not in A is contained in all of them. Then f(A)=min{f(S_(a_1)),...,f(S_(a_j))}, i.e. the f(S_i) entirely define the rest of the function. It is easy to check, then, that any choice of the f(S_i) combined with f(S) does give one of the desired functions, i.e. when f(S)=k there are k^n functions. But f(S) runs through 1,...,m and, since all the functions produced must be distinct, the total number of such mappings is Sum{j=1 to m} of j^n, as desired. ============================================================================== A4 From: tycchow@schauder.mit.edu (Timothy Y. Chow) Date: Thu, 9 Dec 93 19:10:16 GMT Here's a proof that someone described to me. Let x_1, x_2, ..., x_m and y_1, y_2, ..., y_n be two sequences of positive integers, arranged in nondecreasing order, such that x_m <= n and y_n <=m. We want to show that there is some nonempty subset of the x's and some nonempty subset of the y's with the same sum. Let X_i be the sum of the first i x's and let Y_i be the sum of the first i y's. Without loss of generality we may assume that X_m >= Y_n. For each i from 1 to n, let k_i be the least integer such that X_(k_i) >= Y_i. (Clearly k_i exists since X_m >= Y_n.) Let S be the multiset {X_(k_i) - Y_i : 1 <= i <= n}. Every element in S is clearly nonnegative and less than n (otherwise k_i could be chosen to be smaller, since each x is at most n). If 0 is in S we are done; otherwise by the pigeonhole principle there must exist r and s with r > s such that X_(k_r) - Y_r = X_(k_s) - Y_s and the sets {y_(s+1),...,y_r} and {x_(k_(s+1)),...,x_(k_r)} work. ============================================================================== A5 From: rusin@mp.cs.niu.edu (David Rusin) Date: Mon, 6 Dec 1993 23:11:02 GMT Lines: 23 >A-5 In view of the forms of the endpoints it makes sense to do substitutions >which render all three integrals onto equal (or adjacent?) intervals. I used >u=1/(1-x) and u=1-(1/x) on the last two integrals to get > >\integral _ {-100} ^ {-10} f(x)^2 dx > >where f(x)= (x^2-x+1)/(x^3-3x+1). This is not quite what I expected; perhaps >I messed up the algebra -- I expected \integral (x^2-1)/(x^3-3x+1)^2 or >something rationally equivalent. Perhaps I expected too much! Tinkering aaround with (quadratic)/(x^3-3x+1), differentiating, and setting equal to f(x)^2 above provides a solution: the antiderivative is (-x^2+x)/(x^3-3x+1). ============================================================================== A6 From: rusin@mp.cs.niu.edu (David Rusin) Date: Mon, 6 Dec 1993 22:50:35 GMT A-6. The sequence is a bunch of terms a_1, a_2, ... with each a_n=2 or 3. Let n_m be the location of the (m+1)st 2. (so n_0=1, n_1=4, etc). Then n_m-n_{m-1} is one more than the number of non-2's (i.e. 3's) in the m-th block. The definition of the origianl sequence makes this exactly a_m. So the n's can be computed from the m's (and vice versa, of course): n_m=(a_m+1)+(a_{m-1}+1)+...+(a_1+1)+1 =1+m+\Sum_{k=1}^{k=m} a_m. Now, a statement a tad stronger than the statement of the original problem is the assertion n_m=1+\floor{r m}. The existence of such an r is equivalent to a non-empty intersectin of the intervals of length 1/m ending at n_m/m. From the formula above, we need r-1 to be in the intersection of intervals of length 1/m starting at (1/m)\Sum_{k=1}^{k=m} a_k Therefore (assuming the limit exists) the only possible value of r-1 is lim_{m\to\infty} (1/m)\Sum_{k=1}^{k=m} a_k. (Isn't this what they call a C\`esaro sum?) Notice that if indeed n_m is about 1+rm, then the number of such n's less than m is about m/r; that is, the number of 2's among the first m terms is about m/r. Since the rest are 3's, the sum is 3m - m/r or so. This gives the equation r-1 = 3- (1/r), r = 2 + sqrt(3) = 3.732... (Actually the other root r=2-sqrt(3) probably also meets the conditions of the original problem without meeting the stronger condition I asserted: each n_m is 1+floor{r m'} for _some_ m', no necessarily with m=m'.) I apologize for the lack of sound epsilonics. I'm sure an accurate estimate of n_m bootstraps to an estimate of n_{rm} or n_{3m} using the preceding paragraphs, but as it is dinner time I think I will go and leave the brilliant and brief derivation to the usual hotshots. ============================================================================== B1 From: dsavitt@unixg.ubc.ca (David Savitt) Date: 5 Dec 93 09:09:08 GMT Note that in particular, with k>=1 we need 1992/1993 < (n-k)/n < 1993/1994, i.e. after rearragement 1993k y > 2x so draw this line in our unit square. For the case where the closest integer is 2 , 3/2 < x/y < 5/2 so draw the lines y=2/3x and y=2/5x. Similarly for 4,6,8... The probability that we are looking for is simply the sum of the areas in the unit square which are: - above the line y = 2x - between y = 2/3x and y=2/5x - between y = 2/7x and y=2/9x etc... call this probability P P = 1/4 + 1/2[2/3 - 2/5 + 2/7 - 2/9 + 2/11 ...] note that pi/2 = 2 - 2/3 + 2/5 - 2/7 + 2/9 - ... so 2 - pi/2 = 2/3 - 2/5 + 2/7 - 2/9 .... Hence P = 1/4 + 1/2[2 - pi/2] = 5/4 - 1/4 pi Sorry my answer was long, hope it was clear. ============================================================================== B4 From: eillihca@drizzle.StanFord.EDU ( Achille Hui, the Day Dreamer ) Date: 08 Dec 93 19:47:50 GMT Let a = min{f(x)/g(x), x in [0,1]}, b = min{g(x)/f(x), x in [0,1]} and WOLOG, let's consider the case a <= b. The continuity and positivity of f and g over [0,1] implies those for f/g. Since [0,1] is closed, there is a x such that f(x)/g(x) = a. Let's denote it as x_min. Notice K(x_min,y) > 0, g(y) - a f(y) >= 0 for all y and / 1 | K(x_min,y)(g(y) - a f(y)) dy = f(x_min) - a g_x(x_min) = 0. | / 0 This implies g - a f = 0. Similarly, we can show f - a g = 0 and hence f = a g = a^2 f -> a^2 = 1 -> a = 1 -> f = g. QED. ============================================================================== B5 From: gedgar@magnus.acs.ohio-state.edu (Gerald A Edgar) Date: 6 Dec 1993 16:22:00 GMT >If we write a12 for the distance between points 1 and 2, and so on, >then the condition that the points be co-planar is: > > [ 2 2 2 ] > [ 0 a12 a13 a14 1 ] > [ ] > [ 2 2 2 ] > [ a21 0 a23 a24 1 ] > [ ] > [ 2 2 2 ] > det [ a31 a32 0 a34 1 ] = 0 > [ ] > [ 2 2 2 ] > [ a41 a42 a43 0 1 ] > [ ] > [ 1 1 1 1 0 ] > >Now if all the a's are odd integers, then all squares are =1 mod 8, >and the determinant at the end is > > > [ 0 1 1 1 1 ] > [ ] > [ 1 0 1 1 1 ] > [ ] > det [ 1 1 0 1 1 ] = 4 mod 8 > [ ] > [ 1 1 1 0 1 ] > [ ] > [ 1 1 1 1 0 ] > >The determinant is 4 mod 8, so not zero, >so the points are NOT co-planar. ============================================================================== B6 From: Garth Payne Date: Tue, 7 Dec 1993 14:09:46 -0500 Here is an outline of a solution which is right in spirit if not in detail. We show that {a,b,c} with 0=0). ==============================================================================