Math 17 Spring 2016
An Introduction to Mathematics Beyond Calculus:
Instructor: Prof. Peter Winkler (peter.winkler at dartmouth.edu)
Abstract  Classes  Staff  Textbooks  Grading  News and current assignment  Past assignments  Exams  Honor Code
News 
FINAL EXAM will be at 6:30pm Friday, June 3, in our regular room (Kemeny 108)! OFFICE HOURS week of 5/306/3: Monday 1:303, Tuesday 1021:30, Friday 1011:30. 

Abstract 
The theory of combinatorial games is a unique development in mathematics, with its own language and its own "surreal" numbers. It is quite different from "standard" game theory, in which humans in an economy are modeled as gameplayers. Its roots go back to the 1930's, but it didn't really begin to bloom until Elwyn Berlekamp, John H. Conway and Richard Guy published their multivolume classic Winning Ways. By then Conway had already devised his surreal numbers, and the new book set forth a plan to understand actual games that people playin particular, 2person, alternating move, full information games. The theory is not something on which a lot of other mathematics has been built, so it is rarely taught and never a required course. You should not take it instead of linear algebra, for example, whose applications are ubiquitous in mathematics. But as an extra course, combinatorial games will get you comfortable with inductioneven transfinite induction!and with proofs in general, while illustrating how a great theory is built from the ground up. And if you like playing games, you're bound to have a lot of fun. Prerequisites: Math 8, placement into Math 11, or permission of the instructor. Dist: QDS.
Here is a (tentative) rough weekly syllabus.


Classes 
Room: Kemeny Hall 108 

Staff 


Textbook 
Albert, Nowakowski and Wolfe, Lessons in Play, AK Peters/CRC Press, 2012. 

Grading 
Your grade will be based on homework, class participation, two inclass exams and a final exam. 

Exams 
There will be two inclass hour exams,
the first on Monday April 18, the second on Monday May 9. 

Homework 
Homework will be assigned at each class period, due at the beginning of the next class.


Assignments 
Due Wednesday March 30: Read Chapters 0 and 1 of the text. Due Friday April 1: Do Problems 1 and 2 on p. 30, at the end of Chapter 1. Due Monday April 4: Do Problem 4 on p. 30, at the end of Chapter 1, and figure out who wins 4x4 HEX when Louise starts at the righthand end of row 2. Due Wednesday April 6: Do Problem 5 on p. 30, and prove that 0 is less than or equal to 0 (!). Due Thursday April 7: Do Problem 14 on pp. 3132 (SQUEX).Due Monday April 11: Show that (a) 1 is less than or equal to 0; (b) 0 is not less than or equal to 1; (c) 1 is less than or equal to 1; and (d) 1 is not greater than or equal to 1. Due Wednesday April 13: Give, for as many numbers born on Day 2 as you can, an equivalent BlueRed Hackenbush position.Due Friday April 15: Prove that if x = {X_LX_R} is a (surreal) number, then any x' in X_L is less than or equal to x. Due Wednesday April 20: Prove, by induction on the number of lines, that there is no position in BlueRed Hackenbush in which the first playerbe it Blue or Redhas a winning strategy.Due Friday April 22: Use our new definition of addition of surreal numbers to verify that 1 + 1/2 = 3/2. Due Monday April 25: Show that positions in DOMINEERING are not totally ordered, by presenting two positions (say, A and B) and two positions C and D, such that a playersay, Louise playing firstwould rather be faced with A+C than B+C, but would prefer playing B+D to A+D. Due Wednesday April 27: Read 4.1 and 4.2, and do Problem 1 on p. 83. Note that three of the pictured positions contain a green line. (To draw a partial order: if x is less than y, with no other element between them, put x below y and connect by a line.) NOTE: the last position should have been given the label "j", not "i".Due Thursday April 28: Prove that changing a leaf from green to blue makes a strictly better game for Louise in HACKENBUSH. Due Monday May 2: Fill out the addition table for nimbers up to *5 + *5. Due Wednesday May 4: Prove that from NIM positions with NIMsum 0 a player can reach only positions with non0 NIM sum.Due Friday May 6: Read Chapter 7. State and prove (by induction) the gamevalues conjectured in class (0,0,*,*,*2,0,0,*,*,*2 etc.) for n chips, in the Subtraction Game with S={2,3}. Due Wednesday May 11: (ripped off from exam): Solve the version of NIM in which you win by reducing to a single chip.Due Friday May 13: Show that a surreal number born on a finite day appears in only one form the first day it is born. (If this works, we get a normal form for surreal numbers that represent finite games. If not, how would you fix it?) Due Monday May 16: Read Section 4.3 (Normal Form, AKA Canonical Form). Analyze the following game: 25 points (cities, say) on a map are fixed, no two pairs at the same distance. Alice puts a pin in some city, then Bob puts a pin in some other city. After that the players alternate pulling out a pin and replacing it in a city that's closer to the other pin. As usual, if you can't move, you lose! Due Wednesday May 18: Prove that down (that is, the game {*0}) is incomparable to *, but down + down is less than *.Due Friday (not Thursday!) May 20: Read Section 5.2 and either prove Theorem 5.40 (p. 101) or Theorem 5.43 (p. 104). Due Monday May 16: Read Section 1.7 and do Problem 15, p. 23. Due Wednesday May 20: Try to construct a tree on 8 vertices, with a coin on each vertex, such that Bob gets more than half the money in the following game: beginning with Alice, each player chooses a leaf of the current tree, pockets the coin found there, and then lops off that vertex from the tree.Due Friday May 22: Explain the paradox of ROTISSERIE, in which Louise and Richard each play vertical dominoes into a grid that rotates 90 degrees after each turn. Plainly, ROTISSERIE is the same game as DOMINEERING, yet ROTISSERIE is impartial and DOMINEERING is notwe know the latter because DOMINEERING takes values like "up" that, according to the theorem of Sprague and Grundy, do not occur in impartial games.  
Honor Code 
Students are encouraged to work together to do homework problems. What is important is a student's eventual understanding of homework problems, and not how that is achieved. The honor principle applies to homework in the following way. What a student turns in as a written homework solution is to be his or her own understanding of how to do the problem. Students must state what sources they have consulted, with whom they have collaborated, and from whom they have received help. Students are discouraged from using solutions to problems that may be posted on the web, and as just stated, must reference them if they use them. The solutions you submit must be written by you alone. Any copying (electronic or otherwise) of another person's solutions, in whole or in part, is a violation of the Honor Code. If you have any questions as to whether some action would be acceptable under the Academic Honor Code, please speak to me, and I will be glad to help clarify things. It is always easier to ask beforehand than to have trouble later! 

Disabilities 
I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations with me, which might help you with this class, either after class or during office hours. Dartmouth College has an active program to help students with disabilities, and I am happy to do whatever I can to help out, as appropriate. The Student Disabilities Center is located at 318 Wilson Hall, ext. 69900, http://www.dartmouth.edu/~accessibility, if you have any questions. Any student with a documented disability requiring academic adjustments or accommodations is requested to speak with me by the end of the second week of the term. All discussions will remain confidential, although the Academic Skills Center may be consulted to verify the documentation of the disability and advise on an appropriate response to the need. It is important, however, that you talk to me soon, so that I can make whatever arrangements might be needed in a timely fashion. 