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

HMMT February 2005 — Guts Round — Problem 9

[6] 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 or between two rabbits. If there are 600 ducks, what is the least number of cows there can be for this to be possible? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, FEBRUARY 19, 2005 — GUTS ROUND

解析

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 or between two rabbits. If there are 600 ducks, what is the least number of cows there can 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 be served by two rabbits, but we cannot have equality, since this would require alternating between rabbits and ducks all the way around the circle, contradicting the fact that more 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.