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

英文解析

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