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=24regardless 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 toa[23] + a[j-1]`` or `a[23] + a[j+1]`.

Therefore, for some `iand ``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 thata[d] > a[c]``

Let's generalize it.

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

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

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

I cannot contradict it because `1, 2, 3, ..., 25will be just fine here. There is no ``a[24]/2` anda[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 `xthat ``a[x] == a[y]` anda[23] + a[x] != a[24]``, then we got it!
  • If there is `xthat ``a[x] == a[y]` anda[23] + a[x] = a[24]``, then we can choose `a[24]and ``a[0]``` to be an answer instead…
  • If there is no `xthat ``a[x] == a[y]`, then it will terminate because, ina[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]` anda[0]`` instead…
    • If `a[23] + a[j] != a[24]`, then we got the answer.

That's it.

Give it a kudos