4
$\begingroup$

I am trying to prove that, given a set of $25$ positive numbers, it is always possible to choose a pair of them such that none of the other numbers equals either their sum or their difference.

For instance, if you take the set to be the numbers from $1$ to $25$, taking $12$ and $24$ will give a sum of $36$ which is not in the set, and a difference of $12$ which is not a different element of the set than the two chosen.

I feel like the proof of this is a lot simpler than I am making it. So far I have split the situation into two cases, being able to generalise for evenly spaced numbers by simply suggesting the first element chosen be a number $y \in S$ such that $2ny \in S$ but $3ny \notin S$, where $n$ is the space between each number. Thus these two elements will always give a sum outside of the set and difference of $y$. However, this does not help at all for a random group of numbers and I feel there is a better argument that covers both cases.

Considering the problem as a counting argument, I have determined that there are $300$ possible pairs within the set of $25$ numbers. If I can show that there are more pairs than possible sums and differences within the set, I am done. I have considered using a system of triples to express this, i.e. a subset of three elements $\{x_i,x_j,x_k\}$ of $S$ such that $x_i+x_j=x_k$. Thus each triple will give the sum of a pair and the difference of two pairs. However, counting the number of triples becomes difficult.

I considered tackling this by counting the number of 'statements' created by each, i.e. sum or difference created by the pairs and triples. Each pair $(a,b)$ would give me a sum and a difference $a+b=c, a-b=d$ for $a,b \in S$ but $c,d$ not necessarily in $S$. Each triple gives me a sum and two differences $x_i+x_j=x_k, x_k-x_i=x_j, x_k-x_j=x_i$ for $x_i,x_j,x_k \in S$. Thus I figure this simplifies the proof into showing that there are more sums and differences created by the pairs than by the triples. Then I just want to show that $300\cdot 2 \geq |T|\cdot3$, where $T$ is the set of triples. Thus $|T| \leq200$.

But then again, this doesn't ensure a single pair has neither its sum nor difference within the set, only that at least one pair has one of its sum or difference outside of the set. Argh! The circles begin!

Now I am completely stuck. How do I go about proving that the number of triples is below a certain number? Am I going about this in the wrong direction? Have I oversimplified the problem? Any help at all is much appreciated!

$\endgroup$
0
$\begingroup$

Assume we have some set $A=\{a_1, a_2, \ldots, a_{25}\}$ which contradicts our assumption.

Lemma: For each integer $i$, $1\le i\le 24$, the equality $a_i+a_{25-i}=a_{25}$ holds.

Proof: Note that since $a_{25}+a_t\notin A$ for each integer $t, 1\le t\le 24$, it follows that $a_{25}-a_t\in A$ for all such $t$. It follows that, since: $$a_{25}-a_1>a_{25}-a_2>\ldots>a_{25}-a_{24}$$ these $24$ terms must be equal to $a_{24}, a_{23}, \ldots, a_1$ respectively. The lemma immediately follows.

Now we use a similar trick to finish. Due to the lemma, we see that for any $i, j$ such that $i>j, i+j>25$, we have $a_i+a_j>a_{i}+a_{25-i}=a_{25}$, so $a_i-a_j\in A$. Now consider the $24$ terms: $$a_{25}-a_1>a_{25}-a_2>\ldots >a_{25}-a_{12}>a_{24}-a_{12}>$$ $$a_{24}-a_{13}>a_{23}-a_{13}>a_{22}-a_{13}\cdots >a_{14}-a_{13}$$ It follows that these are $a_{24}, a_{23}, \ldots, a_1$ in that order. But then $a_{24}-a_{12}=a_{12}$ and $a_{24}+a_{12}>a_{25}$, a contradiction. So the existence of $A$ is impossible and we are done.

$\endgroup$

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.