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, let a_i be the increasing sequence, let b_i be the decreasing sequence, and let k be the largest integer for which a_k < b_k (take k = 0 if a_1 > b_1). Then the branches of the X pattern are {a_1, ..., a_k}, {a_{k+1}, ..., a_n}, {b_1, ..., b_k}, {b_{k+1}, ..., b_n}. At the center we have: a_k < b_k, b_{k+1} < a_{k+1} (by choice of k) a_k < a_{k+1}, b_{k+1} < b_k (by monotonicity of a_i, b_i) Together with the monotonicity of the branches, this implies that every integer in the lower branches is smaller than every integer in the upper branches, from which the above assertion follows. J.P. On Sat, Aug 23, 2014 at 9:24 PM, Gareth McCaughan < gareth.mccaughan@pobox.com> wrote:
A recent post on the (excellent) blog "Futility Closet" http://www.futilitycloset.com/2014/08/21/proizvolovs-identity/ cites without proof the following theorem:
Take the numbers 1..2n. Divide them into two subsets of size n. Write one in ascending order and the other in descending order. Then the sum of |a_i-b_i| is always n^2.
This isn't difficult to prove, but the proof I found not-difficult to find isn't terribly elegant. Is there a neat "bijective" proof?
(There are two proofs at http://www.cut-the-knot.org/Curriculum/Games/ProizvolovGame.shtml neither of which seems very elegant to me. Both are better than my proof, which proceeds by induction on n.)
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun