HMMT 二月 2010 · 冲刺赛 · 第 23 题

HMMT February 2010 — Guts Round — Problem 23

[ 12 ] In the country of Francisca, there are 2010 cities, some of which are connected by roads. Between any two cities, there is a unique path which runs along the roads and which does not pass through any city twice. What is the maximum possible number of cities in Francisca which have at least 3 roads running out of them? 2 2

解析

[ 12 ] In the country of Francisca, there are 2010 cities, some of which are connected by roads. Between any two cities, there is a unique path which runs along the roads and which does not pass through any city twice. What is the maximum possible number of cities in Francisca which have at least 3 roads running out of them? Answer: 1004 The restrictions on how roads connect cities directly imply that the graph of the cities of Francisca with the roads as edges is a tree. Therefore the sum of the degrees of all the vertices is 2009 · 2 = 4018. Suppose that b vertices have degree ≥ 3. The other 2010 − b vertices must have a degree of at least 1, so 3 b + (2010 − b ) ≤ 4018 or 2 b ≤ 2008. So b is at most 1004. We can achieve b = 1004 with the following graph: · · · 2 2