Mathematical Games (15-859D, 21-801), Spring 2011 (original) (raw)

Mathematical Games

Professors Danny Sleator and Alan Frieze

This course will present a number of combinatorial games and puzzles, focusing on those for which there exist mathematical techniques for solving them. (Links to previous instantiations of the course below suggest the kinds of topics we'll be covering.)

Time and Place: Tuesday Thursday 1:30-2:50 in WEH 5312

Grading will be fairly informal, and based on homework assignments and class participtation, and class presentation.

Homework

• Homework 1, Due February 3
• Homework 2, Due February 22

Textbook

One of the books we'll be using is Lessons in Play by Albert, Nowakowski, and Wolff.

Lectures

• Jan 11, Jan 13, Jan 18, Jan 20
  Frieze notes Combinatorial Games
  more Frieze notes Combinatorial Games
  Part 1 of Ferguson
  Frieze notes Subtraction Games
• Jan 25, Jan 27, Feb 1
  Combinatorial Game Theory from Lessons In Play (Chapters 0 through 6)
  Sleator's notes on games that are numbers
  Mathworld Article
  Wikipedia on Surreal Numbers
• Feb 3
  Frieze notes Maker-Breaker Games
  Maker/Breaker Games, a paper by Chvatal and Erdos
• Feb 8, Feb 10Frieze notes on Cops and Robbers
  A Game of Cops and Robbers (paper by Aigner and Fromme)
  Variations on Cops and Robbers (paper by Frieze, Krivelevich and Loh)
  Noga Alon Weighs in on Cops and Robbers
• Feb 15, Feb 17
  Chapters 5 and 6 from Lessons in Play
• Feb 22: Lisa: Angel And Devil
• Feb 24: Mine Sweeper
• Mar 1, Mar 3: John: Dundee and the Problem of Coincidences
  John Dickerson's Lecture Slides
  Lajos Takacs, The Problem of Coincidences
  Mcfadyen's Review of Book on Games of Chance by Gerolamo Cardano
  A History of Probability and Statistics and their Applications before 1750
  How to Play Dundee
• Mar 15: Emily: Welter's Game
• Mar 17: Sam: Green Hackenbush
  A Short Guide to Hackenbush
  Green Hackenbush from Winning Ways
  Notes by A. N. Walker
• Mar 22: Brian K: Game Chromatic Number The Map Coloring Game
• Mar 24: Amin: Richman Games
• Mar 29: David Bergman: King and Devil (Chapter 19 of Winning Ways)
• Mar 31: Brian M: Peg Solitaire (Chapter 23 of Winning Ways)
• Apr 5: Marla: Sylver Coinage (Chapter 18 of Winning Ways)
• Apr 7: Klaus Suttner Lights out and Related Puzzles:
  Linear Cellular Automata and the Garden-of-Eden
  Sigma-Automata and Chebyshev-polynomials
  Decomposition of Additive Cellular Automata
  Lecture Notes
• Apr 12: Frieze Patterns
  Conway, Coxeter, Mathematical Gazette Jun., 1973
  Lighter Side of Mathematics, 1994

Suggested Presentation Topics

• Coin Weighing Problems:notes, coins2,coincompet.pdf,maacoins.pdf
• Game Chromatic Numbers
• Dundee
• On Numbers and Endgames, Noam Elkies
• Impartial Misere Games

Resources

• Combinatorial Game Programs by D. Sleator: Game.java,Simplify.java, Domineering.java, Topple.java
• Game Theory is a book by Tom Ferguson
• Mathematical Games Course, 2005
• Mathematical Games Course, 2001
• David Epstein's Combinatorial Game Theory page
• Thane Plambeck's pages studies Misere games
• The Combinatorial Games Suite is a free interactive system for analyzing combinatorial games, written in Java.

Danny Sleator

Last modified: Mon Apr 11 16:22:58 2011