HMMT 二月 2019 · 团队赛 · 第 8 题

HMMT February 2019 — Team Round — Problem 8

[ 50 ] Can the set of lattice points { ( x, y ) | x, y ∈ Z , 1 ≤ x, y ≤ 252 , x 6 = y } be colored using 10 distinct colors such that for all a 6 = b, b 6 = c, the colors of ( a, b ) and ( b, c ) are distinct?

解析

[ 50 ] Can the set of lattice points { ( x, y ) | x, y ∈ Z , 1 ≤ x, y ≤ 252 , x 6 = y } be colored using 10 distinct colors such that for all a 6 = b, b 6 = c, the colors of ( a, b ) and ( b, c ) are distinct? Proposed by: Franklyn Wang Answer: Yes Associate to each number from 1 to 252 a distinct 5-element subset of S = { 1 , 2 , . . . , 10 } . Then assign to ( a, b ) an element of S that is in the subset associated to a but not in that associated to b. It’s not difficult to see that this numerical assignment is a valid coloring: the color assigned to ( a, b ) is not in b , while the color assigned to ( b, c ) is in b , so they must be distinct.