Problem: (ACoPS 3.4.21) Initially, we are given the sequence . Every minute, we erase any two numbers and and replace them with the value . Clearly, we will be left with just one number after minutes. Does this number depend on the choices we made?
Solution: We claim that the number does not depend on the choices. Let be the numbers on the board after minutes. Define . We claim that the sequence is constant.
Noticing that , we see that replacing with has no effect on the product . Indeed,
so we have by induction. Since is clearly constant, must be as well. Seeing that 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 should remind you of Simon’s favorite factoring trick, leading to the invariant as described above.
Practice Problem: (ACoPS 3.4.23) Start with the set . You are then allowed to replace any two numbers and with the new pair and . Can you transform the set into ?
Leave a Reply
You must be logged in to post a comment.