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.
Best Answer
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.