HMMT 二月 2003 · 冲刺赛 · 第 17 题

HMMT February 2003 — Guts Round — Problem 17

[8] There are 10 cities in a state, and some pairs of cities are connected by roads. There are 40 roads altogether. A city is called a “hub” if it is directly connected to every other city. What is the largest possible number of hubs?

解析

There are 10 cities in a state, and some pairs of cities are connected by roads. There are 40 roads altogether. A city is called a “hub” if it is directly connected to every other city. What is the largest possible number of hubs? Solution: 6 ( ) h If there are h hubs, then roads connect the hubs to each other, and each hub is 2 ( ) h connected to the other 10 − h cities; we thus get + h (10 − h ) distinct roads. So, 2 ( ) h 2 40 ≥ + h (10 − h ) = − h / 2+19 h/ 2 , or 80 ≥ h (19 − h ). The largest h ≤ 10 satisfying 2 this condition is h = 6, and conversely, if we connect each of 6 cities to every other ( ) 6 city and place the remaining 40 − [ + 6(10 − 6)] = 1 road wherever we wish, we can 2 achieve 6 hubs. So 6 is the answer.