Maths Olympiad Prep

Library / /354 of 377

Combinatorics Difficulty 5.8 AIME, harder Prove it United States

Problem:

The ordered pairs (2011,2),(2010,3),(2009,4),,(1008,1005),(1007,1006)(2011,2),(2010,3),(2009,4), \ldots,(1008,1005),(1007,1006) are written from left to right on a blackboard. Every minute, Elizabeth selects a pair of adjacent pairs (xi,yi)\left(x_{i}, y_{i}\right) and (xj,yj)\left(x_{j}, y_{j}\right), with (xi,yi)\left(x_{i}, y_{i}\right) left of (xj,yj)\left(x_{j}, y_{j}\right), erases them, and writes (xiyixjyj,xiyiyjxj)\left(\frac{x_{i} y_{i} x_{j}}{y_{j}}, \frac{x_{i} y_{i} y_{j}}{x_{j}}\right) in their place. Elizabeth continues this process until only one ordered pair remains. How many possible ordered pairs (x,y)(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 00. Let \star denote the replacement operation. For each pair on the board (xi,yi)\left(x_{i}, y_{i}\right) define its primary form to be (xi,yi)\left(x_{i}, y_{i}\right) and its secondary form to be [xiyi,xiyi]\left[x_{i} y_{i}, \frac{x_{i}}{y_{i}}\right]. Note that the primary form determines the secondary form uniquely and vice versa. In secondary form,

[a1,b1][a2,b2]=(a1b1,a1b1)(a2b2,a2b2)=(a1b2,a1b2)=[a12,b22]. \left[a_{1}, b_{1}\right] \star\left[a_{2}, b_{2}\right]=\left(\sqrt{a_{1} b_{1}}, \sqrt{\frac{a_{1}}{b_{1}}}\right) \star\left(\sqrt{a_{2} b_{2}}, \sqrt{\frac{a_{2}}{b_{2}}}\right)=\left(a_{1} b_{2}, \frac{a_{1}}{b_{2}}\right)=\left[a_{1}^{2}, b_{2}^{2}\right].

Thus we may replace all pairs on the board by their secondary form and use the above rule for \star instead. From the above rule, we see that if the leftmost number on the board is xx, then after one minute it will be xx or x2x^{2} depending on whether it was erased in the intervening step, and similarly for the rightmost number. Let kk be the number of times the leftmost pair is erased and nn be the number of times the rightmost pair is erased. Then the final pair is

[40222k,(10071006)2n] \left[4022^{2^{k}},\left(\frac{1007}{1006}\right)^{2^{n}}\right]

Any step except the last cannot involve both the leftmost and rightmost pair, so k+n1005k+n \leq 1005. Since every pair must be erased at least once, k,n1k, n \geq 1. Every pair of integers satisfying the above can occur, for example, by making 1005kn1005-k-n moves involving only the pairs in the middle, then making k1k-1 moves involving the leftmost pair, and finally nn moves involving the rightmost pair.

k=11004n=11005k1=k=110041005k=k=11004k=100410052=504510 \sum_{k=1}^{1004} \sum_{n=1}^{1005-k} 1=\sum_{k=1}^{1004} 1005-k=\sum_{k=1}^{1004} k=\frac{1004 \cdot 1005}{2}=504510

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.