Proof. We can view the sum in question as follows: Take an \(a \times b\) grid. Color even-numbered rows white and odd-numbered rows black. Then invert the color of squares on every other set of \(b\) “consecutive” cells, where consecutive allows wrap-around at the border of the square. Now we apply this combinatorial interpretation to prove the desired inequality.

We transform such an \(a_0 \times b_0\) grid and into an \(a\times b\) grid as follows: stretch each square into \(d\) squares. Then duplicate the grid \(d\) times, possibly inverting the colors in even indexed duplicates, and append these duplicates to the bottom of the grid. Thus, we can bound the – i.e., deviation from half of the grid area – by \(d^2\) times the badness before. And in general this is tight. That is, for some \(a,b\) it really will be \(d^{2}\) times worse.

Proof. Define the of a point \(x\in [ab]\) to be \(f_a(x)\oplus f_b(x) \in \left\{ 0,1\right\}\).

If \(ab\) is even, there is a simple involution: \[x\mapsto ab-1-x.\] We claim that this involution is color flipping, i.e., \[f_a(x)\oplus f_b(x) = 1 \oplus f_a(ab-1-x)\oplus f_b(ab-1-x).\] To see this, observe that for all integers \(x\) we have \[\left\lfloor \frac{x}{a} \right\rfloor \equiv 1 + \left\lfloor \frac{-1-x}{a} \right\rfloor \mod 2.\] Thus, pairing terms we find that the sum in the lemma statement is exactly \(\frac{ab}{2}\).

If \(ab\) is odd, the situation is slightly more subtle. Let \(\lambda\) be the unique solution in \([ab]\) to the system \[\lambda \equiv 1 \bmod a, \;\; \lambda \equiv -1 \bmod b.\] The existence of \(\lambda\) is guaranteed by the Chinese remainder theorem. Furthermore, if \(\lambda = ka+1=c b -1\) then \(k\equiv c \bmod 2\) because \(a,b\) are odd. Observe that \(\lambda^2\equiv 1\bmod ab\). This means that \(x\mapsto \lambda x\) is an involution.

We separate the fixed points from the non-fixed points. We have the following useful characterization of fixed points: \[\lambda x \equiv x \bmod ab \iff \lambda \equiv 0 \bmod b.\] To conclude the proof, we will show that:

• Non-fixed points are sent to points with opposite color.
• Of the \(a\) fixed points, \(\left\lfloor a/2 \right\rfloor\) are color \(1\).

CLAIM 1: Let \(x\) be a non-fixed point, i.e., \(x\not\equiv 0\bmod b\). Then \(x\) and \(\lambda x\) have opposite color.

This is because \[\left\lfloor \lambda x / a \right\rfloor = \left\lfloor x(ka+1) / a \right\rfloor = kx+\left\lfloor x/a \right\rfloor.\] \[\left\lfloor \lambda x / b \right\rfloor = \left\lfloor x(cb-1) / b \right\rfloor = cx+\left\lfloor -x/b \right\rfloor.\] But, we showed before \(k\equiv c \bmod 2\). Thus, \[ \left\lfloor \lambda x / a \right\rfloor + \left\lfloor \lambda x / b \right\rfloor \equiv \left\lfloor x/a \right\rfloor+\left\lfloor -x/b \right\rfloor \not\equiv \left\lfloor x/a \right\rfloor + \left\lfloor x/b \right\rfloor \mod 2. \] CLAIM 2: Of the \(a\) fixed points, \(\left\lfloor a/2 \right\rfloor\) are color \(1\).

Let \(F = \left\{ b,2b,\ldots, (a-1)b\right\}\) denote the fixed points except for \(0\). We define a color flipping involution \(\phi: F\to F\) by \[yb \mapsto (a-y)b.\]

To see why this is color-flipping we compute: \[\left\lfloor \frac{yb}{a} \right\rfloor\oplus \left\lfloor \frac{yb}{b} \right\rfloor \equiv y \oplus \left\lfloor \frac{yb}{a} \right\rfloor \mod 2.\] \[\left\lfloor \frac{(a-y)b }{a} \right\rfloor\oplus \left\lfloor \frac{(a-y)b}{b} \right\rfloor \equiv y \oplus \left\lfloor \frac{-yb}{a} \right\rfloor \mod 2,\] and note that \[\left\lfloor \frac{-yb}{a} \right\rfloor \equiv 1\oplus \left\lfloor \frac{yb}{a} \right\rfloor\mod 2\] for \(y\in \left\{ 1,2,\ldots, b-1\right\}.\)