The Country Of Brilliant

Discrete Mathematics 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.


Problem Loading...

Note Loading...

Set Loading...