Course webpage for Freshman Seminar 23j: Chess and Mathematics (Fall 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.
September 18: Zermelo & friends:

September 25: Introduction to chessboard combinatorics

October 9 (Columbus Day): Introduction to enumerative chess problems and some of the mathematics and computational techniques they lead to

October 16: Introduction to various genres of chess problems and notions of soundness, and how to adapt the ``Zermelo'' approach to obtain them. Also: follow-up on enumeration problems (how many walks of length N on a path of length k?); the Grasshopper; Bettmann's selfmate Babsontask; some other problem variants (series-movers, reflex, maximummer).

October 23: Computational complexity and other asymptotic issues
(also: problem twins etc.)

October 30: Combinatorial game theory; transfer matrices and some enumerative applications

November 6: Root-of-unity tricks for counting paths on cycles, and the connection with earlier transfer-matrix stuff;
the knight hypercube;
Richard Stanley's guest lecture on series-helpmate queue problems

November 13: Some preliminary progress reports on final projects;
The use of definite integrals to count linear extensions of finite posets (used in Stanley's talk);
Kasteleyn's permanent-determinant method for enumerating domino tilings of a rectangle
(interlude: the sign of a permutation, and Loyd's 15 puzzle)

November 20: More progress reports;
An illustration of Erdös-style probabilistic argument: exponential lower bound on the Ramsey number R(n,n);
Problem exotica: three- and fourfold combinative separation, Schrödinger's Cat mates in 2 (a.k.a. partial retrograd analysis), Buchanan's ``Dead Reckoning'' and recent proof game, mutant castling, Circe;
Trying to make a long one-sided proof game;
Pfun with Pfaffians (introduced by enumerating matchings in graphs that are planar but not necessarily bipartite) and exterior algebra

November 27: More progress reports;
A classic cross-check problem and a recent Tamerlane's Cage problem (directmates in 2 and 4 respectively);
Transfer matrices, cont'd: rational generating functions (interlude: the power-series form of the binomial theorem, e.g. Binomial(-1,n) = (-1)n)

Dec.4: More progress reports;
A few conditional chess problems: Rook may not move except to mate, K + Q + capped pawn vs. K, mate with K+Q without moving K;
Interlude: the opposition, and Putnam problem B4;
Linear programming

Dec.11: More progress reports;
Interludes on 163 and friends, on Fritz and the finer points of the triple-repetition rule, on progressive chess, on addition chains, and on the physical limits of computing.

Dec.18: More progress reports;
Also: two classic retroanalytic miniatures, and the return time of finite Markov chains.

Jan.8: Final reports