A question about tournaments containing Hamilton paths

Question

I need to show that there exists a tournament of n vertices $n\ge3$ that has more than $\frac{n!}{2^{n-1}}$ Hamiltonian paths

Can I try to show that with induction? I'm not so sure how to start with $n=3$ Can anyone give a hint?

Thanks

I have tried something else but not sure it's right I have said that I need to show that the probability of that case must be greater than zero meaning its completion should be less that one which is right because not all tournaments contain at most $\frac{n!}{2^{n-1}}$ because we have shown that there exists (a tournament) with at least $\frac{n!}{2^{n-1}}$ Is that even right?

which way is recommended the induction or trying to fix the second way?

Answer 1

HINT:

1. Assign each edge $e$ in $K_n$ a direction, where each edge is assigned a direction mutually independently of the directions assigned to the other edges in $K_n$, and either direction is assigned to $e$ with probability $\frac{1}{2}$.

2. Let $x_1,x_2, \ldots, x_n$ be an ordering of $V(G)$. Then the probability that $x_1x_2,\ldots x_n$ form a Hamiltonian path [in that order] in the tournament as prescribed in 1. above is $2^{-(n-1)}$. [Indeed, each of the $n-1$ edges $\{x_i,x_{i+1}\}$ has to be oriented from $x_i$ to $x_{i+1}$.]

3. There are $n!$ such orderings as in 2. above. Conclude that the expected number of Hamiltonian paths in the tournament, as constructed in 1. above, is then $n! \times 2^{-(n-1)}$. Thus, there has to be at least one tournament with that many Hamiltonian paths.