HMMT 十一月 2018 · 冲刺赛 · 第 23 题

HMMT November 2018 — Guts Round — Problem 23

[ 12 ] Let S be a subset with four elements chosen from { 1 , 2 , . . . , 10 } . Michael notes that there is a way to label the vertices of a square with elements from S such that no two vertices have the same label, and the labels adjacent to any side of the square differ by at least 4. How many possibilities are there for the subset S ?

解析

[ 12 ] Let S be a subset with four elements chosen from { 1 , 2 , . . . , 10 } . Michael notes that there is a way to label the vertices of a square with elements from S such that no two vertices have the same label, and the labels adjacent to any side of the square di ↵ er by at least 4. How many possibilities are there for the subset S ? Proposed by: James Lin Answer: 36 Let the four numbers be a, b, c, d around the square. Assume without loss of generality that a is the largest number, so that a > b and a > d . Note that c cannot be simultaneously smaller than one of b, d and larger than the other because, e.g. if b > c > d , then a > b > c > d and a d + 12. Hence c is either smaller than b and d or larger than b and d . Case 1: c is smaller than b and d . Then we have a c 8, but when a c = 8, we have b = c + 4 = d , so we need a c = 9, giving the only set { 1 , 5 , 6 , 10 } . Case 2: c is larger than b and d . Since a > c and b, d are both at most c 4, the range of possible values 5 4 3 2 for c is { 6 , 7 , 8 , 9 } . When c = 9 , 8 , 7 , 6, there are 1 , 2 , 3 , 4 choices for a respectively and , , , 2 2 2 2 for b and d respectively (remember that order of b and d does not matter). So there are 1 · 10 + 2 · 6 + 3 · 3 + 4 · 1 = 35 sets in this case. Therefore we have 1 + 35 = 36 possible sets in total.