From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: sci.math Subject: Re: Two 1990 Putnam problems problems Message-ID: <5167:Dec617:24:0690@kramden.acf.nyu.edu> Date: 6 Dec 90 17:24:06 GMT References: <5246:Dec201:45:4390@kramden.acf.nyu.edu> Organization: IR Lines: 18 Posted: Thu Dec 6 18:24:06 1990 In article jrussell@ibm.com writes: > brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > > Problem A-2 > > Is \sqrt{2} the limit of a sequence of numbers of the form > > \root3{n} - \root3{m}, (n, m = 0, 1, 2, ...) ? Justify your answer. > Is this right? Should it be 'n, m \in {0, 1, 2 ...}'? Yes, it should, but on the exam it isn't. > > Problem B-6 [ ... ] > I'm not sure I follow this without the picture. What are support lines? > (lines tangent to S above and below?) Basically. Support lines intersect the set and divide the plane into two half-planes, one of which fully contains the set. ---Dan ============================================================================== From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: sci.math Subject: Re: 1990 Putnam problems, with some unofficial solutions Message-ID: <27162:Dec405:15:3690@kramden.acf.nyu.edu> Date: 4 Dec 90 05:15:36 GMT References: <5246:Dec201:45:4390@kramden.acf.nyu.edu> Organization: IR Lines: 27 Posted: Tue Dec 4 06:15:36 1990 In article squash@math.ufl.edu (Jonathan King) writes: > Is there not a (famous (?)) theorem about the area of a (not necessarily > convex) polygon with vertices on the integer lattice? Pick's theorem: Take a simply connected lattice-vertex polygon with no repeated vertices (really, a simple closed lattice-point cycle). Let A be the area, B the number of lattice points on the boundary, and I the number of interior lattice points not on the boundary. Then A + 1 is I + B/2. The theorem can be generalized to non-simply-connected polygons (the 1 in the formula is the number of disjoint connected regions, minus the number of holes), or to higher dimensions. > 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. Rather than thinking about the problem, just say ``It's not true syntactically in a general ring, so it's false.'' Then write down random A and B with product 0 on and above the diagonal (this is easy), and see whether BABA is 0. Repeat for sizes 2, 3, 4, etc. until finding a counterexample (which shows up at dimension 3). ---Dan ============================================================================== From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: sci.math Subject: Re: 1990 Putnam problems Message-ID: <26957:Dec405:03:5990@kramden.acf.nyu.edu> Date: 4 Dec 90 05:03:59 GMT References: <1990Dec2.181500.7809@zaphod.mps.ohio-state.edu> <58276@brunix.UUCP> <1990Dec4.004553.8652@lily.waterloo.edu> Organization: IR Lines: 14 Posted: Tue Dec 4 06:03:59 1990 In article <1990Dec4.004553.8652@lily.waterloo.edu> cmspring@lily01.uwaterloo.ca writes: > I have yet to see a solution posted here to problem A6 of this year's > Putnam. Huh? As I said, one solution to the problem as stated is ``the sum of {10 - f\binom g}{10 - g\binom f} for f and g between 0 and 10.'' While a closed-form solution for all n (not just 10) is a worthwhile exercise, it is beyond the requirements of the problem. Our focus in presenting a solution should always match the student's focus in finding a solution. I'll post a complete set of solutions (along with possibly interesting information, such as extensions to more general cases) soon. ---Dan ============================================================================== From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: sci.math Subject: Re: 1990 Putnam problems Message-ID: <27424:Dec405:29:1490@kramden.acf.nyu.edu> Date: 4 Dec 90 05:29:14 GMT References: <1990Dec2.181019.7745@zaphod.mps.ohio-state.edu> <1990Dec2.181500.7809@zaphod.mps.ohio-state.edu> <58276@brunix.UUCP> Organization: IR Lines: 12 Posted: Tue Dec 4 06:29:14 1990 In article <58276@brunix.UUCP> thc@cs.brown.edu (Thomas Colthurst) writes: > A-2: > 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. Well, my point was to give an entirely elementary proof. It is easier to work with strict bounds than with series. ---Dan ============================================================================== From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: sci.math Subject: Re: 1990 Putnam problems Message-ID: <27336:Dec405:27:1090@kramden.acf.nyu.edu> Date: 4 Dec 90 05:27:10 GMT References: <1990Dec2.220245.21222@cec1.wustl.edu> <4440@idunno.Princeton.EDU> Organization: IR Lines: 43 Posted: Tue Dec 4 06:27:10 1990 In article <4440@idunno.Princeton.EDU> tycchow@phoenix.Princeton.EDU (Timothy Yi-chung Chow) writes: > A4: 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. Yes, it certainly is. The Putnam should not become a test of which students were lucky enough to find the right problem books or listen to the right Halmos lectures that year. > A5: One way to come up with a counterexample is to notice that if [ ... ] > It takes only about five minutes of playing around to find something > that works. Just construct random matrices whose product is sub-lower-triangular, then multiply them the opposite way and check for any element being 0. There's no need to think about it. > A6: A friend of mine (Johnny Fan) said he thought the answer was the > 21st Fibonacci number. Can anyone else confirm this? Depends how you count Fibonacci numbers. > Another question: > how do you think the grading for this problem will go? The number is > clearly too large for them to expect anyone to give the answer in > standard decimal form, but do you think they will give full credit for > a double sum of binomial coefficients? The problem asked for a solution neither in simplest form nor even in closed form. Obviously this was a mistake, but it means that the problem has difficulty level around A-2. It should be graded at exactly that level. > B1: Rather a silly question, which probably means that the graders will > insist on details like mentioning that the derivative of an integral of > f is equal to f only if f is continuous. Indeed. Popular rumor says that this has always been the case for B-1, though someone who has graded Putnams tells me otherwise. ---Dan ============================================================================== From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: sci.math Subject: Re: 1990 Putnam problems, with some unofficial solutions Message-ID: <5411:Dec202:08:0890@kramden.acf.nyu.edu> Date: 2 Dec 90 02:08:08 GMT References: <5246:Dec201:45:4390@kramden.acf.nyu.edu> Organization: IR Lines: 16 Posted: Sun Dec 2 03:08:08 1990 In article <5246:Dec201:45:4390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > Problem A-4 [ ... ] > Once again the Putnam features an old problem. Anyone keeping track of > how many times in the last few years this exam has repeated problems > brought up in lectures by Halmos, or presented in MAA journals? [ followed by some random musings about the proof ] > Something like that, > anyway. So 4 punches are necessary and sufficient. Well, I'm told that I misremembered the theorem from when I heard it from Halmos a few years ago, and that three punches suffice. I'm also told that Newman's Problem Seminar book presents the problem. I remain sufficiently disgusted about the latter to care about the former. ---Dan