Some oligarchs want to create a corporate
Source: Saint Petersburg MO 2020 Grade 11 Problem 7
May 7, 2020
combinatorics
Problem Statement
oligarchs built a country with cities with each one of them owning one city. In addition, each oligarch built some roads such that the maximal amount of roads an oligarch can build between two cities is (note that there can be more than road going through two cities, but they would belong to different oligarchs).
A total of roads were built. Some oligarchs wanted to create a corporation by combining their cities and roads so that from any city of the corporation you can go to any city of the corporation using only corporation roads (roads can go to other cities outside corporation) but it turned out that no group of less than oligarchs can create a corporation. What is the maximal amount that can have?