I guess this approach might work:

Let be the set of allevenpermutations of . Now if the proof is complete. Otherwise there exists a non-empty set of odd permutations .

Now you define a one-to-one onto map .

Define for .

This shows that thus there are exactly one half even permutations and one half odd permutations.