Invariance and Monovariance Principle

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?

  1. (2008 Putnam) Start with a finite sequence a1,a2,,an a_1, a_2, \ldots , a_n of positive integers. If possible, choose two indices j<kj < k such that aja_j does not divide aka_k , and replace aja_j and aka_k by gcd(aj,ak) \gcd(a_j , a_k ) and lcm(aj,ak)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.

  2. 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.

Note by Calvin Lin
6 years ago

No vote yet
12 votes

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Well, I would perhaps use monovariance (for the first problem) in another way, noting first that gcd(aj,ak)×lcm(aj,ak)=ajak 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 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.

Anqi Li - 6 years ago

Log in to reply

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

Calvin Lin Staff - 6 years ago

Log in to reply

Find many many more!

After I played around with a small list of numbers I noticed something interesting about the prime factorisation of 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(px,py)=pmin(x,y) gcd( p^x , p^y) = p^{min(x,y)} and lcm(px,py)=pmax(x,y) 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)

Anqi Li - 6 years ago

Log in to reply

@Anqi Li I tried thinking about the sum, but it is a monovariant increasing, and doesn't provide to much more information about the actual sequence itself, and thus you couldn't determine whether the process would end.

Bob Krueger - 6 years ago

Log in to reply

@Bob Krueger If you can show that the sum is (strictly) increasing, and is bounded above, then that argument works.

Calvin Lin Staff - 6 years ago

Log in to reply

@Calvin Lin Well, it's clearly strictly increasing. But I don't see how it is bounded. Perhaps it is bounded by n times the LCM of all of the numbers?

Bob Krueger - 6 years ago

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 aja_j and aka_k would be replaced by two numbers, the first of which does indeed divide the second, as gcd(aj,ak)lcm(aj,ak)\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.

Bob Krueger - 6 years ago

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!

Calvin Lin Staff - 6 years ago

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.

Bob Krueger - 6 years ago

Log in to reply

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

Bob Krueger - 6 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...