[As has become my custom I have collected comments about the 2002 Putnam exam from newsgroups and email. For responses to a particular problem, be sure to scan for problem number, as many people might comment separately.] ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Putnam SPOILERS (Was Re: William Lowell Putnam 2002) Date: 8 Dec 2002 05:36:20 GMT In article , I wrote: >Even they should be finished now, so I'll post >the problems, but I won't post my solutions until later tonight, just in >case I've misunderstood the timetables. > >(I've got my usual hackneyed solutions for most of the problems, >but I didn't do A4 or B4. Maybe I'll work on it a bit more later.) I have a long enough bicycle ride home that I finished B4, and have already received a response to A4 in email. So here are some answers. Usual caveats apply (e.g., these answers would likely be considered insufficient by graders who don't know that I know what I'm talking about, and might foolishly insist that I get all the details right.) Comments: This year I noticed an unusually high fraction of games and probability questions, and an unusually low proportion of algebra/group theory and differential equations. I thought the morning questions were easier than the afternoon ones, but all in all this was a reasonable level of difficulty and, as always, a lot of fun. I will save these answers, and other good ones which appear in the newsgroup, where I have been putting Putnam discussions for some years: http://www.math.niu.edu/~rusin/problems-math A1. Just get the recurrence from the product rule: P_n(x) = (x^k - 1)^(n+1) . d/dx{ P_{n-1}(x) . (x^k - 1)^(-n) } = (x^k - 1)^(n+1) . { P_{n-1}'(x) . (x^k - 1)^(-n) + P_{n-1}(x) . (-n)(k x^{k-1}) (x^k - 1)^(-n-1) } = (x^k - 1) . P_{n-1}'(x) + (-n) k x^{k-1} . P_{n-1}(x) Substitute x = 1: P_n(1) = n (-k) P_{n-1}(1). Since P_0(1) = 1, induction on n gives P_n(1) = n! (-k)^n. A2. Richard Blecksmith embarrassed me by claiming this was the easiest Putnam question ever, but I missed this trick: Pick any point P1. Pick P2 among the other four, subject only to being different from the antipode -P1. Draw the great circle through P1 and P2. This defines two closed hemispheres whose union is the whole sphere, so P3, P4, P5 must be in the two of them, hence at least one of those two hemispheres contains at least two of P3, P4, and P5. That's the hemisphere you want. My argument was much more cumbersome but perhaps sheds light on the more delicate question of when _open_ hemispheres would suffice. We can parameterize the open hemispheres by their center point; for example, the hemispheres which _don't_ contain P1 have centers which collectively fill another hemisphere. That's the hemisphere which is "bad" for P1. Likewise there's a hemisphere of centers which would be bad for P2. This leaves only a crescent of centers which are "good" for both P1 and P2 at once. (You might want to draw a picture showing the crescent extending from North to South Poles.) Likewise you can find a crescent of good points for P3 and P4. There are then only two cases: either one of the poles (North or South) lies in the good crescent for P3 and P4 (leaving the other pole bad for both P3 and P4) or else each of the poles is good for one of P3 or P4 and bad for the other. In the former case that pole is good for P1 through P4 and we're done: the hemisphere we want extends from that pole to the equator. In the latter case, we simply note that one of the two poles is good for P5 and the other is bad, giving a center for a hemisphere which contains P1 and P2, one of P3 or P4, and P5; again we're done. I like Richard's argument better, though on some level they say the same thing! A3. Symmetry! That's all a mathematician needs to hear, but the details take a while to write out. Let's write N for the set {1, 2, ..., n}. Note that f : N --> N given by f(x) = n+1 - x is a bijection of order 2, and has no fixed points when n is even, and only fixes (n+1)/2 if n is odd. Extend f to a bijection of the power set of N (also of order 2) by letting it act pointwise. The fixed points of f here are the subsets of N which are unions of pairs { a, f(a) } and, if n is odd, the singleton { (n+1)/2 }. Now, a non-empty set S = { a_i, 1 <= i <= k } is counted by T_n iff sum a_i = 0 mod k. We observe that f(S) is another set of the same cardinality k having element-sum sum f(a_i) = (n+1)k - sum a_i, which is again = 0 mod k. So the subsets we wish to count are preserved (as a family) by f. In particular, most of the sets to be counted occur in pairs { S, f(S) }, giving an even number of them. It remains to enumerate only the counted sets S which are f-invariant. But this is very easy: for any f-invariant set S, we have already seen that S consists of (say) m pairs which individually sum to n+1, plus possibly the singleton (n+1)/2; so S has cardinality 2m or 2m+1 and element-sum (n+1)(m) or (n+1)(m) + (n+1)/2 respectively. When n is even, the first is never a multiple of 2m (and the second cannot occur), so NONE of the f-invariant sets S are counted. When n is odd, (n+1)m IS a multiple of 2m, and also (n+1)m + (n+1)/2 IS a multiple of 2m+1, so that ALL of the f-invariant sets S are counted, except the empty set which was excluded by definition. Well, there are (n-1)/2 f-invariant pairs and the invariant singleton, giving 2^( (n-1)/2 + 1 ) possible unions S of these, and in particular an odd number of non-empty such S. So T_n counts a set of f-orbits (an even number of S's) and either zero or 2^(positive) - 1 f-invariant S's, depending on whether n is even or odd. In either case, T_n = n mod 2. As I remarked to one of our contestants, a student taking number theory this term, this pairing off is just how we prove Wilson's theorem. A4. I didn't get this. One ought to be able to draw a game tree showing all options, then prune the tree because |det(A)| is invariant under all row and column operations and the taking of transpose. But it seemed to me that still leaves too many options to work through. I am lazy, you know. Well I just got this corroboration from Petr Lisonek : >In your sci.math post you wrote that you don't have A4 yet. It's easy. >W.l.o.g. assume 1 starts in (1,1) then 0 replies in (2,2) and 0 wins. >By symmetry there are four cases to consider: >1's second move is (1,2) or (1,3) or (2,3) or (3,3). They are all similar. > >For example, if 1's second move is (1,2) then 0 plays (2,3) forcing 1 to (2,1) >then 0 plays (3,3) forcing 1 to (1,3) then 0 plays (3,2) and the last two rows >will end up equal. The remaining three cases are similar. A5. Prove by induction on height (where h( p/q ) = max(p,q) ). We see 1 = 1/1 in the set already; that's the only rational of height 1. If x = p/q > 1, then p > q so the height of x is p and the height of x-1 is smaller (it's max(p-q, q) < p ). By induction we have x-1 = a_{n-1}/a_n for some n. Then x = (a_n + a_{n-1})/a_n = a_{2n} / a_{2n+1}, which is therefore in the set too. So if the "even" terms of the sequence of ratios are used to give the large x's from early parts of the sequence, then the "odd" terms must give us a way to get the small x's from earlier in the sequence too, right? With that clue we can work backwards to figure out that the argument is supposed to go like this: If x = p/q < 1, then p < q so the height of x is q and the height of x/(1-x) = p/(q-p) is smaller (it's max(q-p,p) < q ). By induction we have y=x/(1-x) = a_{n-1}/a_n for some n. Then x = y/(1+y) = a_{n-1}/(a_n + a_{n-1}) = a_{2n-1} / a_{2n}, which is therefore in the set too. A6. The series converges for b=2 only. Look at the partial sums S_N = sum_{n=1}^{N} 1 / f(n) . These steadily increase, as f is positive, so the question of whether the S_N converge to anything can be resolved by looking at any subsequence of them containing infinitely many N. Very well, consider the cases with N = b^D - 1, that is, add the terms corresponding to n's with fewer than D digits. Collecting terms by numbers of digits we get S_N = sum_{d=1}^{D-1} sum_{n=b^d}^{n=b^(d+1)-1} 1 / {n f(d)} = sum_{d=1}^{D-1} 1/f(d) sum_{n=b^d}^{n=b^(d+1)-1} 1 / n > sum_{d=1}^{D-1} 1/f(d) int_{n=b^d}^{n=b^(d+1)} 1 / n dn = sum_{d=1}^{D-1} 1/f(d) log(b) = log(b) S_{D-1} (using the integral test). So now if log(b) then the S_N cannot converge to a limit S since that would give S >= log(b) S, a contradiction. (Clearly S > 0 ! ) That leaves only the case b=2, which can be done similarly. "We leave to the reader" the task of establishing an inequality of the form S_{2^D - 1} < A + log(2) S_{D-1} as above; then by induction on N we establish a geometric series S_N < A ( 1 + log(2) + log(2)^2 + ... ) which bounds S_N since log(2) < 1. Of course a bounded increasing sequence converges, so the S_N have a limit, and the series converges. B1. The answer is 1/99. More generally, if P(k,n) is the probability that she has precisely k successes among her first n attempts, then P(k,n) = 1/(n-1) if 0 < k < n, and = 0 otherwise. This is easily established by induction on n, since it's true for n=2 and then P(k,n) = P(k-1, n-1) . (k-1)/(n-1) + P(k,n-1) . (1 - k/(n-1) ) (that is, she gets a total of k among the first n either by making the n-th shot after k-1 successes, or by missing the n-th after k successes). Substitute 1/(n-2) for the prior probabilities and simplify. The cases k<=0, k=1, k=n-1, and k>=n should be treated separately. B2. This problem is much easier for me to understand dually: Pick a point inside each face and connect the points chosen from adjacent faces. This partitions the surface of the polyhedron into a bunch of regions. The 3-edges-from-each-vertex rule now means these new regions are all _triangles_. So in my new configuration, the players alternately select vertices, and the winner is the first one to select the three vertices of a triangle. Here is the first player's strategy in brief: pick any vertex P, and study its neighborhood (a collection of N >= 3 triangles forming a ring around P, bounded by a path consisting of N vertices distinct from P). If player 2 takes one of these N vertices, say Q, player 1 should choose a vertex R other than the two neighbors of Q from this path. (If player 2 takes some other vertex not in the path, player 1 can choose R at random from this path.) Then the edge from P to R is shared by two triangles, and player 2 can take the remaining vertex from only one of them, leaving player 1 free to take the remaining vertex from the other triangle containing P and R. Player 1 wins. There are some caveats. First, this process assumes that there IS a point R in the path which is neither Q nor its two neighbors, in other words, we need to assume we can find a vertex P which has N >= 4 adjacent vertices in that path. (In the original description of the game, that means we need to find a face with four or more sides.) This we can do because Euler's formula v - e + f = 2 implies that the only polyhedron made exclusively of triangles and having exactly three edges incident at each vertex will be a tetrahedron, and we were told there are five or more faces. Second, we must know that Q has only two neighbors on the path. This can be violated topologically if two of the original faces share more than one edge (i.e., in the dual picture, if there is more than one path from P to Q; equivalently, Q "shows up twice" in the path). But in a polyhedron the faces are the convex hull of their vertices, and if two faces share two edges, they will share three non-collinear vertices, hence lie in the same plane, which is a degenerate configuration I assume we exclude in the definition of 'polyhedron'. Comment: the two players should have names, like Alice and Bob (so that the test-takers will be ready for a cryptography course!) B3. No need to restrict to integers; it's true for all real n > 1 (and n=1 is OK if we change the last "<" to "<="). In terms of x = 1/n, we need to show that for x in (0, 1) we have x/2 < 1 - e(1-x)^(1/x) < x I'm sure I'm missing some simple application of the Mean Value Theorem, say, but I just decided to follow my nose: we must prove that log(1- x/2) > 1 + log(1-x) /x > log(1 - x) for these x. Well, the three terms equal (have limit equal to) zero as x=0, we we only have to show that they diverge appropriately as x increases. Well, fine then, let's show that the derivatives of the differences are positive. The easy one is on the right: we need (after some algebra) for (ln(1-x) + x)/x^2 to be negative, i.e. ln(1-x) < -x. The Taylor series on the left has all negative coefficients; done. The other one is more trouble. We need the derivative of the difference to be positive. I make it out to be 1/x^2 times x(x^2 - 2x +2)/(1-x)(2-x) + log(1-x) A glance at the Taylor series shows this WILL be positive for small positive x, but how far this continues is not clear. At a minimum the positivity will continue as long as _its_ derivative stays positive, and I make that one out to be (x^2 - 5x + 5) x^2 / (1-x)^2 (2-x)^2 which is indeed positive for x < (5 - sqrt(5))/2 = 1.35... and certainly for x<1. B4. We can define a strategy recursively: starting from any linearly-ordered set of N elements, we (a) guess the largest element first. (With probabilty 1/N we have won; with probability (N-1)/N we will be told the correct answer is smaller.) (b) guess the SECOND largest element second. (If we arrive at step (b), we will win with probability 1/(N-1); we will with probability 1/(N-1) be told the answer is _larger_ -- which of course we will guess to be the largest element, on our next term; and with probability (N-3)/(N-1) we will be told the answer is smaller.) (c) repeat the process with the (N-3)-element set which remains. If the probabilty of winning this game on an odd round (using this strategy) is p(N) then we thus have p(N) = 1/N + (N-1)/N ( 0 + 1/(N-1) + (N-3)/(N-1) p(N-3) ) so N p(N) = 2 + (N-3) p(N-3) It's clear that p(1)=1 and p(2)=1/2, and p(3)=2/3 can be checked as an example of our strategy; in each case N p(N) = floor( (2N+1)/3 ). Then the inductive formula above proves that this is true for all N. Thus we conclude p(N) = floor( (2N+1)/3 ) / N, and in particular p(2002) = 1335/2002, which is just a tad over 2/3. B5. Too many variables for my taste! That probably means I'm missing a slick answer, but this works well enough. Let's just look for numbers which are palindromes of the special form "1a1", that is, n = b^2 + a b + 1 for some integers a and b with 0 <= a < b. We only need n-1 to be a product b(b+a) of two factors, the larger of which is less than twice the smaller. We can do this for example by taking n-1 to be a number of the form product m_i((m_i)+1) where the m's come over a large set M of numbers close together. For then given any disjoint decomposition M = M1 union M2 we obtain a factorization n-1 = D1 D2 where D1 is the product of the m_i in M1 and the product of the (m_i)+1 with m_i in M2, and D2 is obtained the other way around. These two factors are close enough to each other when their ratio is between 1/2 and 2; well, the ratio is product_M1 ( 1 + 1/m_i ) / product_M2 (1 + 1/m_i) and this is never worse than than when one M_i is empty. In that case, we can estimate the ratio with logs: the log is about sum_M ( 1/m_i ) . We can keep this small even with lots of m's if we start with large enough ones. Just to be careful, let's make sure that the factorizations D1 D2 are all distinct; we can, for example, insist that M consist of nothing but primes in the range P <= m_i < 2P for some fixed number P. In that case, all the prime divisors of factors m_i + 1 will be less than P, so we can recover M1 and M2 from D1 and D2, meaning that there are as many factorizations now as there are subsets of M. So if we let M be all the primes between P and 2P, then there are about P/log(P) elements in M. The sum sum_M ( 1/m_i ) of the previous paragraph is approximately int_P^{2P} dx / (x log x) , which I reckon to be roughly log(2)/log(P). In particular, this will certainly stay sufficiently small when P grows. Taking P --> oo, we can have as many primes as we like in M, giving as many distinct factorizations as we like for n-1, and in particular, a number of the form n = 1 + product_{p=prime, P < p < 2P} p(p+1) will be a palindrome "1a1" in a number of bases exceeding 2002 if we simply choose a large enough value of P. B6. One word: Vandermonde. Treat x,y,z as formal variables, that is, consider this determinant as an element of the ring F[x,y,z] where F is the field of p elements. Since the p-th power map f is a ring-homomorphism here, it follows that if we substitute z = A x + B y for any elements A,B in F, we will have z^p = A x^p + B y^p and likewise for the p-th power of this. (I suppose I'm actually working in the ring F[x,y][z] when I start talking about substitutions!). This means that for any elements A,B, the matrix will be singular when we substitute this way, since the columns will be linearly dependent. It follows that this polynomial has all the linear forms z - (Ax+By) as factors. There are p^2 of them, and the determinant is a polynomial of degree p^2 in z, so we have factored the determinant up to a constant (meaning an element of F[x,y]). In similar fashion the determinant is a multiple of each of y - A x and then is a multiple of x itself. This accounts for p^2 + p + 1 linear factors of a polynomial of overall degree p^2 + p + 1. But the coefficients of z^p^2 y^p x are 1 both in the determinant and in the product of our linear forms, so our factorization is complete. This is really a classic argument for such determinants. ============================================================================== From: Robin Chapman Date: Sun, 08 Dec 2002 13:39:56 +0000 Sean wrote: > Here they are: > > Problems: http://www.unl.edu/amc/a-activities/a7-problems/putnam/2002.pdf > Solutions: http://www.unl.edu/amc/a-activities/a7-problems/putnam/2002s.pdf A5. This exact sequence is discussed in a paper "Recounting the Rationals" by Neil Calkin and Herb Wilf which appeared in the Monthly in 2000. Also an equialent problem appeared in a Mothly problem (10906) in 2001 set by Don Knuth. This is probably too well-known to make a suitable problem. B4. There's a simple explicit strategy that works. Choose, in sequence, 1, 3, 4, 6, 7, 9, 10 , ... as far as one can. One wins if the secret number n = 1 (mod 3) and loses if n = 0 (mod 3). If n = 3k+2 one will choose 3k+1 and then 3k+3 and must then choose 3k+2 on an odd guess so one still wins. The probability of winning is thus 1335/2002. Of course, 2002 can be replaced by any N = 1 (mod 3). B5 I came up with an idea that mixed both Bernstein's ideas. Let r = uv where u < v < 2u. Then in base u, r + 1 has digits 1 k 1 where k = v-u. One needs to find an r with a lot of these close factorizations. I took r = n!^2 with n large. We can take u = n! t/(t+1) (and do v = n!(t+1)/t) where 3 <= t <= n-1. -- Robin Chapman, www.maths.ex.ac.uk/~rjc/rjc.html "His mind has been corrupted by colours, sounds and shapes." The League of Gentlemen ============================================================================== From: The World Wide Wade Date: Sun, 08 Dec 2002 07:19:24 GMT In article , rusin@vesuvius.math.niu.edu (Dave Rusin) wrote: > I'm sure I'm missing some simple application of the Mean Value Theorem, > say, but I just decided to follow my nose: we must prove that > log(1 - x/2) > 1 + log(1-x) /x > log(1 - x) > for these x. One way to get this is to use log(1-x) = -(x + x^2/2 + x^3/3 + ...) for 0 < x < 1. In very short order the above inequality turns into x/2 + (1/2)*(x/2)^2 + (1/3)*(x/2)^3 + .... < x/2 + x^2/3 + x^3/4 + ... < x + x^2/2 + x^3/3 + ... The first inequality follows from 1/[n*2^n] < 1/(n+1) for n > 1, and the second inequality is obvious. ============================================================================== From: Fred Galvin Date: Sun, 8 Dec 2002 02:08:51 -0600 On 8 Dec 2002, Dave Rusin wrote: > A3. Let n>=2 be an integer and T_n be the number of non-empty subsets > S of {1, 2, 3, ..., n} with the property that the average of the > elements of S is an integer. Prove that T_n - n is always even. T_n - n is the number of non-singleton sets S with the stated property. The non-singleton sets S come in pairs: an S which contains its average as an element is paired with one that doesn't. More generally, let X be *any* n-element set of numbers, and let T_X be the number of nonempty subsets S of X with the property that the average of the elements of S is in X. Then T_X - n is always even. ============================================================================== From: Fred Galvin Date: Sun, 8 Dec 2002 11:28:36 -0600 Maybe this is a better way to put it: Let Y be any finite set of numbers, let X be an n-element subset of Y, and let t be the number of nonempty subsets S of Y with the property that the average of the elements of S is in X. Then t - n is even. It suffices to prove the statement for the case n = 1, and that case is utterly trivial. This must be one of the easiest Putnam problems ever! -- It takes steel balls to play pinball. ============================================================================== From: Noam Elkies Date: Sun, 8 Dec 2002 20:57:23 -0500 (EST) To: rusin@math.niu.edu Subject: B6 FYI: B-6 on yesterday's Putnam is the special case n=3, f=1 of a theorem that goes back to the 19th century! See Moore, E.H.: A two-fold generalization of Fermat's theorem. Bull. AMS, Vol.2 #7 (4/1896), 189--199. [Fermat's theorem may be viewed as the factorization of x^p-x mod p, which amounts to the factorization of the 2*2 Moore determinant [x,y; x^p,y^p]. Moore's generalization is "two-fold" in that it applies to n*n matrices over the field of p^f elements for any n and f.] Such determinants can also be used to develop the invariants of GL_n(F_q) acting naturally on polynomials in n variables, as first obtained some 90 years ago in Dickson, L.E.: A fundamental system of invariants of the general modular linear group with a solution of the form problem. Trans. AMS, Vol.12 (1911), 75--98. One exposition of this approach can be found in the first few sections of my paper Linearized algebra and finite groups of Lie type. I: Linear and symplectic groups. Pages 77--107 in _Applications of curves over finite fields_ (Seattle, 1997) = Contemp. Math. 245, Providence: AMS, 1999. Sincerely, --Noam D. Elkies ============================================================================== From: Fred Galvin Date: Sun, 8 Dec 2002 22:51:01 -0600 On 8 Dec 2002, Dave Rusin wrote: > B1. The answer is 1/99. More generally, if P(k,n) is the > probability that she has precisely k successes among her first n > attempts, then P(k,n) = 1/(n-1) if 0 < k < n, and = 0 otherwise. > This is easily established by induction on n, since it's true for > n=2 and then > P(k,n) = P(k-1, n-1) . (k-1)/(n-1) + P(k,n-1) . (1 - k/(n-1) ) > (that is, she gets a total of k among the first n either by making > the n-th shot after k-1 successes, or by missing the n-th after k > successes). Substitute 1/(n-2) for the prior probabilities and > simplify. The cases k<=0, k=1, k=n-1, and k>=n should be treated > separately. I don't think you need to use induction. There are 98!/49!49! different sequences of hits and misses that end up with 50 of each after 100 shots (given the stipulation that she started with a hit and then a miss). By just multiplying the conditional probabilities, it's easy to see that each of those sequences has the same probability of occurring, namely 49!49!/99!. Hence the probability of ending up with 50 hits and 50 misses is (98!/49!49!)*(49!49!/99!) = 1/99. Of course the same goes for getting m hits and n misses in the first m+n shots, provided m and n are positive integers: each of the C(m+n-2,m-1) sequences occurs with probability (m-1)!(n-1)!/(m+n-1)!. -- It takes steel balls to play pinball. ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Date: 9 Dec 2002 21:34:09 GMT >Anyway, here is Dave's solution to problem B4: >> >> B4. We can define a strategy recursively: starting from any linearly-ordered >> set of N elements, we >> (a) guess the largest element first. (With probabilty 1/N we have won; >> with probability (N-1)/N we will be told the correct answer >> is smaller.) >> (b) guess the SECOND largest element second. (If we arrive at step (b), >> we will win with probability 1/(N-1); we will with probability >> 1/(N-1) be told the answer is _larger_ -- which of course we will >> guess to be the largest element, on our next term; and with >> probability (N-3)/(N-1) we will be told the answer is smaller.) >The question I have is in part (b). How can we be told that the answer >is larger if this has already been ruled out in step (a)?? Sorry, I was unclear. I meant the second-largest number _remaining_. Begin by guessing "2002", which is very likely incorrect and we are told to guess lower. So now our choices are 1, 2, ..., 2001. This time (meaning it's an even-numbered turn) we guess not 2001 but 2000. We win (boohoo!) with probability 1/2001 but with equal probability we will be told, "No, go higher" which will mean a win next time (yay!). Most likely, of course, we are told to go lower, so we start the process over again with the set 1, 2, ..., 1999. I was trying to write a proof by induction and so started on the big end; it's probably clearer the way others have described it, starting on the small end (an isomorphic situation, as this is just a question about linearly ordered sets!). You guess 1, 3, 4, 6, 7, ... in turn until you either guess right or have a sure bet (e.g. if the right answer is "2"). ============================================================================== From: Fred Galvin Date: Mon, 9 Dec 2002 23:41:00 -0600 On Mon, 9 Dec 2002, Jaded Putnam Cynic wrote: [about Putnam A4] The case analysis for A4 is really quite simple. Player Zero has to occupy a row or a column or a 2-by-2 submatrix. Without loss of generality Player One opens with a(1,1)=1. Then Player Zero plays a(2,2)=0, and now there are 4 variations: I. a(1,2)=1, a(2,3)=0, a(2,1)=1, a(3,3)=0 and wins with the double threat of playing a(1,2)=0 or a(3,3)=0 on the next move. II. a(1,3)=1, a(2,3)=0, a(2,1)=1, a(3,2)=0 and wins. III. a(2,3)=1, a(3,2)=0, a(1,2)=1, a(3,1)=0 and wins. IV. a(3,3)=1, a(3,2)=0, a(1,2)=1, a(3,1)=0 and wins. ============================================================================== From: Fred Galvin Date: Tue, 10 Dec 2002 00:23:36 -0600 On Mon, 9 Dec 2002, Fred Galvin wrote: > The case analysis for A4 is really quite simple. Player Zero has to > occupy a row or a column or a 2-by-2 submatrix. Without loss of > generality Player One opens with a(1,1)=1. Then Player Zero plays > a(2,2)=0, and now there are 4 variations: > > I. a(1,2)=1, a(2,3)=0, a(2,1)=1, a(3,3)=0 and wins with the double > threat of playing a(1,2)=0 or a(3,3)=0 on the next move. Sorry, I mixed up variations. At the end of Variation I, Zero's threats are a(1,3)=0 and a(3,2)=0. > II. a(1,3)=1, a(2,3)=0, a(2,1)=1, a(3,2)=0 and wins. > > III. a(2,3)=1, a(3,2)=0, a(1,2)=1, a(3,1)=0 and wins. > > IV. a(3,3)=1, a(3,2)=0, a(1,2)=1, a(3,1)=0 and wins. ============================================================================== [A2] Date: Fri, 13 Dec 2002 08:49:47 -0500 From: Herman Rubin To: rusin@vesuvius.math.niu.edu On the points on a sphere lying in a hemisphere, one does not even need to assume that the first two are not antipodal, as any great circle will work. For the problem of an open hemisphere, I conjecture that 7 points will suffice to have four in an open hemisphere. That many are needed, as there can be three antipodal pairs. ============================================================================== From: Omer Angel Date: Wed, 18 Dec 2002 11:26:55 +0200 To: mailto:rusin@math.niu.edu Hi Dave, Two variations on the solutions you might be interested in: A2: This requires expressing 0 as a linear combination of the points with at least one negative coefficient, a 0 and at least one positive coefficient. Four points are in the same hemisphere iff their linear combination for 0 has different signed coefficients. This is easily shown to exist. B4: A general strategy is equivalent to a binary tree with 2002 vertices, labeled from left to right. We need a tree with as many vertices as possible with odd heights. 2n/3 is easily constructed, and clearly 1+2n/3 is the best possible (each vertex except the root has a father). Another solution is a tree with all leaves on levels 11 and 9. omer