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.