6
$\begingroup$

"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

$\endgroup$
5
  • $\begingroup$ Would a pair such that the difference was equal to one of the numbers in the pair be invalid (eg 1 and 2 from a set that didn't include 3) $\endgroup$ – StephenTG Mar 18 at 19:47
  • $\begingroup$ @StephenTG , please note that that this is what the question says, "such that none of the other numbers equals either their sum or their difference?" . Notice the key phrase, "none of the other numbers". $\endgroup$ – Hemant Agarwal Mar 18 at 19:51
  • $\begingroup$ Gotcha, just wanted to confirm. $\endgroup$ – StephenTG Mar 18 at 19:52
  • $\begingroup$ Do you actually mean positive integers? $\endgroup$ – Chris Cudmore Mar 18 at 20:25
  • $\begingroup$ @ChrisCudmore , no. 25 different positive numbers. $\endgroup$ – Hemant Agarwal Mar 18 at 20:26
6
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Maybe it is better to use A1, A2....A25 to denote that A1<A2... <A25 . Denoting different numbers with different alphabets is a bit confusing . $\endgroup$ – Hemant Agarwal Mar 18 at 20:12
  • $\begingroup$ @HemantAgarwal but how do you then indicate which ones pair together? $\endgroup$ – loopy walt Mar 18 at 20:14
  • $\begingroup$ " Let B1 be the largest after M. " What does this mean ? That B1 is the second largest number among these 25 numbers ? $\endgroup$ – Hemant Agarwal Mar 18 at 20:16
  • $\begingroup$ @HemantAgarwal Yes, exactly. $\endgroup$ – loopy walt Mar 18 at 20:17
  • $\begingroup$ "Let X be the set that are in no such pair and observe that X cannot be the singleton {A1} because the sum of the others (not M,A1,B1) would have to be 11B1 and 11M at the same time." This implies that A1+B1 = M. But, what is the proof that A1+B1 = M ? $\endgroup$ – Hemant Agarwal Mar 18 at 20:34
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ In my opinion, everything written after the following line, "$x_2 + x_{23} = x_{24}$ (in contradiction with the equations above, because $x_{24} \ne x_{25}$)" is redundant. To understand why, please see the following answer especially the comments given on the answer : puzzling.stackexchange.com/a/107918/57212 $\endgroup$ – Hemant Agarwal Mar 19 at 12:41
  • $\begingroup$ It seems to be claiming too much to say that $x_i + x_{25-i} = x_{25}$ for all $i=1,2,3,...$. $\endgroup$ – Lawrence Mar 20 at 8:49
  • $\begingroup$ @Lawrence well, if that wasn't the case, we would have found a number to go with $x_{25}$ so that the difference isn't one of the other numbers, and $x_{25}$ plus anything is definitely bigger than all the other numbers. $\endgroup$ – Bass Mar 20 at 8:58
1
$\begingroup$

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:

enter image description here

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:

enter image description here

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):

enter image description here

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.

$\endgroup$
0
$\begingroup$

enter image description here

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 ?

$\endgroup$
6
  • $\begingroup$ "But, don't we need to prove that x1+x23 cannot be = x24 before assuming that x2….x23 will get paired up." No, there is no specific order required. If you manage to find one single tuple like e.g. (x2, x24) for which you cannot find the sum or the difference in the set (x1, ..., x25) then this contradicts the initial postulate. BTW, I have the feeling that, since it ends with questions, your answer is the actual question of the puzzle... $\endgroup$ – xhienne Mar 19 at 11:19
  • $\begingroup$ @xhienne , I am looking for more intuitive answers also. I sort of understood the point you made and was surprised that it didn't strike me that way. So, we have proven that x24+x2 > x25 and that x24-x2 is not equal to x23 . But then, don't we need to show that x24-x2 cannot be any other number (such as x22, x21, etc ) either ? $\endgroup$ – Hemant Agarwal Mar 19 at 11:38
  • $\begingroup$ This is the same reasoning that leads to conclude that x25=x24+x1=x23+x2=...=x13+x12. If you have x24-xn=x2 with n < 23 then the difference x24-x23 is not in the set since it is < x2 and it is not x1. Therefore x24=x2+x23=x3+x22=...=x12+x13 => x24=x25 $\endgroup$ – xhienne Mar 19 at 12:01
  • $\begingroup$ @xhienne , " the difference x24-x23 is not in the set since it is < x2 and it is not x1." Apologies if I am forgetting something but why can't x24-x23=x1 ? $\endgroup$ – Hemant Agarwal Mar 19 at 12:11
  • 1
    $\begingroup$ OK, I get you, and now I understand your initial question (why don't we prove that x24=x23+x1). Let me reword it like this: "why in their answer are they considering x24 along with x2,...,x23 and not with x1,...,x23?" (can we agree on this rewording?). Their reason is given as "x2,...,x23 must also be paired" (which I agree with). If you extend the set to the 23 numbers x1,...,x23 then you cannot pair all of them since 23 is odd. IOW, if x24=x23+x1 then x24=x12+x12 and you have found a pair (x12,x24) that is not in the set. $\endgroup$ – xhienne Mar 19 at 12:27
-2
$\begingroup$

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!

$\endgroup$
3
  • 6
    $\begingroup$ What if we chose 24 and 12? Sum is 36 (out of set), difference is 12 (not a number in the set outside the pair) $\endgroup$ – StephenTG Mar 18 at 19:59
  • $\begingroup$ Gah! I didn't see that notice made in the comments... $\endgroup$ – TakingNotes Mar 18 at 20:05
  • $\begingroup$ I was working on a similar proof when the 12 24 issue hit me. $\endgroup$ – Chris Cudmore Mar 18 at 20:11
-2
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ The order does not matter ..we are talking about the absolute difference. $\endgroup$ – Hemant Agarwal Mar 18 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.