2014 towns? 1402 roads?

Probability Level 5

There are 2014 towns in a country, each of which is connected with at least 1402 towns by a direct road. Find the largest integer $n$ such that it must be possible to find $n$ towns, any two which are connected by a direct road.

The answer is 4.

1 solution

Emmanuel Lasker
Jan 6, 2015

I used Turàn's theorem for $2014$ vertices and $\frac{1402\cdot2104}{2}$ edges (i.e. the minimum number of edges possible). Solving for $n$ leads to $n=\boxed{4}$

2014 towns? 1402 roads?

The answer is 4.

1 solution

0 pending reports