CroatianCompetitions

Let $k$ and $l$ be positive integers such that $0 \le k < l \le n-1$. Sums $1+2+\dots+k$ and $1+2+\dots+l$ give the same remainder modulo $n$ if and only if
$$\frac{1}{2} k (k + 1) \equiv \frac{1}{2} l (l + 1) \pmod{n},$$
i.e. if and only if $l(l+1) - k(k+1) = (l-k)(l+k+1)$ is divisible by $2n$.
Notice that $l-k$ and $l+k+1$ give a different remainder modulo $2$.

a) Let $n = 2^m$. Then $2n = 2^{m+1}$, and since $l-k$ and $l+k+1$ give a different remainder modulo $2$, one of them has to be divisible by $2^{m+1}$.
On the other hand, clearly $l-k < 2^{m+1}$, and we have $l+k+1 \le 2l < 2n = 2^{m+1}$, so none of those numbers is divisible by $2^{m+1}$.
We conclude that distinct elements of the set $S$ give different remainders modulo $n$.

b) Let $n = 2^m s$ where $s > 1$ is odd.
We have to choose $k$ and $l$, $0 \le k < l \le n-1$ such that
$$(l-k)(l+k+1) = 2n = 2^{m+1}s.$$
If $2^{m+1} \ge s+1$ we will choose them so that $l+k+1 = 2^{m+1}$ and $l-k = s$, and if $2^{m+1} \le s-1$ then we will choose them so that $l+k+1 = s$ and $l-k = 2^{m+1}$.
In the first case solving the system we get $l = 2^m + \frac{s-1}{2}$ and $k = 2^m - \frac{s+1}{2}$. Clearly $0 \le k < l$. Since $2 < s \le 2^{m+1} - 1$, it follows that
$$l = 2^m + \frac{s-1}{2} \le 2^m + \frac{2^{m+1}-2}{2} = 2^{m+1} - 1 < 2^m s - 1.$$
In the second case we get $l = \frac{s-1}{2} + 2^m$ and $k = \frac{s-1}{2} - 2^m$. Again it is clear that $0 \le k < l$. Finally, we check
$$l = \frac{s-1}{2} + 2^m \le \frac{s-1}{2} + \frac{s-1}{2} = s-1 \le 2^m s - 1.$$