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

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:

(Stefan Wernli) How many move orders to set up the White Stonewall formation c3,d4,e3,f4,Nbd2,Ngf3,Bd3,0-0? [Likewise other opening setups, such as the Sicilian Dragon c5,d6,Nc6,Nf6,g6,Bg7,0-0 for Black -- there the enumeration is easier.]
(Mark Wagner) For each n, how many moves does it take to translate all 16 White units up n squares? [Once n>5 we must imagine a taller board.]
(Zain Khalid) Likewise, how many moves to copy Black's initial setup (with White pawns on the 7th rank and officers on the 8th)?
(Jie Tang) Given n, what's the position that's n moves from White's initial setup and has the largest number of n-move sequences? What's the largest n for which there exists a position that requires n moves in a unique sequence?
(Brian Young) Is there a position with a unique sequence that involves moving all 8 officers?

[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:

What is ``perfect play''; what can ``slight advantage'' or ``strong move'' mean?
The Saavedra example (start here for explanations)
Exhaustive computer analyses (for chess positions with few men, or Connect Four, or...)
K+N+N don't beat K, but may beat K+P (Troitzky)!
Introduction to corresponding squares.

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!² 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 K₅, complete bipartite graph K_3,3, and the Petersen graph.

[Oct.11 was Columbus Day]

October 18: Dynamical programming for enumerative problems:

Mate in N, number of solutions is Nth Fibonacci number (and generalizations)
Counting domino tilings of rectangles with one side-length fixed (for 2*N, again get Fibonacci)
Counting Wazir and Knight tours of boards with one side-length fixed, or of the 8*8 board
Corresponding squares, illustrated by the famous Kings-and-pawns endgame study of Ebersz (1930), and other ``Zermelo'' analyses

October 25:
Puzzle followups: An enumerative problem with 2005 solutions; attempts to create a problem with 6^n-1 solutions in n moves (we already have 2^n-1 [B.Young] and can easily generalize to 3^n-1, 4^n-1, and 5^n-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. 5²+8²=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. 1²+4²+6²+4²+1²=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.