What about this approach: Suppose

Though is not necessarily a subgroup, it does contain the identity and inverses by the automorphism properties, i.e. if is the identity and , . Then in particular , and the set of fixed points of does form a subgroup. Since this subgroup contains more than half of the elements it follows that for all elements of the group.

If we can somehow show that in fact , we are done.