HMMT 二月 2005 · 冲刺赛 · 第 9 题

英文解析

9. Farmer Bill’s 1000 animals — ducks, cows, and rabbits — are standing in a circle.
   In order to feel safe, every duck must either be standing next to at least one cow orbetween two rabbits. If there are 600 ducks, what is the least number of cows therecan be for this to be possible?
   Solution: 201
   Suppose Bill has r rabbits and c cows. At most r − 1 ducks can be between two rabbits:
   each rabbit can serve up to two such ducks, so at most 2 r/ 2 = r ducks will each beserved by two rabbits, but we cannot have equality, since this would require alternatingbetween rabbits and ducks all the way around the circle, contradicting the fact thatmore than half the animals are ducks. Also, at most 2 c ducks can each be adjacent to a cow. So we need 600 ≤ r − 1 + 2 c = (400 − c ) − 1 + 2 c , giving c ≥ 201. Conversely,
   an arrangement with 201 cows is possible:
   RDRDR · · · DR DCD DCD DCD · · · DCD .
   ︸ ︷︷ ︸ ︸ ︷︷ ︸
   199 R, 198 D 201 C, 402 D
   So 201 is the answer.