Suppose we take a 501 element subset $S$ of the first 999 positive integers. Prove that there exists $a_x \not= a_y, a_z \in S$ such that $a_x+a_y=a_z$.

The 501 elements seems pretty close to 1000/2, so it seems to be an application of the pigeon hole principle with 500 "groups". Any hints on how to split $S$ into groups?

  • $\begingroup$ To clarify: If $S=\{500,501, \cdots, 1000\}$ the only triple that works is, I think, $500+500=1000$, so I assume that $a_x$ might equal $a_y$? $\endgroup$ – lulu Sep 24 '19 at 20:07
  • $\begingroup$ You noted that 1000/2=500. It seems that you have to half the set. What more natural way to do it than to separate odd and even numbers? $\endgroup$ – Lucio Tanzini Sep 24 '19 at 20:08
  • $\begingroup$ @LucioTanzini ? You can't choose $S$. You have to prove you can do it whatever $S$ may be. $\endgroup$ – almagest Sep 24 '19 at 20:11
  • $\begingroup$ I didn't mean S, I meant the numbers up to 1000 $\endgroup$ – Lucio Tanzini Sep 24 '19 at 20:15
  • 1
    $\begingroup$ OK, I see you changed the question, but this is problematic... If we restrict to $a_x \neq a_y$, then the statement cannot be proved, because it is false, as shown by the counterexample of @lulu where $S=\{500, 501, \dots, 1000\}$. I.e. in that $S$, you cannot find $a_x \neq a_y, a_z$ s.t. $a_x + a_y = a_z$. OTOH, if we revert to the original question, which allows $a_x = a_y$, then the statement can be proved. Which do you want? $\endgroup$ – antkam Sep 25 '19 at 20:50

This answer assumes $a_x = a_y$ is allowed (i.e. the OP's original wording).


Let $m$ be the maximum element in $S$. Then there are $500$ selected numbers among $A = \{1, 2, \dots, m-1\}$.

Now partition $A$ properly and apply pigeonhole principle.

If $m<1000$ you can be done right away with the right partition. For $m=1000$ you need a tiny bit more work, but not much.

HINT #2 (update 9/25/2019)

Consider $m=999$, so there are $500$ numbers selected from $A = \{1, \dots, 998\}$. You need to partition $A$ into $499$ subsets, each of size $2$. Then pigeonhole would say there is a subset where both numbers are selected. If you partition correctly, you can immediately find $a_x, a_y, a_z$ s.t. $a_x + a_y = a_z$.

Can you finish from here, or do you need more hint?

  • $\begingroup$ I think I need another hint. Perhaps enlightening me with the partition of $m<1000$ will help? $\endgroup$ – Baker013273213 Sep 25 '19 at 20:36
  • $\begingroup$ What about the question gives away the "main idea" of the partition. I'm struggling on thinking on what kind of construction that would help to prove it. $\endgroup$ – Baker013273213 Sep 26 '19 at 1:07

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.