Can we always choose 2 numbers from 25 numbers with the following properties?

Question

"Given 25 different positive numbers, can you always choose two of them such that none of the other numbers equals either their sum or their difference?"

P.S:

1. Looking for various ways to solve the above question. Brownie points to answers which are intuitive. An intuitive answer, according to me, is one that is not just easy to understand but also makes one go, "Oh yes..that was so obvious. Why didn't I think of solving it this way. "

2. I am also mentioning the answer given at the source which I was not able to understand completely until @xhienne helped me understand it. The original answer, my confusion with it and @xhienne 's comments that helped me clear my confusion can be seen by clicking the following link https://puzzling.stackexchange.com/a/107918/57212

Answer 1

Does perhaps fail on the "intuitive" front, but may serve as a start:

The answer is

Yes

Proof:

Let us first examine the case if there were not 25 but 24 or, in fact, any even number of numbers: We then could simply pick the largest, call it M, so the sum with whichever other number we pick is definitely not in the set.
Next we could observe that of the remaining 23, those whose difference with M is another number in the set form pairs (M-B=A if and only if M-A=B). As 23 is odd there must be at least one unpaired number and we can pick that as the second.

With a bit of fiddling we can apply this argument also to the 25 (or general odd > 3) case:

First, remove the largest element, MM, and apply the above construction to the remaining 24. If there are multiple unpaired numbers we are done, because we can then pick one that does not equal MM-M.
Otherwise we have 11 pairs that sum to M. If the remaining one is not MM-M we are done. Otherwise the sum of the 24 numbers other than MM is 11xM+MM. This means that they cannot come in pairs that sum to MM because in that case they would have to sum to 12xMM. We can therefore pick MM and an unpaired other.

Small (N=7) example:

Let the given set be 1,2,3,4,5,6,7.
Then 7 is MM and 6 is M.
Pairs that sum to M are 1,5 and 2,4. Leftover is 3.
As 6+3 != 7 we can choose 6 and 3.

To see how the second case works replace 7 with 9, so given set is 1,2,3,4,5,6,9.
9 is MM, 6 is M
Pairs that sum to M are 1,5 and 2,4. Leftover is 3.
As 6+3 = 9, this time, we cannot choose 6 and 3.
But now the last branch of the proof kicks in:
Sum of elements other than MM is 1+5 (=6) + 2+4 (=6) + 6+3 (=9), or 2xM+MM
Elements that sum to MM are 3,6 and 4,5. If the remaining two would also sum to MM we would have 1+2 + 3+6 + 4+5 = 3xMM = 3x9, but we have already established that the sum is 2xM+MM = 2x6+9. Therefore 1 and 2 do not sum to 9 and either one can be chosen alongside 9.

Answer 2

Here's my silly approach (intuitiveness highly arguable, robustness somewhat dodgy too, entertainment value hopefully somewhat better):

To get started, let's label the numbers, from smallest to largest, with $x_1$ to $x_{25}$.

Then, we'll assume (ignoring all complaints to the contrary) that such two numbers don't exist. Then we can tell (by trying to pick the largest number $x_{25}$ and any other number) that

$x_1 + x_{24} = x_{25}$
$x_2 + x_{23} = x_{25}$
$x_3 + x_{22} = x_{25}$
$\dots$
$x_{12} + x_{13} = x_{25}$

Then, trying to pick the next largest number $x_{24}$ and another number bigger than $x_{1}$, we either find a suitable number (impossible under our assumption), or get one of the following two results:

$x_2 + x_{23} = x_{24}$ (in contradiction with the equations above, because $x_{24} \ne x_{25}$)

or

$x_1 + x_{23} = x_{24}$
$x_2 + x_{22} = x_{24}$
$x_3 + x_{21} = x_{24}$
etc.
_{^{(We're deliberately not going to look at what happens at $x_{12}$, because we don't want to create an exact duplicate of @loopy walt's answer.)}}

Now we can do maths with this system of equations:

Plugging $x_1 + x_{23} = x_{24}$ into $x_1 + x_{24} = x_{25}$ we get

$x_1 + x_1 + x_{23} = x_{25}$

and comparing this with $x_2 + x_{23} = x_{25}$ we find that

$x_1 + x_1 = x_2$

and doing the same with $x_2 + x_{22} = x_{24}$, $x_1 + x_{24} = x_{25}$ and $x_3 + x_{22} = x_{25}$ yields

$x_1 + x_2 = x_3$

Continuing in a similar manner, we find out that under the constraints created by the requirements, we can actually do addition on the indexes $N$ of $x_N$!

$x_m + x_n = x_{m+n}$

But this means we have an easy way to find the desired pair of numbers: we'll just pick $x_{10}$ and $x_{20}$. Their sum is $x_{30}$ which never was in the set, and their difference is $x_{10}$, which we just removed by picking it.

So by making the assumption that "there's no way to choose two numbers in such a way" we've managed to actually find two such numbers, which is the final contradiction we needed to show that our initial assumption must have been wrong.

Answer 3

As OP is asking for intuition, here are a few pictures:

We can think of an ordered pair as a point in the plane. We can then visualise the sum by drawing a diagonal left up and looking at the y-intercept. Similarly, we can get the difference by drawing a diagonal left down:

We can also read this back-to-front. For example, given the sum, we can put it on the y-axis and draw the diagonal right down (until we hit the x-axis). The points on this diagonal are the pairs of positive numbers with the given sum.

Now, let us apply this to the question:

In the leftmost column, on the y-axis marked by filled circles we have the 25 numbers x1...x25. The diamonds are all ordered pairs xi,xj. Their sum or difference is in x1...x25 exactly if the diamond lies on one of the blue or teal diagonals. For this to be true for all pairs we can see that the xi must be equidistant (@Bass's result):

So this looks as if it were possible. Why is it not? Because of the requirement that the pair and the difference must be distinct. Without this requirement x1=1,x2=2, etc. would indeed be a counterexample. The requirement can be phrased as that pairs of the form t,2t (red line) must lie on a blue diagonal, teal does not count for those. But there are quite a few diamonds on the red line for which there is no blue diagonal.

Answer 4

Given above is the answer mentioned at the source, which I am not able to completely follow. I understood, from the answer given in the image above, that the assumption that every two numbers have either their sum or their difference represented among the other numbers implies that

$x_1 + x_{24} = x_{25}$
$x_2 + x_{23} = x_{25}$
$x_3 + x_{22} = x_{25}$
$\dots$
$x_{12} + x_{13} = x_{25}$

Now, let us look at $x_{24}$. We know that $x_{24}+x_{1}= x_{25}$ . So, we only need to see if for i = (2 to 23), $x_{24}+x_{i}$ or $x_{24}-x_{i}$ is represented by the other numbers. But, $x_{24}+x_{i} > x_{25}$ . So, the sum is not possible. Now, let us look at the difference.

And, this is where I start to not completely follow the answer. The answer above says that $x_{2}, x_{3} ..... x_{23}$ need to be paired up, i.e

$x_{2}+x_{23}= x_{24}$
$x_{3}+x_{22}= x_{24}$
.....
$x_{12}+x_{13}= x_{24}$

This would mean that $x_{2}+x_{23}$ will have to be =$x_{24}$ which is a contradiction since we know that $x_{2}+x_{23} = x_{25}$

But, don't we need to prove that $x_{1}+x_{23}$ cannot be = $x_{24}$ before assuming that $x_{2}$….$x_{23}$ will get paired up.

Is the proof given in the image above, complete or does it need to prove more things ?

Answer 5

No. This is because...

If we just focus on the difference part, then we realise that the difference of the two numbers is going to be less than the largest number in the set, because we can't go into the numbers. Then, an easy solution pops up. If we were to make sure that we have all the numbers below the biggest in our set, then we wouldn't be able to encounter any that we couldn't solve. So if we were to have all the numbers from 1 - 25 in the set, then there wouldn't be any differences that weren't already attributed for!

We can go a bit further and extrapolate that...

Surprisingly, this solution can be replicated an infinite amount of time, as if we take all the numbers from the previous set and multiply them by n, then we find that for a - b = c, na - nb = nc, and we know that we must have nc because we have all the previous numbers (including c) multiplied my n!

Answer 6

However,

if the order matters (since the difference is noncommutative), the answer is "yes"

since

we can always pick the second-largest number and the largest one (necessarily in that order!). Their sum is obviously outside the set (since it's greater than the largest number), and their difference (again, in that order) is negative, so it's too outside the set (since all 25 numbers are positive).