The William Lowell Putnam Mathematical Competition and the Polya Problem-Solving Seminars 2007

The photo on the right was taken during the 2007 Putnam by Michael Helms --- it appears with his permission. Here is a photo of much of the group before the 2006 afternoon session, thanks to Alex Flury.

The Putnam is a challenging opportunity for you to test your mathematical mettle. In the 2006 competition, 3640 individuals participated, representing 402 colleges and universities across Canada and the U.S. The Stanford team placed sixth, and many individuals did very well. (I have a text file of results that I can forward to anyone interested.) The measure I look to is the number of competitors on the list of top performers sent out with the results; in 2006, we had 41, making us one of the top three.

The competition emphasizes ingenuity rather than knowledge, so freshmen are not at much of a disadvantage compared to seniors. Interest in or experience with problem solving is a plus. Not just math majors have done well; many recent winners have come from nearby disciplines, including physics, computer science, and engineering.

Completely solving even one of the twelve problems is a significant achievement, and in almost all years would place you well above the median. (Keep in mind that the particpants are self-selected from among the best in the continent.)

• The introductory meeting will take place Monday Oct. 1, time 5:15-5:45, in 380-383N (in the corner of the third floor of the math department). Here is the introductory poster. Here is the introductory handout.
• Meetings: the Polya Problem-Solving Seminars are informal dinner-time problem solving practice sessions this fall quarter, on Mondays 5:15-6:45. (Rough schedule: 5-5:15 beforehand, people can drop by to discuss ``left-overs'' from the previous week. 5:15-5:30: short discussion of new technique. 5:30-6:15: work on problems. 6:15-6:45: eat pizza, watch ``volunteers'' present solutions and explain how they thought about the problems.) Some faculty and graduate students always turn up with wise words. Practice problems will include some on the topics discussed, and some others. Handouts will appear here.
  • Monday, October 8: general problem-solving strategy, induction, and the pigeonhole principle. (We start with this every year.)
    Problems.
    Problem of the week: I saw this when I went to have coffee with a google mathematician, at the Red Rock Cafe on Castro Street in Mountain View, and it is undoubtedly still there. It was taped to the counter by the cash register. Find positive integers n and a_1, ..., a_n such that a_1+...+a_n=100 and the product is as large as possible. I asked if anyone solving it would get some sort of prize or a free coffee, but they laughed, and said that around here, lots of people could solve it, so all they could give was a warm smile. That's one of the great things about living in Silicon Valley.
  • Monday, October 15: number theory.
    Problems.
    Problem of the week: On Thursday, I gave a talk to alumni, in which I explained (amongst other things) why Fibonacci numbers turn up in nature. The explanation went through the following problem. I heard it from Prof. Greg Kuperberg at UC Davis. Consider a circle whose circumference is the golden mean ( (1 + root(5)/2, approx. 1.61803). Start at any point on the circle, and take some number of consecutive steps of arc length one in the clockwise direction. Number the points you step on in the order you encounter them, labeling your first step P_1, your second step P_2, and so on. Show that when you stop, the difference in the subscripts of any two adjacent numbers is a Fibonacci number. (from the 2nd ed. of A Mathematical Mosaic, p. 163)
  • Monday, October 22: recurrences.
    Problems.
    Problem of the week: Sylver coinage. This problem is from Simon Rubinstein-Salzedo, who came to these seminars as a high school, and has just started his Ph.D. here. Two players take turns naming positive integers that are not sums (with repetition) of previously named positive integers, with the player who names 1 being the loser. Prove that the game must end. Then prove that the first play can win.
  • Monday, October 29: complex numbers.
    Problems.
    Problem of the week: the ``Lights-out'' game. Suppose n >= 2 light bulbs are arranged in a row, numbered 1 through n. Under each bulb is a button. Pressing the button will change the state of the bulb above it (from on to off or vice versa), and will also change the state's neighbors. (Most bulbs have two neighbors, but the bulbs on the end have only one.) The bulbs start off randomly (some on and some off). For which n is it guaranteed to be possible that by flipping some switches, you can turn all the bulbs off?
  • Monday, November 5: invariants and monovariants.
    Problems.
    Problem of the week: match wits with Bob Hough. You have a very big urn, and at the start of the game, there are twenty balls, two each numbered one through ten. At each turn, you throw out one ball, and Bob dumps in any (finite) number of his choice of balls with smaller (positive integer) labels. For example, if you throw out a ball labeled ten, Bob could dump in a million balls labeled four. But if you throw out a ball labeled one, then Bob can't do anything. You win if you can empty the urn. Can you win? What is your strategy?
  • Monday, November 12: probability and expected values.
    Problems.
    Website of the week: turning a sphere inside out. A video showing that you can turn a sphere inside out ("everting the sphere"). You're allowed to pass the sphere "through" itself, but you aren't allowed to crinkle its surface, or it will burst. This video was made by the Geometry Center. (Thanks to Cihan Baran for finding this!)
    Problem of the week (from Sound). There are a hundred prisoners numbered one to hundred, and a room with a hundred boxes numbered one to hundred. There are hundred slips of papers numbered 1 to 100; they are scrambled randomly, and one slip is placed inside each box. Each prisoner is led into the room and is allowed to inspect the numbers in up to 50 boxes of his choice. If all the prisoners see their own number in one of the boxes that they inspect, then they are all set free. The prisoners may initially agree on a strategy with which to open boxes, but after this no communication among them is allowed. Can their odds be better than 1/2<sup>100</sup>?
  • Monday, November 26: last regular meeting: Putnam problems and strategy.
    Problems.
    Problem of the week (proposed independently by both Bob Hough and Sound). Suppose that a rectangle is cut into finitely many smaller rectangles, with sides parallel to the larger rectangle's sides. Suppose also that each smaller rectangle has at least one side of integer length. Prove that the larger rectangle has at least one side of integer length.
• There will also be a Masterclass for a few experts (everyone is welcome), on Mondays (immediately after the regular seminar, roughly 7-8 unless 6:45-7:45 is much better).
  • Monday, October 8 problems.
  • Monday, October 15 problems.
  • Monday, October 22 problems.
  • Monday, October 29 problems.
  • Monday, November 5 problems.
  • Monday, November 12 problems.
  • Monday, November 26 problems.
• We have one final meeting, a "Putnam post mortem seminar", on Monday January 21, at 4 pm in 383-N (the usual room). All twelve problems will be presented in rapidfire succession. Here are the problems and presenters.
• The official Putnam website.
• Recommended reading:
  • I really like Loren Larson's Problem Solving Through Problems --- definitely worth owning. It's great preparation for the Putnam.
  • Ditto for Paul Zeitz' The Art and Craft of Problem Solving. It is ostensibly aimed at high school students, but there is no sell-by date on this stuff.
  • It is also great help (more than you would think) trying many old problems. I'd especially recommend the collection of recent Putnams The William Lowell Putnam Mathematical Competition 1985-2000: Problems, Solutions, and Commentary, by Kiran Kedlaya, Bjorn Poonen, and myself.
  • There are more good problems in the previous Putnam book, The William Lowell Putnam Mathematical Competition Problems and Solutions: 1965-1984, by Alexanderson, Klosinski, and Larson (look especially at those in the 1980's).
  Larson and Putnam'85-'00 are in the math library (2-day reserve, under the course ``VAKIL-SEM''), in Building 380 (fourth floor). Also, on the web you can find
  • a compilation of old Putnam problems and solutions on the web, collected by Kiran Kedlaya --- the 2007 solutions are here too;
  • to find solutions to older Putnams, you can read the official solutions in the American Mathematical Monthly, which you can see electronically (from any Stanford computer) here. At that page, 'Search this journal' for ``William Lowell Putnam'' in the title.
  • Some more links are available through this good UCSD site, by Patrick Fitzsimmons.
• Last year's Stanford Putnam website.
• Michael Helms has put together this "Hint sheet".

George Polya was perhaps the most famous person to think about understanding mathematical problem-solving. He was a professor at Stanford. You can read about him here. (At some point I'll look up how to give him the correct Hungarian accent in html!)

Want more? Additional suggestions for others? Please let me know!