Course webpage for Freshman Seminar 23j: Chess and Mathematics (Fall 2004)

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.
Setember 20: Informational meeting. Several approaches to the supplementary question for the Seminar. No 2005 puzzle yet, though Brian Young makes the promising observation that 2002=Binomial(14,5). Meanwhile, some other questions: [All but J.Tang's questions can be solved with what we know already.] Also, a few words about Losing Chess, including the mutual Zugzwang Be1/Ne6.

September 27:
Puzzle followups (Abraham et al.: 59 or 60 moves for Z.Khalid's question, depending on whether KQ switch places; Jie et al.: partial progress on my 2005 challenge and the 8-officer task)
The ``Zermelo'' (retrograde analysis) algorithm, and some variations and consequences:

Also: examples of underpromotion and mutant promotions.

October 4: Graph theory of the chessboard: distance functions, maximal (co)cliques, domination numbers, and distance functions for the King, Queen, Rook, Bishop, and Knight. Board symmetries: 8, if we ignore Castling (as in the KRR/K puzzle) and one-way pawns; 2·8!2 for the Rook; how many for the Bishop? Some chess applications; enumeration of maximal configurations, including some open problems (King domination and cocliques on rectangular boards of arbitrary size). Aside: Euler paths and Euler's formula V-E+F=2; application to non-planarity of complete graph K5, complete bipartite graph K3,3, and the Petersen graph.

[Oct.11 was Columbus Day]

October 18: Dynamical programming for enumerative problems:

October 25:
Puzzle followups: An enumerative problem with 2005 solutions; attempts to create a problem with 6n-1 solutions in n moves (we already have 2n-1 [B.Young] and can easily generalize to 3n-1, 4n-1, and 5n-1);
Meet-in-the-middle tricks (sometimes with sorting n objects in time n log(n)), and applications: solving Rubik's cube; the sum of two consecutive Fibonacci squares is an even-numbered Fibonacci number (e.g. 52+82=89 -- what's the corresponding result for odd-numbered Fibonaccis?); the sum of squares of entries in the n-th row of Pascal's triangle is Binomial(2n,n) (e.g. 12+42+62+42+12=70).
Combinatorial Game Theory: Nim, CGT values, pawn endgames, the ``upstart [Up-Star] identity'', the mex rule, Misère Nim.

November 1:
An introduction to various genres of chess problems and notions of soundness; how one might modify the ``Zermelo'' approach to list all sound problems (under various definitions), or those with features like setplay, twins, etc.
Also: Introduction to asymptotics; some asymptotic chess questions.

November 8:
Catalan numbers and some chess problems where they arise; more problem variants: combinative separation; Schrödinger's Cat mates in 2; Grasshopper and Maximummer.

November 15:
Parity proof games and their construction; final project discussion.

November 22:
Theory of Computation seminar on ``Exponentially long chess problems on large boards''.
Also: the golden ratio as an eigenvalue, and its appearance in the formula for Fibonacci numbers as an illustration of solving general linear recurrences. (Asides on the golden ratio in the regular pentagon(!) and on the (-n)th Fibonacci number.)

November 29:
Initial progress reports on the final projects.
Also: two classic Babson-task problems; King and multi-leaper vs. King; a one-sided proof game with a unique solution that moves all eight officers; introduction to Kasteleyn's permanent-determinant method for enumerating domino tilings of checkerboard chunks [it works more generally for any bipartite planar graph].

December 6:
Richard Stanley's guest lecture on queue problems.
Also: a few more progress reports; a Mate in 4 problem based on the Jelliss-Beasley Knight hypercube.

December 13:
More progress reports; also: the sign of a permutation, and applications to Loyd's 15-puzzle, Rubik's cube, and generalizations.