14. [25] Rachel and Brian are playing a game in a grid with 1 row of 2011 squares. Initially, there is one white checker in each of the first two squares from the left, and one black checker in the third square from the left. At each stage, Rachel can choose to either run or fight. If Rachel runs, she moves the black checker moves 1 unit to the right, and Brian moves each of the white checkers one unit to the right. If Rachel chooses to fight, she pushes the checker immediately to the left of the black checker 1 unit to the left; the black checker is moved 1 unit to the right, and Brian places a new white checker in the cell immediately to the left of the black one. The game ends when the black checker reaches the last cell. How many different final configurations are possible?
Answer: 2009 Both operations, run and fight, move the black checker exactly one square to the right, so the game will end after exactly 2008 moves regardless of Brian's choices. Furthermore, it is easy to see that the order of the operations does not matter, so two games with the same number of fights will end up in the same final configuration. Finally, note that each fight adds one white checker to the grid, so two games with different numbers of fights will end up in different final configurations. There are 2009 possible values for the number of fights, so there are 2009 possible final configurations.