HMMT 二月 2011 · TEAM2 赛 · 第 14 题

英文解析

14. [ 25 ] 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 moves 1 unit to the right, and Brian moves each of the white checkers one unit to theright. 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 checkerin the cell immediately to the left of the black one. The game ends when the black checker reaches thelast cell. How many different final configurations are possible?
    Answer: 2009 Both operations, run and fight, move the black checker exactly one square to theright, so the game will end after exactly 2008 moves regardless of Brian’s choices. Furthermore, it iseasy to see that the order of the operations does not matter, so two games with the same number offights will end up in the same final configuration. Finally, note that each fight adds one white checkerto 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.