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

  • Thread starter Thread starter Ackbach
  • Start date Start date
  • Tags Tags
    2016
Click For Summary
SUMMARY

The discussion centers on finding necessary and sufficient conditions for positive integers \(m\) and \(n\) such that the sum \(\sum_{i=0}^{mn-1} (-1)^{\lfloor i/m \rfloor +\lfloor i/n\rfloor}=0\) holds true. This problem, identified as Problem B-4 from the 1998 William Lowell Putnam Mathematical Competition, was successfully solved by user Opalg, while user Joppy received honorable mention for their attempt. The conditions derived from the solution are critical for understanding the behavior of this alternating sum.

PREREQUISITES
  • Understanding of floor functions and their properties
  • Familiarity with alternating series and their convergence
  • Basic knowledge of combinatorial mathematics
  • Experience with mathematical competition problems
NEXT STEPS
  • Research the properties of floor functions in number theory
  • Explore techniques for solving alternating series
  • Study combinatorial identities relevant to the Putnam competition
  • Examine previous Putnam problems for similar patterns and solutions
USEFUL FOR

Mathematics students, competitive problem solvers, and educators interested in advanced combinatorial techniques and mathematical competitions will benefit from this discussion.

Ackbach
Gold Member
MHB
Messages
4,148
Reaction score
94
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!
 
Physics news on Phys.org
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.

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.
 

Similar threads

  • · Replies 1 ·
Replies
1
Views
1K
Replies
1
Views
1K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 1 ·
Replies
1
Views
2K