Problem #PRU-5095

Problems Combinatorics

Problem

There are \(33\) cities in the Republic of Farfarawayland. The delegation of senators wants to pick a new capital city. They want this city to be connected by roads to every other city in the Republic. They know for a fact that given any set of \(16\) cities, there will always be some city that is connected by roads to all those selected cities. Show that there exists a suitable candidate for the capital.