Putnam 1998, Problem B-4

Find necessary and sufficient conditions on positive integers \( m \) and \( n \) so that
\[
\sum_{i=0}^{mn-1} (-1)^{\lfloor i/m \rfloor + \lfloor i/n \rfloor} = 0.
\]

Solution:
For convenience, define \( f_{m,n}(i) = \left\lfloor \frac{i}{m} \right\rfloor + \left\lfloor \frac{i}{n} \right\rfloor \), so that the given sum is \( S(m, n) = \sum_{i=0}^{mn-1} (-1)^{f_{m,n}(i)} \). If \( m \) and \( n \) are both odd, then \( S(m, n) \) is the sum of an odd number of \( \pm 1 \)'s, and thus cannot be zero. Now consider the case where \( m \) and \( n \) have opposite parity. Note that \( \left\lfloor \frac{i}{m} \right\rfloor + \left\lfloor \frac{k - i + 1}{m} \right\rfloor = k - 1 \) for all integers \( i, k, m \). Thus \( \left\lfloor \frac{i}{m} \right\rfloor + \left\lfloor \frac{mn - i - 1}{m} \right\rfloor = n - 1 \) and \( \left\lfloor \frac{i}{n} \right\rfloor + \left\lfloor \frac{mn - i - 1}{n} \right\rfloor = m - 1 \); this implies that \( f_{m,n}(i) + f_{m,n}(mn - i - 1) = m + n - 2 \) is odd, and so \( (-1)^{f_{m,n}(i)} = -(-1)^{f_{m,n}(mn - i - 1)} \) for all \( i \). It follows that \( S(m, n) = 0 \) if \( m \) and \( n \) have opposite parity.

Now suppose that \( m = 2k \) and \( n = 2l \) are both even. Then \( \left\lfloor \frac{2j}{2m} \right\rfloor = \left\lfloor \frac{2j + 1}{2m} \right\rfloor \) for all \( j \), so \( S \) can be computed as twice the sum over only even indices:
\[
S(2k, 2l) = 2 \sum_{i=0}^{2kl-1} (-1)^{f_{k,l}(i)} = S(k, l)(1 + (-1)^{k + l}).
\]
Thus \( S(2k, 2l) \) vanishes if and only if \( S(k, l) \) vanishes (if \( 1 + (-1)^{k + l} = 0 \), then \( k \) and \( l \) have opposite parity and so \( S(k, l) \) also vanishes).

Piecing our various cases together, we easily deduce that \( S(m, n) = 0 \) if and only if the highest powers of \( 2 \) dividing \( m \) and \( n \) are different.