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.

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<sub>5</sub>'' 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₅''.] 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.

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₂(N), so 2ⁿ 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²,x⁴,x⁸,...,x²ⁿ. 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₂ 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₂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: