According to legend, when the inventor of chess presented his creation to the king of his country, the king was so impressed that he promised the inventor any reward whatsoever for the invention. The man, being very clever and not very wise, asked the king this: for the first square of the chessboard, he would receive one grain of rice; two for the second square, four for the third, and so on, doubling each time. Eventually the king realized this would take more rice than had ever been grown in the kingdom, and punished the inventor.
Suppose, however, that the kingdom had been unimaginably wealthy, and contained sufficient rice to give the inventor his reward. The king's treasurer places the grains of rice on the squares of the chessboard starting at a1 and going from left to right to h1, then a2 to h2, and so on, ending on h8. What fraction of the rice will be placed on white squares?
To remind you: in chess, a Knight moves by jumping to a square whose center is √5 units away from the center of the square the Knight is currently on. This means that a square which is two spaces away diagonally is very hard to get to: the Knight will need at least four moves. Fix such a pair of squares (for example, e4 and c6). In how many ways can a Knight get from the first square to the second in exactly four moves? (If the squares are near the center of the board, the edges of the chessboard will not be a problem.)
This problem can be solved just by drawing lots of pictures and counting. However, if you approach it in this way, you'll have a hard time convincing yourself you're right, and didn't miss anything. Think of this problem as a challenge to come up with a systematic way of counting all the possibilities.
Suppose we place 8 queens on the chessboard in such a way that no two queens attack each other. (A queen attacks all queens which share a row, column, or diagonal with it.) Verify that for all such queen placements, it is always possible to tile the remaining 56 squares of the chessboard with 1 by 2 domino tiles.
(I suspect that there is a simple mathematical proof that this is possible; moreover, that this is possible over a wide range of board dimensions. However, since I don't currently have such a proof, all I can ask for is to treat this as a programming exercise: write a program to check all possible queen arrangements for having a domino tiling. If there is a proof, I would like to know!)
A Rook starts on the bottom left corner of the chessboard (a1) and proceeds to make random legal moves: every move takes the Rook to one of the 14 squares in the same row or the same column, with equal probability. What is the mean number of moves that it will take the Rook to land on the top right corner of the chessboard (h8)?
By pooling the resources of several chess sets, you have amassed a collection of 64 pawns. On a whim, you decide to play the following solitaire game: you begin by placing a few pawns on some of the squares of the chessboard. Then, whenever an empty square is adjacent to at least two squares with pawns (horizontally or vertically, but not diagonally), you place a pawn in that square. You repeat this process until either the entire chessboard is filled with pawns, or there are no more empty squares on which a pawn should be placed.
What is the smallest number of pawns you need to place at the beginning, so that eventually the whole board is filled with pawns?
(As with all optimization problems, there are two parts to a complete answer to this problem. First, you must show how to arrange N pawns that will fill the chessboard, where N is as small as possible. Second, you must prove that no arrangement of N-1 or fewer pawns will work. Expect a slick solution to this problem.)
The crooked rook is a fictional chess piece that can only move one square up or one square to the right. Starting from the bottom left square of a standard chessboard (a1), how many ways are there to move the crooked rook to the top right square (h8), while avoiding the four squares in the center of the chessboard (d4, d5, e4, and e5)?
For full credit, write the final answer as a simple expression involving binomial coefficients. Such a solution can easily be generalized to an N by N chessboard and a K by K center.