Pi Mu Epsilon Undergraduate Math Society at USC
Fall 2005 Semester
September 19.
The Putnam exam this year is Saturday, Dec. 3 9 am-12noon (A session), then lunch,
then 1-4pm (B session), more or less,
Prof. Lototsky prepared a handout, 7 2-sided sheets, giving 14 years worth of
Putnam problems, 1991-2004.
For next week, we hope to get some written solutions for (strict, Putnam-style) grading.
The problems will be A1,A2,B1, and B2, from 1991 and 1992.
People took individual problems as "assigned" --- after trying to solve it, look up solutions
on the web, and be prepared to present a solution to the meeting. The matching was
1991 A1 Sunny, A2 Mark, B1 Kelly, B2 Daniel
1992 A1 Alex, A2 Timothy, B1 Colin, B2 Alex.
September 26.
One new person attended:
Angela Stirm (junior) stirm@usc.edu
Alex, Mark, Timothy, Colin, and Sunny each presented
one solution.
Some solutions were perfect, some others needed more. But, overall,
this seems like a good procedure, and I hope we repeat it.
Unfortunately,
we only thought of next week --- Oct 3, as time was running out. So rather
than the ideal of making individual assignments, we simply ask that
everyone try (some) of 1993 A1-2, B1-2. As always, feel invited both to find
your own solution, and to find solutions on the web. Presenting even the latter
is valuable training.
October 3.
There were four students and two profs. What a ratio!
Alex, Colin, Tim, and Sunny each presented one of 1993 A1-2,B1-2.
We have individual assignments for next week: the 1994 exam,
Alex A1, Colin A2, Tim B1, Sunny B2.
On 1993 B2, we needed a better proof that B always wins.
Here is a proof by Professor Arratia:
" We show by induction on k, for k=1 to n, that with good play by
B, A cannot win with his k-th turn. The base case: A cannot win on his first card, since no single card is 0 mod 2n+1.
Now suppose 1 <= k < n, and assume as induction hypothesis that either B has already won, or else
A has just played his k-th card, without having won with this card. If the game is already over, then trivially, A will not win on his k+1st turn.
If the game isn't yet over, call the current sum
S, and with j = n-k say that the card A still holds are i_1, i_2, ..., i_j. The only way that A can win on his k+1 st turn
is if the sum S' left after B's k-th turn is congruent to one of
-i_1,... -i_j mod 2n+1; call these the BAD values.
But just after A has played k cards,
B has played only k-1, and hence holds j+1 cards; call them b_1,
b_2, ... b_{j+1}. By choosing one of these cards for
his k-th turn, B causes the sum S' to be one of S+b_1, ... S+ b_{j+1}. There are j BAD values for S', and B controls j+1
choices for S',
hence at least one of his choices is not BAD. He knows the cards held by A, so he can make a non-BAD choice.
This proves the statement for k+1, and completes our proof by induction.
Finally, note that if A hasn't won on turns 1,2, ..., n, then B must win, since if he hasn't won before his n-th turn, then
he wins on his nth turn, at which point the sum is 1+2+...+2n = n(2n+1), a multiple of 2n+1."
Note that we don't need to consider whether or not B wins on his k+1 st turn. Also, this works in any additive group, not just
Z mod 2n+1, assuming that A holds any n nonzero cars, and B holds any n distinct cards, B knows what n cards A holds,
and the sum of all 2n cards is zero in that group.
That A holds only nonzero card is needed for the base of the induction.
That B holds distinct cards, and knows the initial content of A's hand, is needed for the induction step. That the sum of all 2n cards is zero
is needed for the sentence
beginning with "Finally ... " And hence that last sentence is really needed for a complete proof! By generalizing the problem to any group,
we get a clearer view of what is needed for a proof.
October 10.
In attendance were Profs. Arratia and Lototsky, grad student/puzzle guru Igor Cialenco, and undergrads
Angela, Collin, and Sunny. We looked at problems 1995 A1, 1994 A2, and 1994 B2. We also
talked about pigeon-hole pronciple and tried 1994 A3.
October 17.
In attendance were Prof. Arratia, grad student Igor Cialenco, and
undergrads Alex and Timothy. We looked at problems 1995 B2, A1, 1994 A1, and 1991 B2.
Suggested focus for October 24: (1995 A2, B1) and (1996 the usual 4, i.e. A1, A2, B1, B2).
October 24.
On Oct 24, we met with 6 students, 2 professors, 1 grad student. We looked at
1995 B3, ( 1995 B4 with only partial result), (1996 B1 and B2).
We signed up individual volunteers for next week:
Angela 96 A2 and or 97 B1
Mark 97 A3
Alex 96 B3
Jeff Pennington 97 A4
Michael Johnson 97 A5
Back to the main page