Intuitively, why must a group of order $2n$ ($n$ is odd) have a subgroup of order $n$? I have seen a proof of the following fact:

If $G$ is a group of order $2n$, where $n$ is odd, then $G$ has a subgroup of order $n$.

We consider $G$ as a subgroup of $S_{2n}$, and prove that $G \cap A_{2n}$ has index $2$ in $G$.
However, I can't wrap my head around the situation. Can someone provide some intuition? What, essentially, is it that forces $G$ to have a subgroup of order $n$?
 A: Let me give you some generalization of the fact you mentioned,
Let $P\in Syl_p(G)$ be cyclic where $p$ is the smallest prime dividing the order of $G$. Then $G$ is $p$-nilpotent ($G$ has normal Hall $p'$-subgroup).
The reason that why this is true simply is that when $p$ is the smallest prime one can easily show that $N_G(P)=C_G(P)$.
This causes that the transfer map from $G$ to $P$ is an onto homomorphism. Now the case $|P|=2$ is a special case of it and it can be proven in an elemantary way.
But in big picture, it is always true that for an abelian Sylow $p$ subgroup $P$ if $N_G(P)=C_G(P)$, then $G$ is $p$-nilpotent due to the fact that there is an onto homomorphism from $G$ to $P$.
Now you may ask the intuition of these facts. If you are familiar with transfer theory, it is easy to see why $N_G(P)=C_G(P)$ causes so many nice results. Note that these results are due to Burnside.
A: Let $H = G\cap A_{2n}$.

Since $G$ has even order, $G$ has an element of order $2$, $f$ say.

As an element of $S_{2n}$, if $f$ has a fixed point, $x$ say, then $fx=x \implies f=1$, contrary to $o(f)=2$.

Hence $f$, as an element of $S_{2n}$ has no fixed points.

Since $f$ has order $2$, the disjoint cycle representation of $f$ consists of a product of disjoint transpositions, and since $f$ has no fixed points, the number such transpositions must be exactly $n$. Then, since $n$ is odd, $f$ is an odd permutation. It follows that 
$f \notin H$.

Thus, $H$ is a proper subgroup of $G$.

Let $J = G \setminus H$.

Since  all elements of $J$ are odd, it follows that all elements of $fJ$ are even, hence $fJ \subseteq H$, which implies $|J| \le |H|$.

Since  all elements of $H$ are even, it follows that all elements of $fH$ are odd, hence $fH \subseteq J$, which implies $|H| \le |J|$.

Thus, $|J|=|H|$, and hence, $H$ has index $2$ in $G$, as was to be shown.

Some motivation for the "discovery" . . .

The idea is that if all elements of $G$ are even permutations, then $G = H$, and $H$ would have index $1$, not $2$ (and then the theorem would be false).

So we need to find an element of $G$ which, as an element of $S_{2n}$, is an odd permutation.

Now, any square of an element of $S_{2n}$ is automatically even, so in looking for our odd permutation, we don't want squares.

But any element of odd order is already a square in its own cyclic subgroup, so forget about using elements of odd order.

Thus, to find an element of $G$ which is an odd permutation, the only candidates are elements of even order.

But how to bring the oddness of $n$ into play?

The next idea is consider an element of order $2$.

Without trying it, it may not be so obvious that it will yield an odd permutation, but it's worth a try. 

For one thing, we know that such an element exists.

Also an element order $2$ has a simple disjoint cycle representation (it must be a product of disjoint transpositions), hence the evenness or oddness of such an element will be known if we can determine the evenness or oddness of the number of disjoint transpositions.

But then there's a trick (a reusable trick) . . .

In the permutation representation of a group by left multiplication, all permutations are fixed-point free, except for the identity.

To be fixed-point free, the disjoint transpositions must "fill up" all of the $2n$ positions, hence there must be exactly $n$ of them! And $n$ is odd!

Voila!

There's the Aha! of discovery mode (at least that's what I said when it hit me!). 

Of course, there's a little more to do$\,-\,$comparing the cardinalities of $J$ and $H$, but already, at this point, the problem is "broken", and won't be able to fight back with much conviction (it might as well just give up).
A: Maybe the easiest explanation is that when we use the Cayley embedding of $G$ into $S_{2n}$ (coming from the action on itself by right translation) an element $t$ of order $2$ in $G$ is represented as a product of $n$ $2$-cycles. Since $n$ is odd, $t$ is represented as an odd permutation. Hence the elements which map to even permutations in the Cayley embedding form a proper subgroup of $G$ of index $2$.
