Let $S=\{1, 2, 3, ..., 1000\}$. Bob has decided to paint $701$ of these integers in green. Prove that one can choose $400$ of these green integers whose total sum is equal to $200,000$
I know this has to do with the pigeonhole principle but I am having trouble setting it up. Here what I have so far:
We can denote the set that consists of two elements: $k$ and $1000-k$ by $A_k$.
This means $A_k=\{k, 1000-k\}$ (let's call this a set) for $k=1, 2, 3, ..., 500$.
Now Bob will paint $701$ of these numbers in green, this means since we have $500$ sets, there will be $201$ sets where both numbers of the set are painted in green.
Now I do not know why we can always choose $400$ green numbers that sum to $200,000$?
Let we define a green number $k$ as good if $1000-k$ is also a green number. We just have to show that there are at least $400$ (i.e. $200$ pairs of) good green numbers. Let we consider the couples $\{1,999\},\{2,998\},\ldots,\{499,501\}$. We have to paint in green at least $700$ of their elements: if we assume$^{\color{purple}{(T)}}$ that there are at most $199$ pairs of good green numbers, there are at most $199$ couples completely colored in green, so there are at least $499-199=300$ couples with just $0$ or $1$ element painted in green. So there are at most $300+2\cdot 199=698$ green-colored integers in $[1,1000]$, but our hypothesis gives us that they are $701$, so $\color{purple}{(T)}$ cannot hold.