1
$\begingroup$

Good evening fellow curious minds

Suppose S is a subset of size 10 from the positive integers 1,…,99.

Is it true that there will always be two distinct pairs from S that have the same sum?

I think a pigeonhole principle is needed, unless the claim is a falsehood, a counter example would be needed.

EDIT ——

Context for the problem: I was reading an article in a book by Martin Gardner (called ‘The Last Recreations’), the famous columnist of recreational maths problems. His question was about arbitrary subsets of a set of size 10 from 1,…,99. Which is again a pigeonhole proof. I wondered if the same holds for pairs, which is my question above.

What I tried: I didn’t get far but I thought of the number of sums you could get from 5 pairs (since S is size 10). There are 945 ways of splitting 10 into 5 pairs. The next step would be somehow comparing the pair sums for each partitioning and proving some partitioning has two equal pair sums.

$\endgroup$
1
  • $\begingroup$ @DS Sure, thanks. Apologies for not putting more effort in. It’s a sunny day here lol. Will add my work in an edit to the question $\endgroup$
    – jet
    Apr 7, 2023 at 16:35

1 Answer 1

1
$\begingroup$

Start with three numbers $1\le a<b<c$: $$S_3 = \{a,b,c\}$$Clearly, $a+b$, $b+c$ and $a+c$ are all distinct, so there do not exist any two pairs which have the same sum. Given $S_k$, find $S_{k+1}$ by the relation: $$S_{k+1} = S_k \cup \{(x+y-a+1)\}$$ where $x$ and $y$ are the two largest elements in $S_k$ and $a$ is the smallest element.

We prove by induction that no two pairs in $S_n$ have the same sum. The base case for $n=3$ is already proven, and we assume the claim holds for $S_k$.
Notice that all the pairs in $S_{k+1}$ which do not include this new element (or in other words, belong to $S_k$) have their sum at most $x+y$, while all pairs which include the new element have their sum at least $x+y+1$. So, no two pairs in $S_{k+1}$ have the same sum, since no two pairs in $S_k$ have the same sum.


Now, we need to find $a,b,c$ such that the largest element in $S_{10}$ is less than $100$. Clearly, $a=1, b= 2, c= 3$ minimizes the largest element in $S$. Finding $S_{10}$, we see that it is the Fibonacci Sequence, where $S_n$ contains the first $n+1$ Fibonacci numbers except $0$.

Thus, $\boxed{S= \{1,2,3,5,8,13,21,34,55,89\}}$ is a counterexample.

$\endgroup$
4
  • 1
    $\begingroup$ Really elegant. Thank you. A lovely induction. Is this the canonical way to construct a list of numbers with no two pairs having the same sum? Or did you come up w this on the fly. If so, I’d be interested in your thought process and how you got the idea for this solution. Thanks again $\endgroup$
    – jet
    Apr 7, 2023 at 17:08
  • 1
    $\begingroup$ First, I thought there were only $45$ pairs, but $195$ possible sums, so there was a fat chance a counterexample existed. Then, I thought about an algorithm such that when I add a new number to a list, still no two sums are equal. This immediately brought me to the idea that the new pairs should have sums greater than the old pairs. And then, I thought of $x+y-a+1$. $\endgroup$
    – D S
    Apr 7, 2023 at 17:13
  • $\begingroup$ Also, the Fibonacci sequence pops up in many such questions where sums of elements are involved. I was myself surprised that I did not think of it before and had to arrive at it the longer way. $\endgroup$
    – D S
    Apr 7, 2023 at 17:14
  • $\begingroup$ Thanks, that’s a great explanation. Reading it, I can see how one thing led to another. By the way, another sequence such that no two pairs have equal sum could be a power series, eg 1,2,4,8,16,… . Except that for this problem we have an upper limit of 100, so yours is more efficient in the sense of fitting the set of size 10 into a smaller bound $\endgroup$
    – jet
    Apr 7, 2023 at 17:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .