Speaking of "bijective proofs", I'd like to bring up something that Jim (Propp) once mentioned I think on math-fun: For any finite set X, it's easy to show that it has the same number of odd-sized subsets as of even-sized subsets. But there doesn't seem to be a natural bijection between them. (In fact the standard proof is this: pick any element x of X. Then for any subset not including x, add it; for any subset including x, remove it.) What I'd like to know is, Is there a proof of the nonexistence of a "natural" bijection here? (Something like a proof that any bijection requires the use of the finite Axiom of Choice. Or maybe this can be expressed as the nonexistence of some kind of functor from the category of finite sets to the category of finite bijections.) --Dan On Aug 23, 2014, at 6: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