# Prove, that in the subset of $\{1,\ldots,150\}$ there are two disjoint pairs with the same sums.

Prove, that in the subset with cardinality $25$ of $\{1,\ldots,150\}$ there are two disjoint pairs with the same sums.

Well, there are at most $150+149=299$ possibilities of sums. But if we have a pair there are ${{23}\choose{2}}=253$ ways of choosing another disjoint to it, so theoretically it would be possible for all other pairs to have other sums that the one we chose.

• Don't you want ${25 \choose 2} = 300$ and not ${23 \choose 2}$? – Derek Allums Feb 9 '14 at 18:33
• Why did you write ${23}\choose{2}$ instead of ${25}\choose{2}$ ? Replacing with the correct value gives you the answer. – Denis Feb 9 '14 at 18:33

There are $\binom{25}{2}=300$ pairs. So two at least have the same sum. They must be disjoint. For if they share an element, and have the same sum, they are identical.
• I don't understand how the possible sums was found by $150+149=299$ ? Also why can't the two disjoint pairs be selected as $25\choose 2$*$23\choose 2$ – sam_rox Nov 18 '14 at 6:41
• The number of conceivable sums is in fact at most $297$ ($3$ to $299$) and each of these is achieved. I did not correct the $299$ because it made no difference to the logic of the Pigeonhole Principle argument, anything under $300$ is good enough. As to your second question, we are not counting disjoint pairs (you counted the number of pairs of pairs (you counted ordered pairs of pairs). We are just counting unordered pairs. – André Nicolas Nov 18 '14 at 6:58
• Yes, we count the number of pairs that can be formed from $35$ objects. There are $300$ of these. Since there are only $297$ conceivable sums, at least two distinct pairs must have the same sum. – André Nicolas Nov 18 '14 at 7:30