Waste less time on Facebook — follow Brilliant.
×

Sum and Difference Replacement

I have a list of non-negative integers on a whiteboard. Every second, I pick two integers \(a\) and \(b\) from the list (where \(a\ge b\)), and replace them with \(a+b\) and \(a-b\).

Prove that one of the numbers will be \(\ge X\) in a finite amount of time, given any arbitrary integer \(X\). In other words, prove that the numbers on the blackboard increase without bound.

Note by Daniel Liu
2 years, 11 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Every second the sum of all of the numbers on the board increases by \(a-b\ge 0\). It's easy to convince yourself that it is impossible for the sum to increase by nothing (in other words, have \(a=b\)) for an arbitrarily long amount of time, so I'll leave that as an exercise. Thus the sum of all of the terms increase without bound. Also, it's trivial that there will never be a negative term, that is, at all times, each term must be nonnegative. Since the sum of all of the terms increases without bound, so does the lower bound on the largest term, thus the statement is proven. Nathan Ramesh · 2 years, 11 months ago

Log in to reply

Your result is not quite correct. If there are two zeros on the whiteboard, then you can keep performing the operation on the two zeros, and the numbers never change. Jon Haussmann · 2 years, 11 months ago

Log in to reply

If we can prove the condition for two arbitrary integers, then you can extend the logic to any other pairs of integers in the set.

\(\textbf{Case 1: }a\neq b\)

The two numbers at the start have a sum of \(a+b,\) which is one of the new numbers. The second set of numbers has a sum of \(2a.\) \(2a>a+b\Rightarrow a>b,\) which is one of the conditions of the problem.

The second iteration will produce the numbers \(2a\) and \(2b,\) which are both greater than the original \(a\) and \(b.\) Each number will double every two iterations.

\(\textbf{Case 2: }a=b\)

The numbers are \(a\) and \(a.\) The first iteration yields \(2a\) and \(0.\) The second iteration yields \(2a\) and \(2a.\) Once again, both numbers will double every two iterations.


Cases \(1\) and \(2\) can be combined, but I split them up to demonstrate it for what most people would try first: unequal numbers.

It is worth noting that this is not true if all of the numbers in the set are \(0.\) Trevor B. · 2 years, 11 months ago

Log in to reply

@Trevor B. Can you explain how you would generalize it for a group of integers? What if you did the operation on two numbers \(a\) and \(b\), and then did the second operation on some other pair, like \(a-b\) and \(c\)? Daniel Liu · 2 years, 11 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...