CombinatoricsDifficulty 5.8AIME, harderProve itUnited States
Problem:
The ordered pairs (2011,2),(2010,3),(2009,4),…,(1008,1005),(1007,1006) are written from left to right on a blackboard. Every minute, Elizabeth selects a pair of adjacent pairs (xi,yi) and (xj,yj), with (xi,yi) left of (xj,yj), erases them, and writes (yjxiyixj,xjxiyiyj) in their place. Elizabeth continues this process until only one ordered pair remains. How many possible ordered pairs (x,y) could appear on the blackboard after the process has come to a conclusion?
Solution
Solution:
Answer: 504510
First, note that none of the numbers will ever be 0. Let ⋆ denote the replacement operation. For each pair on the board (xi,yi) define its primary form to be (xi,yi) and its secondary form to be [xiyi,yixi]. Note that the primary form determines the secondary form uniquely and vice versa. In secondary form,
Thus we may replace all pairs on the board by their secondary form and use the above rule for ⋆ instead. From the above rule, we see that if the leftmost number on the board is x, then after one minute it will be x or x2 depending on whether it was erased in the intervening step, and similarly for the rightmost number. Let k be the number of times the leftmost pair is erased and n be the number of times the rightmost pair is erased. Then the final pair is
[40222k,(10061007)2n]
Any step except the last cannot involve both the leftmost and rightmost pair, so k+n≤1005. Since every pair must be erased at least once, k,n≥1. Every pair of integers satisfying the above can occur, for example, by making 1005−k−n moves involving only the pairs in the middle, then making k−1 moves involving the leftmost pair, and finally n moves involving the rightmost pair.