Let Sk denote the set of PINs that are k digits long, where the PIN may not start with three repeated digits or end with three repeated digits. In terms of k, what is |Sk |? (Example 9.11 computed |S4|.)
Checkers is a game, like chess, played on an 8-by-8 grid. Chinook, a recently built checkers-playing program that never loses a game,3 computes all possible board positions with up to k tokens, for small k. Over the next few exercises, you’ll 3 Jonathan Schaeffer, Neil Burch, Yngvi Bjornsson, Akihiro Kishimoto, Martin Muller, Rob Lake, Paul Lu, and Steve Sutphen. Checkers is solved. Science, 317(5844):1518– 1522, 14 September 2007. compute the scope of that task for very small k—namely, k ∈ {1, 2}. Figuring out how many board positions have two tokens—note that two tokens can’t occupy the same square!—will take a little more work. Briefly, the rules of checkers are as follows. Two players, Red and Black, move tokens diagonally on an 8-by-8 grid; tokens can only occupy shaded squares. There are two types of tokens: pieces and kings. Any piece that has reached the opposite side of the board from its starting side (row 8 or row 1) becomes a king. (So Black cannot have a piece in row 8, because that piece would have become a king.) Note that Black occupying square C3 is different from Red occupying C3. (See Figure 9.16.)
1 How many board positions have exactly one token (of either color)?
2 How many board positions have two kings, one of each color?
3 How many board positions have two Red kings? (Notice that two Red kings cannot be distinguished, so it doesn’t matter “which” one comes first.)
4 How many board positions have two Black pieces?
5 How many board positions have two pieces, one of each color?
6 How many board positions have one Red king and one Red piece?
7 How many board positions have one Black king and one Red piece?
8 Use the last six exercises to determine how many total board positions have two tokens.
