/sci/ - Science & Math

Previous Thread >>10523587

>>10526643
Obviously mn must be even

>>10527141
Let f(m,n) be the sum.
If m and n are coprime then f(km,kn) = (k^2)f(m,n).
If you can solve it for coprime m,n then you can solve it for all pairs.

I believe it is both necessary and sufficient to say that the number of 2s in the prime factorization of n and m are not equal.

>>10527244
I this is definitely necessary.
I'm still trying to figure out the sufficient part.

>>10527281
My somewhat informal thought process as follows.

If one of n,m is odd and one is even it must be true, consider the two sequences S(n) and S(m) defined by S(n)_k = floor(k/n) mod 2. We take mod 2 because only the parity matters. You will notice that if m is odd S(n)_k is symmetric, meaning S(n)_k = S(n)_(mn-1-k). If m is even S(n)_k is "antisymmetric", meaning S(n)_k = 1-S(n)_(mn-1-k). From this it is not hard to see that in such a case if you take the sequence of parities of each term up to i = (mn/2 - 1), the opposite parities will be repeated (in reverse order) through the second half of the sequence.

If n, m are both odd this obviously does not hold.

If n, m are both even, both sequences are antisymmetric so the partial sum at the halfway point will be half the total sum, meaning the condition can only hold if the partial sum at the halfway point is 0 which is itself equivalent to saying that the condition also holds for n/2, m/2.

>>10527318
To avoid the "jumps" of the floor, I rewrote f(m,n) using floor((i+1/2)/m) and floor((i+1/2)/n).
This doesn't change f at all.
Split the sum into two parts:
i from 0 to mn/2 -1
i from mn/2 to mn-1

Let i = mn-1-j in the second sum to make the bounds of j and the first i match.

The terms for j are (-1)^[m+n+floor(-(j+1/2)/m)+floor(-(j+1/2)/n)]

m+n is odd so you can make the term:
-(-1)^[floor(-(j+1/2)/m)+floor(-(j+1/2)/n)]

since the floors avoid integers, you can use the "identity":
floor(-x) = -1 - floor(x) for non-integer x.

This makes the j terms:
-(-1)^[-floor((j+1/2)/m)-floor((j+1/2)/n)-2]
which is equal to:
-(-1)^[floor((j+1/2)/m)+floor((j+1/2)/n)]
which are the negative of the i terms.

It's basically the same antisymmetry argument.

>>10527756
Ah fuck just spotted the floors. Why are Putnam problems almost never based?

maybe using [math]x - 1 < [x] < x + 1[/math] and >>10527756 ???