CombinatoricsDifficulty 5.3AIME, harderFind the answerUnited States
Problem:
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?
A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.
Solution
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.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.