HMMT 十一月 2016 · 冲刺赛 · 第 24 题

英文解析

24. [ 12 ] Consider an infinite grid of equilateral triangles. Each edge (that is, each side of a small triangle)
    is colored one of N colors. The coloring is done in such a way that any path between any two nonadjecent vertices consists of edges with at least two different colors. What is the smallest possible valueof N ?
    Proposed by: Henrik Boecken
    Answer: 6
    Note that the condition is equivalent to having no edges of the same color sharing a vertex by justconsidering paths of length two. Consider a hexagon made out of six triangles. Six edges meet at the center, so N ≥ 6. To prove N = 6, simply use two colors for each of the three possible directions of anedge, and color edges of the same orientation alternatingly with different colors.