# Sum and Differences

31 Mar 2012

The problem sounds familiar. I might already solved it. But that doesn't matter. I'll try to solve it again.

Here is the problem statement:

```Given 25 different positive numbers, prove that you can choose two of them such that none of the other numbers equals either their sum or their difference. ```

Ok, let's rephrase the problem:

```There are 0 < a[0] < a[1] < ... < a[24]. They are all positives. We can find a[i] and a[j] where a[i] > a[j] and, a[i] + a[j] != a[k] and, a[i] - a[j] != a[m] where (k is not i or j) and (m is not i or j) ```

Ok, so how do we begin? I somehow would really like to use contradiction.

```For every i and j, I will assume a[i] + a[j] = a[k] where a[k] > a[i] > a[j] ```

I should contradict it… but how? You can see that if I choose ``i=24``regardless of ```j```, the assumption is false.

Actually, we can choose ``i=23``, and it still works. Because if ```a[23] + a[j] = a[24]``, we can easily adjust to``a[23] + a[j-1]``` or ``a[23] + a[j+1]``.

Therefore, for some ``i``and ```j``,``a[i] + a[j] != a[k]```.

Let's move on to another one:

```For every i and j, I will assume a[i] - a[j] = a[m] where a[i] > a[j],a[m] ```

We should choose ``i=24``, as it is ok for the first condition.

1. If ``a[24]-a[23]`` is valid, we got it!
2. If not, try ``a[24]-a[22]`` is valid. If ok, we got it.
3. Repeat until finding the valid one

But how to prove that there will be a valid one?

We can see that ``a[24] - a[23] = a[c]``, and ```a[24] - a[22] = a[d]````. We can see that````a[d] > a[c]```

Let's generalize it.

```a[24] - a[x] = a[y]. As x decreases, y increases. ```

If there is ``x``that ```a[x] == a[y]``, then``a[24] = 2 * a[x]```. If there is ``a[x] = a[24] / 2``, we should choose it and we're done.

If there is no ``x``that ```a[x] == a[y]```, then …

I cannot contradict it because ``1, 2, 3, ..., 25````will be just fine here. There is no `````a[24]/2`` and``a[24] - a[11] = a[12]``` and ``a[24] - a[12] = a[11]``.

## Try it again

```For every i and j, I will assume a[i] - a[j] = a[m] where a[i] > a[j],a[m] ```

How about choosing ``i=23``?

Choosing ``a[23]`` is perfect because

• If there is ``x``that ```a[x] == a[y]`` and``a[23] + a[x] != a[24]```, then we got it!
• If there is ``x``that ```a[x] == a[y]`` and``a[23] + a[x] = a[24]```, then we can choose ``a[24]``and ```a[0]``` to be an answer instead…
• If there is no ``x``that ```a[x] == a[y]``, then it will terminate because, in``a[0]``` to ``a[22]``, there will be one ```a[j]``` that doesn't have its pair.
• If ``a[23] + a[j] = a[24]``, then we can choose ```a[24]`` and``a[0]``` instead…
• If ``a[23] + a[j] != a[24]``, then we got the answer.

That's it.