# Pigeonhole on sums of subsets from {1,…,99}

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.

• @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
– jet
Apr 7, 2023 at 16:35

Start with three numbers $$1\le a: $$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.

• 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
– jet
Apr 7, 2023 at 17:08
• 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$.
– D S
Apr 7, 2023 at 17:13
• 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.
– D S
Apr 7, 2023 at 17:14
• 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
– jet
Apr 7, 2023 at 17:15