1
$\begingroup$

Here is problem 33 from "Putnam and Beyond" :

Given 50 distinct positive integers strictly less than 100, prove that some two of them sum to 99.

Now I answered the problem differently than the official solution in the book and I was hoping you could tell me if my answer is still correct, or if it is not, explain to me where I went wrong. So here is my answer:

As the book suggests I try and use the pigeon hole principle. In my answer the "pigeons" are all two element subsets of the given set and the "holes" are the possible values the sum of the two elements of any two element subset can take. There are 1225 two-element subsets of any such given set and the sum of the two members of these subsets can take any value from 1+2=3 to 99+98=197. Hence there are 1225 "pigeons" and only 195 "boxes". There must be more than two pigeons in every box and hence at least two subsets with sum of 99.

Thats my answer. Thanks for any help!

|cite|improve this question
$\endgroup$
  • $\begingroup$ How do you conclude that every box has at least two pigeons? $\endgroup$ – Lord Shark the Unknown Oct 8 '17 at 18:24
  • $\begingroup$ What you have shown is that there must be repeated sums in your list of all possible sums, not that $99$ must be among the sums. $\endgroup$ – N. F. Taussig Oct 8 '17 at 18:24
  • 1
    $\begingroup$ As stated, the claim is false : Choose $1,2,3,4\cdots,49,99$. Since $99$ alone does not count, we cannot get sum $99$ $\endgroup$ – Peter Oct 8 '17 at 18:31
  • $\begingroup$ OK I think I see where I went wrong now...thanks! $\endgroup$ – krtgdl Oct 8 '17 at 18:34
  • 1
    $\begingroup$ It was a typo in the book.The intended problem: $50$ distinct positive integers less than $99$. $\endgroup$ – quasi Oct 8 '17 at 18:37
-1
$\begingroup$

The simple answer to your question is that your choice of "pigeons" and "holes" didn't support a proof of the claim. That's not to say it didn't do something. As the commenters correctly pointed out, you showed that you can't have a set of $50$ numbers less than $99$ such that any two numbers in the $50$ sum to a unique number, relative to any other pair. If this is what the question had been asking, then your logic is absolutely sound.

But the quesiton wasn't asking that. It was asking for the existence of $99$ as one of the pairwise sums. And, in this case, the choice of pigeons and holes given in the book works, and yours doesn't.

The thing about the pigeon hole principle, or any other proof technique, is that it's a tool. And like any tool, it has to be applied the right way to solve the problem at hand. This is a great lesson for you as a mathematician- to see that there are many ways to apply a single tool to a single problem. It's not enough to say "The pigeon hole principle didn't work". You must say "The pigeon hole principle, with this choice of pigeons and holes, gives me this result, which doesn't seem to help." All the same, you mentally note it in case you need it later, and then you either change your choice of tool or try to apply the tool in a different way. Problem solving is an art, as much as a science.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you ! Realy helpful! $\endgroup$ – krtgdl Oct 8 '17 at 19:02
  • $\begingroup$ You're welcome :) $\endgroup$ – Colm Bhandal Oct 8 '17 at 19:11
0
$\begingroup$

The $49$ pairs $(1/98) , (2/97) , (3/96) ,\cdots (49,50)$ sum up to $99$. If you choose $50$ distinct positive integers, at least one pair must be hit twice.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Yes... I know, I did read the solution in the book. I really just wanted to know if my answer was correct, but I understand now where I went wrong. Still thanks. $\endgroup$ – krtgdl Oct 8 '17 at 18:40
  • $\begingroup$ What if you take numbers $1,2,3...,49,99$? $\endgroup$ – ZFR Dec 19 '17 at 10:07
  • $\begingroup$ @RFZ Look at the above comment about the typo in the book. In fact as stated, the claim is false (which I mentioned in a comment with exactly your choice) $\endgroup$ – Peter Dec 20 '17 at 9:26

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.