This week, we learn about Invariance and Monovariance Principle, which are useful methods to help determine if certain states can be achieved in problems involving sequences, recursions, or iterative processes.
How would you use Invariance and Monovariance to solve the following?
(2008 Putnam) Start with a finite sequence \( a_1, a_2, \ldots , a_n\) of positive integers. If possible, choose two indices \(j < k\) such that \(a_j\) does not divide \(a_k\) , and replace \(a_j\) and \(a_k\) by \( \gcd(a_j , a_k )\) and \(lcm(a_j , a_k )\), respectively. Prove that if this process is repeated, it must eventually stop.
Find many many different ways to approach this question using the ideas of invariance and monovariance.
In Worked Example 1, can you classify all possible values which Grayson could be left with on the blackboard? We have already shown that it must be even.