Question 2.6.24: There are 2000 towns in a country, each pair of which is lin......

We will prove the same statement for n ≥ 6 towns. First suppose n = 6. In this case there are 2^{15} assignments, and an assignment is rejected only if either one town has road to all of the others in the same direction, or if there are two sets of three towns, such that within each town the roads point in a circle, but all of the roads from one set to the other point in the same direction. There are 5 · 2^{11} bad assignments of the first kind and 20 · 8 of the second kind, so the fraction of good assignments is at least 5/8.

For n ≥ 6, we claim that the fraction of good assignments is at least

{\frac{5}{8}}\prod\limits_{i=6}^{n-1}\left(1-{\frac{1}{2^{i-1}}}\right).

We show this by induction on n: a good assignment on n − 1 vertices can be extended to a good assignment on n vertices simply by avoiding having all edges from the last vertex pointing in the same direction, which occurs in 2 cases out of 2^{n−1}.

Now it suffices to show that the above expression is more than 1/2. In fact,

\prod\limits_{i=5}^{\infty}\left(1-{\frac{1}{2^{i}}}\right)^{-1}\ \ \leq\ \ 1+\sum\limits_{i=5}^{\infty}{\frac{i~-~4}{2^{i}}}

   \begin{array}{r l}{={}}&{{}1+{\frac{1}{2^{5}}}\sum\limits_{i=0}^{\infty}{\frac{i~+~1}{2^{i}}}}\end{array}

   \begin{array}{r l}{={}}&{{}1+{\cfrac{1}{2^{5}}}\sum\limits_{i=0}^{\infty}\sum\limits_{k=i}^{\infty}{\frac{1}{2^{i}}}}\end{array}

   \begin{array}{r l}{={}}&{{}1+{\frac{1}{2^{5}}}\sum\limits_{i=0}^{\infty}{\frac{1}{2^{i-1}}}}\end{array}

    =\quad1+\frac{4}{2^{5}}=\frac{9}{8}

Thus the fraction of good assignments is at least (5/8)(8/9) = 5/9 > 1/2.