## Saturday, April 15, 2006

### That's A Lot Of Numbers. Topic: Logic/NT. Level: Olympiad.

Problem: (ACoPS 3.4.21) Initially, we are given the sequence $1,2, \ldots, 100$. Every minute, we erase any two numbers $u$ and $v$ and replace them with the value $uv+u+v$. Clearly, we will be left with just one number after $99$ minutes. Does this number depend on the choices we made?

Solution: We claim that the number does not depend on the choices. Let $a_1, a_2, \ldots, a_n$ be the numbers on the board after $100-n$ minutes. Define $\displaystyle P_n = \prod_{i=1}^n (a_i+1)$. We claim that the sequence $P_{100}, P_{99}, \ldots, P_1$ is constant.

Noticing that $(u+1)(v+1) = uv+u+v+1$, we see that replacing $u, v$ with $uv+u+v+1$ has no effect on the product $P_n$. Indeed,

$P_{k-1} = \frac{P_k(uv+u+v+1)}{(u+1)(v+1)} = P_k$

so we have $P_{100} = P_{99} = \cdots = P_1$ by induction. Since $P_{100}$ is clearly constant, $P_1$ must be as well. Seeing that $P_1$ is equivalent to the remaining number, we conclude that it does not depend on the choices, as desired. QED.

--------------------

Comment: Problems with invariants require you to discover something (often a sum or product) that doesn't change with each step. The term $uv+u+v$ should remind you of Simon's favorite factoring trick, leading to the invariant $P_n$ as described above.

--------------------

Practice Problem: (ACoPS 3.4.23) Start with the set $\{3,4,12\}$. You are then allowed to replace any two numbers $a$ and $b$ with the new pair $0.6a-0.8b$ and $0.8a+0.6b$. Can you transform the set into $\{4,6,12\}$?