MathDB

7

Part of 2020 Saint Petersburg Mathematical Olympiad

Problems(1)

Some oligarchs want to create a corporate

Source: Saint Petersburg MO 2020 Grade 11 Problem 7

5/7/2020
NN oligarchs built a country with NN 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 11 (note that there can be more than 11 road going through two cities, but they would belong to different oligarchs). A total of dd 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 NN oligarchs can create a corporation. What is the maximal amount that dd can have?
combinatorics