Welcome to the Math 17 Web Page

Math 17 Spring 2016

An Introduction to Mathematics Beyond Calculus:
Surreal Numbers and Combinatorial Games

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/30-6/3: Monday 1:30-3, Tuesday 10-21:30, Friday 10-11: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 game-players. 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 multi-volume 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 play---in particular, 2-person, 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 induction---even 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.

1. Games, combinatorial and otherwise; surreal numbers

2. Techniques for solving games

3. Outcome classes and sums of games

4. Game values

5. Impartial games

6. Hot games

7. All-small games

8. Induction

9. New directions

Classes

Room: Kemeny Hall 108
Lectures: "2" slot, in particular: Monday, Wednesday and Friday 1:45-2:50.
X-hour: Thursdays (same room) 1:00 pm--1:50pm. Will be used on special occasions, including the following days: April 6 (instead of April 7), and April 27 (instead of April 28).

Staff

Instructor:
Peter Winkler -- Kemeny Hall 231 / Tel. 6-3468
Office Hours: Tuesdays 1:15-2:45; Thursdays 10:15-11:45.

Textbook

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

Grading

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

Exams

There will be two in-class hour exams, the first on Monday April 18, the second on Monday May 9.
Let me know immediately if you might not be able to make it to an exam.
The final exam will be at 6:30pm Friday, June 3.

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 right-hand 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. 31-32 (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 Blue-Red Hackenbush position.

Due Friday April 15: Prove that if x = {X_L|X_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 Blue-Red Hackenbush in which the first player---be it Blue or Red---has 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 player---say, Louise playing first---would 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 NIM-sum 0 a player can reach only positions with non-0 NIM sum.

Due Friday May 6: Read Chapter 7. State and prove (by induction) the game-values 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 re-placing 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 not---we 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. 6-9900, 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.