Solution for $(a)$: Let $A_i$ be set of numbers from $S$ congruent $i$ $mod 4$. Now assume the opposite for the sake of contradiction: WLOG let $a$ be from $A_1$. Now we have that for every $b$ from $A_1$ the number $\frac{a+b}{2}$ is in $A_1$ or $A_3$. Also for every $b$ from $A_3$ nubmer $\frac{a+b}{2}$ is in $A_0$ or $A_2$. Let $|A_i|=a_i$ and let number of those who place $\frac{a+b}{2}$ in $A_1$ be $x$ and those who place $\frac{a+b}{2}$ in $A_0$ be $y$. We have: $x+a_1\le \frac{n}{4}$, $a_1-x+a_3\le \frac{n}{4}$, $y+a_2\le \frac{n}{4}$, $a_3-y+a_0\le \frac{n}{4}$, so $n \ge 2a_1+2a_3+a_0+a_2> \frac{3n}{4}+a_1+a_3$ $\implies$ $a_1+a_3< \frac{n}{4}$ $\implies$ $a_0+a_2 > \frac{n}{2}$ so contradiction.

(a) Let $a \in S$ be the element that does not satisfy the condition. For every pair $(a \pm t, a\pm 2t)$, at least one of them is not in $S$. (There are $m=[ \, \frac{a}{2}] \, + [ \, \frac{n-a}{2}] \,$ such pairs) Take $(a+1, a+2)$, and remove the pair that contains $a+2$. (i.e., $(a+2, a+4)$) Take $(a+3, a+6)$, and remove the pair that contains $a+6$. (i.e., $(a+6, a+12)$) Take $(a+4, a+8)$ and $(a+5, a+10)$.... And we can get at least $\lceil \frac{m}{2} \rceil$ pairs where each element is included in at most one pair. $\Rightarrow$ $|S| \le n - \lceil \frac{m}{2} \rceil \le \frac{3n}{4}$. (b) Put $a=k$. We can construct $S$ by removing one of the elements from each pair we chose in (a), so that $S$ contains at most $\frac{n}{3}$ elements.