The William Lowell Putnam Mathematical Competition
and the Polya ProblemSolving 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 selfselected
from among the best in the continent.)
 The introductory meeting will take place Monday Oct. 1,
time 5:155:45,
in 380383N (in the corner of the third floor of the math department).
Here is the introductory poster.
Here is the introductory handout.
 Meetings: the Polya ProblemSolving Seminars are informal dinnertime problem solving practice
sessions this fall quarter, on Mondays 5:156:45.
(Rough schedule: 55:15 beforehand,
people can drop by to discuss ``leftovers'' from the previous week.
5:155:30: short discussion of new technique. 5:306:15: work on problems.
6:156: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 problemsolving 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 RubinsteinSalzedo, 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 ``Lightsout'' 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^{100}?

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 78 unless 6:457:45 is much better).
 We have one final meeting, a "Putnam post mortem seminar",
on Monday January 21, at 4 pm in 383N (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 sellby
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 19852000: 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: 19651984, by Alexanderson, Klosinski, and Larson (look especially at those
in the 1980's).
Larson and Putnam'85'00 are in the math library (2day reserve, under
the course ``VAKILSEM''), 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 problemsolving. 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!
To Ravi Vakil's homepage