Hamiltoncykler i riktad graf

Jag har fastnat på den här uppgiften.

Antalet potentiella hamiltoncykler i K_n tänker jag ges av antalet permutationer av [n], justerat för n sätt att rotera cykeln: $\frac{n!}{n}= (n-1)!$

För att en sådan permutation ska vara en hamiltoncykel krävs att alla n noder har samma riktning. Om vi har en slumpmässig K_n så blir sannolikheten för detta $2^{-(n-1)}$, eftersom den första kanten kan ha vilken riktning som helst och resterande (n-1) kanter måste ha samma.

Väntevärdet på antalet hamiltoncykler blir då:

$(n-1)!·2^{-(n-1)}$

Utifrån detta vet jag inte hur man visar att det finns en turnering med åtminstone $n!2^{-n}$ hamiltoncykler.