HMMT 二月 2011 · TEAM1 赛 · 第 2 题

HMMT February 2011 — TEAM1 Round — Problem 2

[ 15 ] 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 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?

解析

[ 15 ] 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 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? 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 to see that if we view running and fighting as operations, they commute. So the order of the moves does not matter, all that matters is how many times Rachel runs and how many times Rachel fights. 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.