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. Betweenany two cities, there is a unique path which runs along the roads and which does not pass through anycity twice. What is the maximum possible number of cities in Francisca which have at least 3 roadsrunning out of them?
2 2
解析
英文解析
- [ 12 ] In the country of Francisca, there are 2010 cities, some of which are connected by roads. Betweenany two cities, there is a unique path which runs along the roads and which does not pass through anycity twice. What is the maximum possible number of cities in Francisca which have at least 3 roadsrunning out of them?
Answer: 1004 The restrictions on how roads connect cities directly imply that the graph of thecities of Francisca with the roads as edges is a tree. Therefore the sum of the degrees of all the verticesis 2009 · 2 = 4018. Suppose that b vertices have degree ≥ 3. The other 2010 − b vertices must have adegree of at least 1, so 3 b + (2010 − b ) ≤ 4018 or 2 b ≤ 2008. So b is at most 1004. We can achieveb = 1004 with the following graph:
· · ·
2 2