I guess this approach might work:
Let be the set of all even permutations 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.