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

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

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 S_{5}'' 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 K_{5}''.]
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

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
log_{2}(N), so 2^{n} 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 x^{N} can be written as the product
of at most n+1 of the numbers
x,x^{2},x^{4},x^{8},...,x^{2n}.
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=11111010100_{2} we would write

What of part (ii), which asked to compute f_{N}(x)
without divisions (or subtractions)? We can easily compute
f_{N}(x) in less than 2N operations using the recursion
f_{N+1}(x)=1+xf_{N}(x).
But we can adapt our factorization trick too, reducing
the number of operations to a small multiple of log_{2}N.
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: