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.

No vote yet

12 votes

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewestWell, I would perhaps use monovariance (for the first problem) in another way, noting first that \( gcd(a_j,a_k) \times lcm(a_j,a_k) = a_ja_k \). So the whole sequence is bounded above by this product. Then perhaps we can proceed by looking at the last element. Remark that it can only increase since it is replaced by its \( lcm \) and some other number we don't really care. So in a way, once it reaches its max value it becomes fixed. Similarly we can consider the second-last element, third-last element, etc. using the exact same argument, we can show that the process stops.

Log in to reply

Great, that's 1 way. Find many many more!

Log in to reply

After I played around with a small list of numbers I noticed something interesting about the

prime factorisationof the original sequence and the final sequence, that they are the same, but in the final sequence, they were sorted in an increasing order. (To see what I mean, try it out yourself!) This fact is rigorized by noticing that:\( gcd( p^x , p^y) = p^{min(x,y)} \) and \( lcm( p^x, p^y) = p^{max(x,y)} \)

Then trivially this process would have to stop.

Just a thought: Maybe sum of the elements in the process might lead to the monovariant? (since I used product)

Log in to reply

Log in to reply

Log in to reply

Log in to reply

I would use monovariance for the first problem, letting S equal the number of pairs (j,k) possible in the problem. Each successive iteration would reduce this number by 1, since \(a_j\) and \(a_k\) would be replaced by two numbers, the first of which does indeed divide the second, as \(\gcd (a_j,a_k)| lcm (a_j,a_k)\). Since there are a finite number of pairs, and each iteration reduces S by 1, eventually S will be zero, and the process could not be continued.

Log in to reply

Can you explain in more detail why the number of pairwise coprime integers is a monovariance? It is not immediately obvious to me.

If that works, that's 1 way. Find many many more!

Log in to reply

Oops. I misread the question and thought the two numbers were chosen such that they were coprime. I have changed the idea in my original comment.

Log in to reply

Never mind. A proof that the sum is monovariant increasing and bounded from above is much harder than I thought.

Log in to reply