Will the following do as a proof? Just look! Draw a rectangle with 2n rows and n columns, Area 2n^2. In each column i (1 \leq i \leq n) draw two lines at levels a_i, b_i, so that there is just one line at every level from 1 to 2n. Then the answer is the area between the n pairs, i.e. the total area, 2n^2, minus the area above the higher lines, 0+1+2+...+(n-1) and the area below the lower lines, 1+2+3+...+n. 2n^2 - n^2 = n^2. P'raps this has already been said (more than once?) R. On Sun, 24 Aug 2014, James Propp wrote:
I know an argument which I think is different from the other two. It shows that the value of the sum in question is the same regardless of how you split 1,2,...,2n into two sets of size n, but doesn't compute what that value is (though it's easy to compute it via a separate argument, using the odd-even split or the low-high split). You just need to show that if you swap two adjacent integers between the two sets, the value of the sum doesn't change; and that you can get from any split to any other via moves of this kind.
This isn't what the OP asked for, but I find this approach very handy for many sorts of combinatorial problems.
Jim Propp
On Sunday, August 24, 2014, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 24/08/2014 12:50, J.P. Grossman wrote:
I'm not sure what you mean by "bijective", but if you graph the two sequences then they form an X pattern. The numbers in the upper branches are always {n+1, ..., 2n} in some order, and the numbers in the lower branches are always {1, ..., n} in some order, so the sum |a_i - b_i| is always (n+1 + n+2 + ... + 2n) - (1 + 2 + ... + n) = n^2
More formally, [...]
Yes, this is basically the same as one of the proofs on the cut-the-knot page I linked to. It's not bad, but not quite what I was hoping for.
By "bijective" I mean: We're trying to prove that one positive integer equals another. Perhaps there's a proof that makes it obvious that each of them is the size of some set, and exhibits a bijection between the two sets.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun