Prove that for any positive integers $a$ and $b$ we have $$a+(-1)^b \sum^a_{m=0} (-1)^{\lfloor{\frac{bm}{a}\rfloor}} \equiv b+(-1)^a \sum^b_{n=0} (-1)^{\lfloor{\frac{an}{b}\rfloor}} \pmod{4}.$$
Problem
Source: India TST 2017 D3 P3
Tags: number theory, combinatorics
Kayak
09.12.2017 17:13
This was the legendary Biomathematician's RMO (yep, RMO, not even INMO) mock P5.
(I wonder which problems will appear in his INMO mock then ... )
ThE-dArK-lOrD
09.12.2017 19:12
Consider all lattice points with non-negative coordinates under the graph $y=\frac{b}{a}x$.
For each such point with coordinate $(i,j)$ we denote its value to be $(-1)^{j+1}$.
For each $m\in \{ 0,1,2,\dotsc ,a\}$ we get that the sum of values of all such points with $x$-coordinate equal to $m$ is equal to $$S_m=\begin{cases}
0, & \text{if } \lfloor bm/a\rfloor \equiv 0\pmod{2}\\
-1, & \text{if } \lfloor bm/a \rfloor \equiv 1\pmod{2} \end{cases}.$$Easy to see that $(-1)^{\lfloor bm/a\rfloor}$ is equal to $2S_m+1$. Hence, $LHS=a+(-1)^b\cdot \left( a+1+2\sum_{m=0}^{a}{S_m}\right)$.
Now, we will compute $\sum_{m=0}^{a}{S_m}$.
For each $n\in \{ 0,1,2,\dotsc ,b\}$, the sum of values of all such points with $y$-coordinate equal to $n$ is equal to $$(-1)^{n+1}\cdot \left( a-\left\lceil an/b\right\rceil +1\right).$$Thus we have
\begin{align*}
\sum_{m=0}^{n}{S_m} & =\sum_{n=0}^{b}{(-1)^{n+1}\cdot ( a-\left\lceil an/b \right\rceil +1) }\\
& =(a+1)\sum_{n=0}^{b}{(-1)^n} -\sum_{n=0}^{b}{\lceil an/b\rceil (-1)^{n+1}} .
\end{align*}
We can now simplify $LHS$ to $-1-2(-1)^b\sum_{n=0}^{b}{\lceil an/b \rceil (-1)^{n+1}} $.
Similarly, $RHS$ is equal to $-1-2(-1)^a\sum_{m=0}^{a}{\lceil bm/a\rceil (-1)^{m+1}} $.
So, now we need to show that $(-1)^b\sum_{n=0}^{b}{\lceil an/b\rceil (-1)^{n+1}} \equiv (-1)^a\sum_{m=0}^{a}{\lceil bm/a \rceil (-1)^{m+1}} \pmod{2}$.
Denote the points $O(0,0),P(a,b),U(a,0),V(0,b)$.
Let $r$ be the number of lattice point on the line $y=\frac{b}{a}x$ when $1\leqslant x\leqslant a-1$.
The number of lattice point in the interior of triangle $OUP$ is equal to $$\sum_{n=1}^{b-1}{( \lceil bn/a \rceil -1) } -r:=H_b-(b-1)-r.$$The number of lattice point in the interior of triangle $OVP$ is equal to $$\sum_{m=1}^{a-1}{( \lceil am/b \rceil -1) }-r:=H_a-(a-1)-r.$$By Pick's theorem, with the fact that the area and the number of lattice points on the boundary of two triangles are equal, we get that $$H_b-b=H_a-a.$$The modulo relation we want to prove is equivalent to $$-a+(-1)^bH_b\equiv -b+(-1)^aH_a\pmod{2}.$$This is true since $$LHS \equiv -a+H_b=-a+(H_a+b-a)\equiv b+H_a\equiv -b+H_a\equiv RHS \pmod{2}.\quad \blacksquare$$