Harvard-MIT Mathematics Tournament #0icv

Harvard-MIT Mathematics TournamentHard

Community difficultyNo ratings yetBe the first to rate this problem.

Understand the scale

Scale 0.5: Easiest math competition problems, often solvable even for early middle school students without experience. 1: Problems strictly for beginners, often at a moderate middle school level. 1.5: Problems for stronger beginner students, on the level of the middling problems in most middle school contests. 2: For motivated beginners, harder questions from the previous categories. 2.5: More advanced beginner problems, hardest questions from previous categories. 3: Early intermediate problems that require more creative thinking. 3.5: Tougher early intermediate problems that consistently stretch into higher-level creative thinking or conceptual knowledge. 4: Intermediate-level problems. 4.5: Upper intermediate problems approaching the upper bound for non-invitational sprint math competitions. 5: More difficult AIME problems or simple proof-based Olympiad-style problems. 6: High-level AIME-styled questions or introductory Olympiad-level questions. 7: Tougher Olympiad-level questions, may require more technical knowledge. 8: High-level Olympiad-level questions. 9: Expert Olympiad-level questions. 9.5: The hardest problems appearing on Olympiads which the strongest students could reasonably solve. 10: Historically notorious problems, generally unsuitable for even very hard competitions because they are exceedingly tedious, long, and difficult.

Problem

Problem: You would like to provide airline service to the 10 cities in the nation of Schizophrenia, by instituting a certain number of two-way routes between cities. Unfortunately, the government is about to divide Schizophrenia into two warring countries of five cities each, and you don't know which cities will be in each new country. All airplane service between the two new countries will be discontinued. However, you want to make sure that you set up your routes so that, for any two cities in the same new country, it will be possible to get from one city to the other (without leaving the country). What is the minimum number of routes you must set up to be assured of doing this, no matter how the government divides up the country?