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.

- If
``a[24]-a[23]`

` is valid, we got it! - If not, try
``a[24]-a[22]`

` is valid. If ok, we got it. - 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]`

`.

```
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.

- If

That's it.