What Are the Conditions for This Putnam Problem's Sum to Equal Zero?

[Ackbach]

Here is this week's POTW:

-----

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.\]

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 246 - Dec 27, 2016

This was Problem B-4 in the 1998 William Lowell Putnam Mathematical Competition.

Congratulations to Opalg for his correct solution, which follows. Honorable mention to Joppy for a good attempt.

Spoiler

Let $S(m,n) = \sum_{i=0}^{mn-1} (-1)^{\lfloor i/m \rfloor +\lfloor i/n\rfloor}$. The sum $S(m,n)$ consists of $mn$ terms, each of which is $\pm1$. If $m$ and $n$ are both odd, then there is an odd number of terms. In that case, the number of $+1$s in the sum cannot be the same as the number of $-1$s. So they cannot cancel out, and there is no possibility that $S(m,n) = 0.$

Now suppose that one of $m,n$ is even and the other one is odd. Let $j = mn-1-i$. Then $\dfrac jm = \dfrac{mn-m + (m-1-i)}m = n-1 + \dfrac{m-1-i}m.$

Since $-\bigl\lfloor\frac st \bigr\rfloor= \bigl\lfloor\frac {t-1-s}t \bigr\rfloor$ (for all natural numbers $s,t$), it follows that $$\Bigl\lfloor \frac jm \Bigr\rfloor = n-1 + \Bigl\lfloor \frac {m-1-i}m \Bigr\rfloor = n-1 -\Bigl\lfloor \frac I am \Bigr\rfloor.$$ In a similar way, $$\Bigl\lfloor \frac jn \Bigr\rfloor = m-1 -\Bigl\lfloor \frac in \Bigr\rfloor.$$ Therefore $$\Bigl\lfloor \frac jm \Bigr\rfloor + \Bigl\lfloor \frac jn \Bigr\rfloor = m+n-2 - \Bigl(\Bigl\lfloor \frac I am \Bigr\rfloor + \Bigl\lfloor \frac in \Bigr\rfloor\Bigr).$$ Since $m+n$ is odd, it follows that if $\bigl\lfloor \frac I am \bigr\rfloor + \bigl\lfloor \frac in \bigr\rfloor$ is even then $\bigl\lfloor \frac jm \bigr\rfloor + \bigl\lfloor \frac jn \bigr\rfloor$ is odd, and vice versa. Thus the $j$-term in the sum $S(m,n)$ will be the negative of the $i$-term. So each term in the first half of the sum will cancel with a term in the second half, and $S(m,n)$ will be $0$.

Finally, what happens if $m$ and $n$ are both even, say $m=2p$ and $n=2q$? Then $\frac{2i+1}m = \frac ip + \frac i{2p}$, so that $\bigl\lfloor \frac{2i+1}m \bigr\rfloor = \bigl\lfloor \frac ip \bigr\rfloor = \bigl\lfloor \frac{2i}m \bigr\rfloor.$ Similarly $\bigl\lfloor \frac{2i+1}n \bigr\rfloor = \bigl\lfloor \frac{2i}n \bigr\rfloor.$ So each consecutive pair of terms in the sum $S(m,n)$ are the same as the corresponding term in the sum $S(p,q),$ and therefore $S(m,n) = 2S(p,q).$ Thus $S(m,n) = 0$ if one of $p,q$ is odd, but $S(m,n) \ne0$ if they are both odd. If they are both even, then we have to repeat this process of "dividing by 2" until one or both of the resulting numbers is odd. In this way you see that a necessary and sufficient condition for $S(m,n) = 0$ is that the power of $2$ in (the prime factorisation of) $m$ should be different from the power of $2$ in $n$.

Another way to state that necessary and sufficient condition for $S(m,n) = 0$ is this: if $d$ is the greatest common divisor of $m$ and $n$ then $\dfrac{mn}{d^2}$ is an even number.