The Country Of Brilliant

Probability Level 5

The country of Brilliant has $2015$ towns. Some pairs of towns are connected via two-way railroads. No town is connected to itself.

A set $S= \{a_1, a_2, \cdots , a_n\}$ of towns is called good if $|S|= n>2$ is even, and $a_2$ is connected to $a_1$ , $a_3$ is connected to $a_2$ , $\cdots$ , $a_n$ is connected to $a_{n-1}$ and $a_1$ is connected to $a_n$ (note that connectivity is mutual, i.e. if $x$ is connected to $y$ , $y$ is connected to $x$ ). In other words, a good set is a cycle containing an even number of vertices.

There are a total of $m$ railroads in the country. Find the smallest value of $m$ such that no matter how the railroads are connected, given that there are a total of $m$ railroads, there must always exist a good set of cities.

Details and assumptions - All railroads are distinct, i.e. no two railroads connect the same pair of cities. - No railroad connects a city to itself. - This problem is not original.

The answer is 3022.

1 solution

Adit Mohan
Apr 30, 2015

We need the smallest m that will force us to make an even cycle. with m smaller than the required answer we must be able to make free lines or cycles which do not have a common edge.
In other words we have to be forced to draw two odd cycles with a common edge.
The most efficient odd cycle will be a triangle , if this is not already evident it will become clearer as the solution progresses.
For the first triangle we make we will need to incorporate three vertices. For subsequent triangles we will need to incorporate at least two vertices. Hence number of triangles we can form without running out of vertices is.
1007 (floor 2015/2).
No of lines drawn = 1007*3=3021.
When we draw another line(track) we will create an even cycle.
Thus answer =3021+1=3022

As opposed to claiming that "the most efficient odd cycle will be a triangle", what you need to do is:

Show that there is a graph with 3021 edges with no even cycle. This has been implicitly done.
Show that any graph with 3022 edges must have an even cycle. This has not been done.

Calvin Lin Staff - 6 years, 1 month ago

The Country Of Brilliant

The answer is 3022.

1 solution

0 pending reports