On Onwards And Downwards

| 0 Comments

When last they met, the Baron challenged Sir R----- to evade capture whilst moving rooks across and down a chessboard. Beginning with a single rook upon the first file and last rank, the Baron should have advanced it to the second file and thence downwards in rank in response to which Sir R----- should have progressed a rook from beneath the board by as many squares and if by doing so had taken the Baron's would have won the game. If not, Sir R----- could then have chosen either rook, barring one that sits upon the first rank, to move to the next file in the same manner with the Baron responding likewise. With the game continuing in this fashion and ending if either of them were to take a rook moved by the other or if every file had been played upon, the Baron should have had a coin from Sir R----- if he took a piece and Sir R----- one of the Baron's otherwise.

The first thing to note about this game is that after each turn, should a rook not have been taken, the sum of the ranks of every piece must equal eight, for each rank that is lost by the one player is gained by the other. Since no rook rests upon the first file, the game must conclude with either the Baron or Sir R----- taking a piece.
The next thing to note is that each would have been compelled to demote their chosen rook by less than one half of its rank or else it should have been taken by the other's promotion. Since exchanging the pair of rooks sat upon a file at the end of a turn should make no difference to consequent play, we need only rule out dividing the rank by exactly one half.
This game is therefore isomorphic to Grundy's game, which is itself equivalent to Nim, in which \(n\) piles of stones are split into \(n+1\) by taking any of them having more than one stone and dividing it into two unequal piles, with two players taking turns until one of them is unable to do so and loses the game. I told the Baron as much but, judging by his somewhat bellicose response, I do not believe that he fully grasped my point.
Sketching out the tree of states of the game, with the Baron's possible moves drawn as blue branches and Sir R-----'s as red

we see that the Baron loses in two of the three end-states. However, if we carefully prune the tree

we find that the Baron may always compel Sir R----- to his losing state and I should therefore have advised him to decline the wager.
\(\Box\)

Leave a comment

 
This site requires HTML5, CSS 2.1 and JavaScript 5 and has been tested with

Chrome Chrome 26+
Firefox Firefox 20+
Internet Explorer Internet Explorer 9+