Friday, January 08, 2016

(Another) Solution: Writting year as sums of runs of numbers

The solution of just grinding out of the algebra is fine but it's a bit dull and unintuitive. We can use the discussion at the end of the last post to produce a simple proof with almost no algebra.

What we're going to prove is that the number of sequences of consecutive integers that sum to \(Y\) is equal to twice the number of odd divisors of \(Y\).

First off note that if the sum is positive, then there must be more positive numbers in the sequence than negatives. I'm going to assume it's positive, if it's negative then the procedure works, just with the signs changed.

Next, note that the solutions to the problem always come in pairs. Every sequence of even length has a corresponding sequence of odd length. You can construct one from the other as follows.

If 0 appears in the sequence then you cancel every negative number with it's opposite positive number and remove the zero. Every time you cancel a \(-\) with a \(+\) you remove 2 elements from the sequence, so it stays odd or even. Finally removing the 0 flips from odd to even or vice versa. E.g. $$ -3 + -2 + -1 + 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 $$ becomes $$ 4 + 5 + 6 + 7 $$ 2 slightly non-obvious cases of this are sequences beginning with 0 or 1. They have no negative elements, so you just either add or remove 0 at the start.

Conversely if the sequence does not contain 0, prepend all the numbers from 0 up to the start of the sequence and also prepend their negatives. This does not change the sum but it flips the length from even to odd or vice versa. E.g. $$ 4 + 5 + 6 + 7 $$ becomes $$ -3 + -2 + -1 + 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 $$

So now we just consider the solutions of odd length. If we can show that there is exactly one of those for every odd divisor of \(Y\), we're done. That turns out to be fairly easy.

First, lets say you have an odd length sequence that sums to \(Y\). Since it's odd-length, it must have a middle number, let's say \(n\) and then there are \(k\) numbers before and \(k\) numbers after. The befores and afters go together in pairs. \(n-1\) with \(n+1\), \(n-2\) with \(n+2\) etc. Each of these pairs sums to \(2n\) and there are \(k\) pairs plus a lone \(n\) from the middle giving a total of \((2k+1)n\). So we have that \(Y=(2k+1)d\) and so \(2k+1\) (the length of the sequence) must be an odd divisor of \(Y\). So this shows that any sequence that sums to Y leads to a specific odd divisor of Y.

Conversely given an odd divisor of \(Y\), \(2k+1\) and we set \(n = Y/(2k+1)\) then the sequence of length \(2k+1\) centred on on \(n\) sums to \(Y\). So every odd divisor leads to a sequence of odd-length and we're done.

No comments: