the Preliminary Questions for Freshman Seminar 23j:
Chess and Mathematics (Fall 2003)

CHESS: This is the celebrated ``Saavedra position''. See Krabbé's article on the history of the position. White to play can force a win with the remarkable sequence
1 c7 Rd6+ 2 Kb5 Rd5+ 3 Kb4 Rd4+ 4 Kb3 Rd3+ 5 Kc2 Rd4! 6 c8R!! Ra4 7 Kb3!.
White's first two moves are unique (for instance, 3 Kc5? Rd1(d2)! draws), as is the third if we ignore the time-wasting repetition 3 Kb6 Rd6+. Instead of 4 Kb3 Rd3+ 5 Kc2, White could also play 4 Kc3 Rd1 5 Kc2 reaching the same position. Now Black's Rd4! is based on the continuation 6 c8Q Rc4+! forcing 7 Qxc4 stalemate. This seems to draw (6 Kc3(b3) Rd1(d3+) repeats earlier positions), but White's Rook promotion -- which is Saavedra's only but decisive contribution to the analysis -- ruins Black's plot. Normally K+R vs. K+R is a sterile draw, but here Black has restricted his own King so much in the attempt to get stalemated that White's Rook suffices to create decisive mating threats. 6...Ra4 is the only way to stop 7 Ra8# without immediately losing a Rook, but 7 Kb3 threatens both 8 Rc1# and 8 Kxa4 and Black cannot defend both threats.

An implicit assumption in this analysis is that K+Q vs. K+R is a ``generic win'', that is, that the K+Q win unless the K+R have a specific resource that forces a draw (as in the stalemate trick above) or even a win (as after 3 Kc5? Rd1(d2)! 4 c8Q?? Rc1+). Exhaustive computer analysis about 25 years ago finally showed that this assumption is correct but the win can be surprisingly difficult against best defense: with either 1...Rd3 or 1...Kb2 Black can last 20 moves until losing the Rook, even with optimal White play. Still, it is the extraordinary variation culminating with c8R that's regarded as the ``main line'' of the ending, not the lengthy but routine K+Q/K+R fight when Black lets White queen quickly.

I gave the ``Saavedra'' position without specifying whose turn it is, so a complete solution includes evaluation of the position with BTM (Black To Move). This is a routine draw, despite Black's huge "point" advantage of Rook against pawn: White's King and pawn are too close to the touchdown square c8, and Black's King too far from it, for Black to make any serious attempt to win. In such positions there are many ways Black can draw: exchange the Rook for White's pawn (for instance 1...Rd6 2 Kb7 Rxc6 3 Kxc6); wait until White queens and then trade Rook for Queen (as in 1...Rg5 2 c7 Rg8 3 Kb7 Kb2 4 c8Q Rxc8 5 Kxc8); or harass White forever with long-distance threats (as after 1...Rd2 2 c7 Rb2+ 3 Ka7 Ra2+ or 3...Rc2). This last option has the curious side-effect that chess-playing computers often have a hard time ``understanding'' that this kind of position is a draw: the computer will evaluate the position as an easy Black win until it exhausts all the drawing lines and ``sees'' that Black can do no better than go endlessly from one drawn position to another.

COMBINATORIAL MATHEMATICS: The two graphs are equivalent; they are two pictures of the ubiquitous Petersen graph. See this Mathworld page for some information about this graph. Among many other things, this is the unique "Moore graph of degree 3" -- that is, a graph each of whose vertices has 3 neighbors, with any two vertices either adjacent or having a unique common neighbor (but not both). Equivalently, it is a regular graph of degree 3, diameter 2, and girth (minimal cycle length) 5. It is known that Moore graphs of degree d exist only for d=2 (the 5-cycle), d=3 (Petersen), d=7 (another unique graph, discovered and proved unique by Hoffman and Singleton -- here's an outline of a combinatorial proof), and possibly d=57 (a famous open problem). For the proof that no other values of d are possible -- which uses properties of eigenvalues of symmetric matrices! -- see for instance B.Bollobas's Extremal Graph Theory.

Often a unique solution to a combinatorial problem has many symmetries. This is true for the Petersen graph. Our two pictures show a fivefold and a threefold symmetry. There are 120 symmetries in all, forming the ``symmetric group S5'' of permutations of a set F of 5 objects, say F={a,b,c,d,e} -- note that 120=1*2*3*4*5=5!. One succinct description of the Petersen graph that exhibits all these symmetries is: the vertices correspond to the 10 two-element subsets of F, and two vertices are adjacent if and only if the corresponding subsets are disjoint. [For instance, {a,b} is adjacent to {c,d}, {c,e}, and {d,e}. This description is equivalent to Mathworld's ``the complement of the line graph of the complete graph K5''.] We can also obtain the graph from the 2*10=20 vertices and 2*15=30 edges of a regular dodecahedron (the regular solid bounded by 12 pentagons) by identifying opposite pairs of vertices; this reveals exactly half the symmetries of the graph, corresponding to the ``even permutations'' of F.

COMPUTING: More generally let
fN(x) = 1 + x + x2 + x3 + x4 + ... + xN-2 + xN-1 = (1-xN/ (1-x),
and consider first the slightly larger but easier case of N=2048=211. Then xN can be computed quickly by repeated squaring: calculate x*x=x2, then (x2)2=x4, (x4)2=x8, (x8)2=x16, ..., (x1024)2=x2048. This takes only 11=log2(N) multiplication steps instead of 2047=N-1. Three more operations reach fN(x)=(1-xN/ (1-x). If we're not allowed to divide (or subtract), a variation of this trick still allows us to compute f2048(x) in only 31 steps (20 multiplications and 11 additions): factor f2048(x) as
(1+x) (1+x2) (1+x4) (1+x8) ... (1+x512) (1+x1024),
and calculate each of x2, x4, x8, ..., x1024 by repeated squaring as before. (This method is so fast that it is sometimes used in practice to compute an approximation to 1/(1-x) for values of x close to zero without performing a single division!) The factorization works because when the product is expanded each power of x between 1 and x2047 appears exactly once, corresponding to the unique binary expansion of the exponent.

This use of binary expansions also let us handle the general case that N is not a power of 2. Let n be the integer part of log2(N), so 2n is the largest power of 2 less than or equal N. Then N can be written as the sum of at most n+1 powers of 2, whence xN can be written as the product of at most n+1 of the numbers x,x2,x4,x8,...,x2n. So this computation takes at most 2n steps, which is still much less than N if N is at all large. For instance, when N=2004=111110101002 we would write

x2004 = x4 x16 x64 x128 x256 x512 x1024
and compute x2004 using only 16 multiplications, for a total of 19 arithmetic operations to calculate f2004(x). Even this is not optimal; can you do better? It is known that for large n the computation need never take more than n+o(n) steps [that is, for each real e>0 there exists n0(e) such that xN can be computed in less than n+en steps for all N such that log2N>n0(e)]. But finding the exact minimum is a very hard problem for most values of N, which has yet to be solved in general! See for instance Knuth's book The Art of Computer Programming, Volume 2: Seminumerical Algorithms, pages 402-422.

What of part (ii), which asked to compute fN(x) without divisions (or subtractions)? We can easily compute fN(x) in less than 2N operations using the recursion fN+1(x)=1+xfN(x). But we can adapt our factorization trick too, reducing the number of operations to a small multiple of log2N. One way to do this is to read the binary expansion of N backwards as a recipe for reaching N from 1 in at most 2n steps of either doubling or adding 1. For instance, for 2004 we have in 16 steps:

1*2=2, 2+1=3, 3*2=6, 6+1=7, 7*2=14, 14+1=15, 15*2=30, 30+1=31, 31*2=62, 62*2=124, 124+1=125, 125*2=250, 250*2=500, 500+1=501, 501*2=1002, 1002*2=2004.
We can thus compute x2, x3, x6, x7, x14, x15, ..., x501, x1002 in 16 multiplications (each either a squaring or a product with x). At the same time, calculate
f2(x)=1+x,   f3(x)=f2(x)+x2,   f6(x)=(1+x3)f3(x),   f7(x)=f6(x)+x6,   f14(x)=(1+x7)f14(x),   . . .,
f501(x)=f500(x)+x500,   f1002(x)=(1+x501)f501(x),   f2004(x)=(1+x1002)f1002(x),
at each step using the power of x just computed. The whole procedure took only 40 operations (24 multiplies and 16 adds), much less than then four thousand, to say nothing of millions.