$S = \{1,2,...,2005\}$, $A = \{a_{1}, ..., a_{k}\} \subset S$ with $a_{i}+a_{j}$ not multiple of 125 whenever $a_{i} \ne a_{j}$. What is $max(k)$?
Attempt:
After exploring, I found that
- We can put only one multiple of 125 among $125,...,2000$ to $A$.
I found that for easier problem: if $S=\{1,2,...,250\}$, then $$ A = \underbrace{\{1,2,...,62 \}}_{S_{1}} \cup \underbrace{\{126, 127, ..., 187\}}_{S_{2}} \cup \{c\} $$ where $c$ is any one of 125 or 250, satisfies the demanding rule. $|A|=62+62+1$.
Because notice for any $x,y \in S_{2}$ and any $x_{1} \in S_{1}$, then $250 <x+y < 375$, and $125 <x_{1}+x< 250$. And for any $x,y \in S_{1}$, $x+y <125$.
Next, let $B = S - A = (\{63,...,125\} \cup \{188,...,250\})- \{c\}$. $|B|=125$. Notice that for any $b \in B$ there is a partner $a \in A$ such that $a+b=125$ (or $250$).
For this easier problem, it will be proven that $max(k)=125$. Assume there is $C$ satisfying rule such that $|C|=126$. Then at least one element of $C$ must be from $B$. Let $C = B' \cup A'$ with $B' \subset B$ and $A' \subset A$. If $|B'|=k$ and $|A'|=126-k$ with $1 \le k \ge 125 $, then it is easy to see there will be contradiction for any value of $k$. So $|C|=126$ is impossible, and this implies $|C|>126$ is also impossible.
Now back to original problem: Let $$S_{1} = \{1,2,...,62\} $$ $$S_{2} = \{125+1,...,125+62\} $$ $$S_{3} = \{2(125)+1, ..., 2(125)+62\}$$ $$...$$ $$S_{16} = \{15(125)+1, .., 15(125) + 62\}$$ $$S_{17} = \{16(125)+1, 2002, 2003, 2004, 2005\}$$
We have these facts:
For $S_{1}$ any 2-combination will have sum less than 125. For $i > 1$, for any $x,y \in S_{i}$ then $ (i)125 < x+y < (i+1)125$.
Since $S_{i} = \{i(125) + 1, ..., i(125) + 62\}$, then for any $x_{i} \in S_{i}$, and $x_{j} \in S_{j}$, we have $$ (i+j)125 < x_{i} + x_{j} < (i+j)125 + 124 < (i+j+1)125 $$
So $A = S_{1} \cup S_{2} ... \cup S_{17} \cup \{c\} $ where $c$ is can be any number from $\{125,...,2000\}$ satisfy the rule. $|A| = 62(16) + 5 + 1 = 998$.
We will show that $max(k) = 998$. Let $B = S - A$, notice that for any $b \in B$ there exist an $a \in A$ such that $a+b$ is multiple of 125. $|B| = 1007$.
If there exist $C$ satisfying the rule, with $|C|=999$, then it at least has one element from $B$.
Let $C = B' \cup A'$ with $B' \subset B$, $A' \subset A$. If $B' = k$, $A' = 999-k$, with $1 \le k \le 999$.
How to finish the proof?
Rather than talk about ranges of numbers, talk about residues $\bmod 125$. As you note, you can have only one number equivalent to $0 \bmod 125$. You cannot have both a number equivalent to $1 \bmod 125$ and $124 \bmod 125$. There are more numbers equivalent to $1$ than to $124$, so take all the ones equivalent to $1$. Make the same argument for all the other pairs of residues $(n, 125-n)$. We get $1$ number equivalent to $0$, $17$ equivalent to each of $1-5$, and $16$ equivalent to $6-62$ for a total of $998$