# Pigeonhole principle on 1000 positive integers

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?

• 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$? – lulu Sep 24 '19 at 20:07
• 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? – Lucio Tanzini Sep 24 '19 at 20:08
• @LucioTanzini ? You can't choose $S$. You have to prove you can do it whatever $S$ may be. – almagest Sep 24 '19 at 20:11
• I didn't mean S, I meant the numbers up to 1000 – Lucio Tanzini Sep 24 '19 at 20:15
• 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? – antkam Sep 25 '19 at 20:50

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

HINT

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?

• I think I need another hint. Perhaps enlightening me with the partition of $m<1000$ will help? – Baker013273213 Sep 25 '19 at 20:36
• 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. – Baker013273213 Sep 26 '19 at 1:07