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.

  • 2
    $\begingroup$ Don't you want ${25 \choose 2} = 300$ and not ${23 \choose 2}$? $\endgroup$ – Derek Allums Feb 9 '14 at 18:33
  • 1
    $\begingroup$ Why did you write ${23}\choose{2}$ instead of ${25}\choose{2}$ ? Replacing with the correct value gives you the answer. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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$ $\endgroup$ – sam_rox Nov 18 '14 at 6:41
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Nov 18 '14 at 6:58
  • $\begingroup$ We have to consider thetotal pairs.Then distribute the pairs among the possible sums right?I was finding the ways of selecting two disjoint pairs $\endgroup$ – sam_rox Nov 18 '14 at 7:10
  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Nov 18 '14 at 7:30

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.