IMC 2013 · Problem 2

Let $p$ and $q$ be relatively prime positive integers. Prove that

$$\sum_{k=0}^{pq-1} (-1)^{\left\lfloor \frac{k}{p} \right\rfloor + \left\lfloor \frac{k}{q} \right\rfloor} = \begin{cases} 0 & \text{if } pq \text{ is even}, \\ 1 & \text{if } pq \text{ is odd}. \end{cases} \tag{$*$}$$

(Here $\lfloor x \rfloor$ denotes the integer part of $x$.)