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

HMMT November 2016 — Guts Round — Problem 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 non- adjecent vertices consists of edges with at least two different colors. What is the smallest possible value of N ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2016, November 12, 2016 — GUTS ROUND Organization Team Team ID#

解析

[ 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 non- adjecent vertices consists of edges with at least two different colors. What is the smallest possible value of 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 just considering 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 an edge, and color edges of the same orientation alternatingly with different colors.