You have the 3 numbers { 4 , 1 + 2 2 , 2 } on a blackboard. You are permitted to perform the following operation whenever you want and as many times as you want:
Is it possible to attain the 3 numbers { 3 + 2 , 2 2 , 2 − 1 } after a finite number of operations?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
This is a very elegant solution! +1 for this man. :-)
I managed to prove that the absolute value of the product of the numbers either stays the same of increases and used it to solve the problem.
Log in to reply
Nice monovariant! Alternatively, you could have used the overall sum of the terms as a monovariant and gotten the contradiction quicker.
Log in to reply
I tried using the sum, but I wasn't able to make it work.
Log in to reply
@Jesse Nieminen – Btw, I managed to implement the O(n) algorithm I came up with in C++.
Sum of squares of the three numbers in the triple is invariant. Then, the rest follows easily as the sum of squares of the numbers in the two triples is different!! So, not possible to get the second triple.
Problem Loading...
Note Loading...
Set Loading...
Note that by applying the operation, the sum of the squares of the three numbers remains constant. Let's prove this:
Let the numbers be ( a , b , c ) . Thus, the new numbers are ( 2 a + b , 2 a − b , c ) . Here, the sum of the squares of each number is
2 ( a + b ) 2 + 2 ( a − b ) 2 + c 2 = 2 2 a 2 + 2 b 2 + c 2 = a 2 + b 2 + c 2
Therefore, the sum of the squares of all the numbers remains constant.
Note that 4 2 + ( 1 + 2 2 ) 2 + 2 2 = 1 6 + 1 + 8 + 4 2 + 2 = 2 7 + 4 2 , whereas ( 3 + 2 ) 2 + ( 2 2 ) 2 + ( 2 − 1 ) 2 = 9 + 2 + 6 2 + 8 + 2 + 1 − 2 2 = 2 2 + 4 2 . Since these values are unequal, we cannot achieve the second set of numbers from the first set.