Friday, November 30, 2012

Friday challenge - 30/11/2012

This week's Friday challenge is the following problem aimed at high school students. A solution to this problem will be posted next week.

Let there be several numbers written on a blackboard. It is allowed to erase any two of them, which are not simultaneously equal to 0, say $a$ and $b$ and replace them with $a - b/2$ and $b+a/2$. Is it possible after several of such steps to arrive at the original numbers?

Source: www.nature.ru

Hint: Check what happens to the sum of squares of these numbers.

Solution

1 comment:

  1. Let A0 be the initial set of numbers written on the blackboard. Let S0 be the sum squares of these numbers.

    Assume that there exists a sequence of given operations that leads to A0 -> A1 -> A2 ->...->A0.
    So the sum of squares of the numbers in the set should also follow a similar sequence:
    S0 -> S1 -> S2 ->...-> S0.

    Applying the mentioned operation to a, b in A_k, clearly A_(k+1) and A_k would differ only at these two positions. Therefore
    S_(k+1) - S_k = (a-b/2)^2 + (b+a/2)^2 - a^2 - b^2.

    = (a^2 + b^2)/4 > 0 for a,b not both zero.

    This implies that S_k is strictly increasing. And for such a sequence to exist,
    S0 < S1 < S2 < ... < S0, which is absurd.

    This contradicts the assumption of existence of such a sequence.

    ReplyDelete