Course webpage for Freshman Seminar 23j: Chess and Mathematics (Spring [2005-]2006)

If you find a mistake, omission, etc., please let me know by e-mail.

Here's the supplementary question for prospective students in the Seminar.
Here's a list of some sources and resources relevant to the seminar, including all the books and articles on reserve for the seminar at the Cabot (a.k.a. Science Center) library.
Here's an outline/review of algebraic notation for chess positions and moves.
Here are glossaries of most of the technical terms from chess and graph theory that we'll use.
February 6: Zermelo & friends:
• Zermelo's theorem, and generalizations to many other games (what exactly is Zermelo using about Chess)?
• what can ``slight advantage'' or ``strong move'' etc. mean in light of Zermelo's theorem?
• Exhaustive ``retrograde'' analysis (an example of ``dynamical programming'') to determine perfect play; variations: computer databases (with 4, 5, 6, or most recently 7 units on the board), corresponding squares (Ebersz), helpmates (Mertes et al.) and other unorthodox genres, other games (Connect Four, checkers, ...)
• Preview of things to come: Szasz's stealth-retrograde problem (#2940 from the Polgar 5334) and an introduction to chess problem conventions

February 13: Introduction to enumerative chess problems and some of the mathematics they lead to

• Examples of positions with Fibo[N] solutions in N moves (each N=1,2,3,...; challenge: find one with 2N-1 solutions)
• The Catalan problem from Stanley's Enumerative Combinatorics
• Dynamical programming again, and first connections with linear algebra

February 20 (Presidents' Day): Introduction to chessboard combinatorics

• The bipartite Knight
• The Eight Queens Problem, and other maximal (co)clique questions
• Two kinds of domination numbers
• Some asymptotic questions
• Preview of things to come: the Grasshopper and other unorthodox pieces

February 27: Nim and Combinatorial Game Theory (CGT) in chess

• (From last Monday: Domination of unoccupied squares on 11x11 board by five Queens, and with a mutant Bishop pair --- of all squares of 8x8 by the eight officers)
• Nim and Nimbers: the Sprague-Grundy theory of finite impartial games; the group of nonnegative integers under Nim addition
• Introduction to the Berlekamp-Conway-Guy generalization of Sprague-Grundy to ``partizan'' games
• Some examples in chess

March 6:

March 13:

March 20:

• Justin's construction showing 2N-1 mates in N in a legal position
• Yet another par(i)ty trick: the 31-domino problem
• Enumeration of domino tilings of rectangles (more generally, perfect matchings of planar bipartite graphs): Kasteleyn's permanent-determinant transformation; outline of the product formula for domino tilings of an MxN rectangle. [Challenge: explain how 1 and Fibonacci arise for M=1,2; prove that there's a per-det transformation in general; if you know about Pfaffians, find the generalization to matchings of planar graphs that need not be bipartite]

[March 27: Spring Break]

April 3: