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 in a finite amount of time, given any arbitrary integer . In other words, prove that the numbers on the blackboard increase without bound.
Note by
Daniel Liu
6 years, 10 months ago
No vote yet
1 vote
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:
*italics*or_italics_**bold**or__bold__paragraph 1
paragraph 2
[example link](https://brilliant.org)> This is a quote# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"\(...\)or\[...\]to ensure proper formatting.2 \times 32^{34}a_{i-1}\frac{2}{3}\sqrt{2}\sum_{i=1}^3\sin \theta\boxed{123}Comments
Every second the sum of all of the numbers on the board increases by a−b≥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.
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.
Case 1: a=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⇒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.
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.
Log in to reply
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?
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.