MathDB

Problem 1 of Fourth round - Airline companies

Source: VII International Festival of Young Mathematicians Sozopol 2016, Theme for 10-12 grade

September 3, 2019

combinatoricsgraph

Problem Statement

There are

2^{2n+1}

towns with

2n+1

companies and each two towns are connected with airlines from one of the companies. What’s the greatest number

k

with the following property: We can close

k

of the companies and their airlines in such way that we can still reach each town from any other (connected graph).