HMMT 二月 2011 · TEAM1 赛 · 第 2 题

英文解析

2. [ 15 ] Rachel and Brian are playing a game in a grid with 1 row of 2011 squares. Initially, there is onewhite checker in each of the first two squares from the left, and one black checker in the third squarefrom the left. At each stage, Rachel can choose to either run or fight. If Rachel runs, she moves theblack checker 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 tothe left, the black checker is moved 1 unit to the right, and Brian places a new white checker in thecell immediately to the left of the black one. The game ends when the black checker reaches the lastcell. How many different final configurations are possible?
   Solution: 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 tosee that if we view running and fighting as operations, they commute. So the order of the moves doesnot matter, all that matters is how many times Rachel runs and how many times Rachel fights. Eachfight adds one white checker to the grid, so two games with different numbers of fights will end up indifferent final configurations. There are 2009 possible values for the number of fights, so there are 2009
   possible final configurations.