HMMT 二月 2017 · 冲刺赛 · 第 22 题
HMMT February 2017 — Guts Round — Problem 22
题目详情
英文原题
- [ 12 ] Kelvin the Frog and 10 of his relatives are at a party. Every pair of frogs is either friendly orunfriendly . When 3 pairwise friendly frogs meet up, they will gossip about one another and end up in a fight (but stay friendly anyway). When 3 pairwise unfriendly frogs meet up, they will also end up
( )
in a fight . In all other cases, common ground is found and there is no fight. If all triples of frogs 11
meet up exactly once, what is the minimum possible number of fights?3
解析
英文解析
- [ 12 ] Kelvin the Frog and 10 of his relatives are at a party. Every pair of frogs is either friendly orunfriendly . When 3 pairwise friendly frogs meet up, they will gossip about one another and end up in a fight (but stay friendly anyway). When 3 pairwise unfriendly frogs meet up, they will also end up
( )
in a fight . In all other cases, common ground is found and there is no fight. If all triples of frogs 11
meet up exactly once, what is the minimum possible number of fights?3
Proposed by: Alexander Katz
Answer: 28
Consider a graph G with 11 vertices – one for each of the frogs at the party – where two vertices areconnected by an edge if and only if they are friendly. Denote by d ( v ) the number of edges emanatingfrom v ; i.e. the number of friends frog v has. Note that d (1) + d (2) + . . . + d (11) = 2 e , where e is the number of edges in this graph.
Focus on a single vertex v , and choose two other vertices u, w such that uv is an edge but wv is not.
There are then d ( v ) choices for u and 10 − d ( v ) choices for w , so there are d ( v )(10 − d ( v )) sets of threefrogs that include v and do not result in a fight. Each set, however, is counted twice – if uw is an edge,
then we count this set both when we focus on v and when we focus on w , and otherwise we count itwhen we focus on v and when we focus on u . As such, there are a total of
∑
d ( v )(10 − d ( v ))1
v 2
sets of 3 frogs that do not result in a fight.
√
d ( v )+10 − d ( v )
Note that = 5 ≥ d ( v )(10 − d ( v )) = ⇒ d ( v )(10 − d ( v )) ≤ 25 by AM-GM. Thus there area maximum of 2
∑
1 1 275
d ( v )(10 − d ( v )) ≤ (25 · 11) =
2 2 2
sets of three frogs that do not result in a fight; since this number must be an integer, there are av
( )
maximum of 137 such sets. As there are a total of = 165 sets of 3 frogs, this results in a minimum 11
165 − 137 = 28 number of fights.3
It remains to show that such an arrangement can be constructed. Set d (1) = d (2) = . . . = d (10) = 5
and d (11) = 4. Arrange these in a circle, and connect each to the nearest two clockwise neighbors; thisgives each vertex 4 edges. To get the final edge for the first ten vertices, connect 1 to 10, 2 to 9, 3 to
8, 4 to 7, and 5 to 6. Thus 28 is constructable, and is thus the true minimum.