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\} $?