Sum and Difference

30 Nov 2011

Given 25 different numbers, prove that you can pick 2 numbers that their sum and difference do not equal any other numbers.

We should first address the problem formally:

Let a[1] < a[2] < … < a[25] be the 25 different numbers.

It's obvious that if we choose a[25] and a[i], their sum will not match any other numbers.

If their difference also does not match any other numbers, then it is great.

Anyway, let's assume that a[25] - a[i] = a[j] for i != j.

This means that a[1], a[2], …, a[24] can be divided into pairs.

The only valid combinations are:

a[25] - a[24] = a[1] a[25] - a[23] = a[2] . . . a[25] - a[13] = a[12]

This can be proved by contradiction.

Let a[25] - a[24] = a[2] and a[25] - x = a[1] Since a[1] < a[2], this means that x > a[24]. And this is impossible. Therefore, a[25] - a[24] must be equal to a[1].

Now let's consider a[24]. For a[24], even we assume the worst case that:

a[24] - a[23] = a[1] a[24] - a[22] = a[2] . . . a[24] - a[12] = a[12] or does not match any other numbers

We still get a[24] and a[12] and their difference does not match any other numbers. Now we need to prove that a[24] + a[12] != a[25]

As we can see from the first assumption, a[25] = a[12] + a[13] and a[24] > a[13], therefore, a[24] + a[12] != a[25]

And the proof is done.

The solution is to choose a[25] with any number that makes it valid. If that is not possible, then choose a[24] and a[12] instead.

In Retrospect

The first critical point is to divide cases.

If we can find a[25] and a[i] that is valid, then it ends. If we cannot, then we draft more conditions (e.g. the pairings)

The second point is to see that a[24] - a[12] = a[12] or does not match any other numbers.

The concrete examples that mirror all the assumptions in the proof are:

  • 1,2,3, …, 25
  • 2,4,6, …, 50
  • 3,6,9, …, 75
  • n, 2n, 3n, …, 25n

Actually, We can see that a[23] and a[24] do not really have to relate at all. We can craft almost any sequence.

The below is a special case where a[24] - a[12] != a[12].

1, 2, 3, 4, 5, 6, 7, 8, 9,10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26

Give it a kudos