HMMT 二月 2019 · 冲刺赛 · 第 12 题

HMMT February 2019 — Guts Round — Problem 12

[ 5 ] Bob is coloring lattice points in the coordinate plane. Find the number of ways Bob can color five points in { ( x, y ) | 1 ≤ x, y ≤ 5 } blue such that the distance between any two blue points is not an integer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT February 2019, February 16, 2019 — GUTS ROUND Organization Team Team ID#

解析

[ 5 ] Bob is coloring lattice points in the coordinate plane. Find the number of ways Bob can color five points in { ( x, y ) | 1 ≤ x, y ≤ 5 } blue such that the distance between any two blue points is not an integer. Proposed by: Michael Ren Answer: 80 We can see that no two blue points can have the same x or y coordinate. The blue points then must make a permutation of 1 , 2 , 3 , 4 , 5 that avoid the pattern of 3-4-5 triangles. It is not hard to use complementary counting to get the answer from here. There are 8 possible pairs of points that are a distance of 5 apart while not being in the same row or column (i.e. a pair that is in the 3-4-5 position). If such a pair of points is included in the choice of five points, then there are 3! = 6 possibilities for the remaining three points, yielding 8 × 6 = 48 configurations that have violations. However, we now need to consider overcounting. The only way to have more than one violation in one configuration is to have a corner point and then two points adjacent to the opposite corner, e.g. (1 , 1) , (4 , 5) , (5 , 4) . In each such case, there are exactly 2! = 2 possibilities for the other two points, and there are exactly two violations so there are a total of 2 × 4 = 8 configurations that are double-counted. Therefore, there are 48 − 8 = 40 permutations that violate the no-integer-condition, leaving 120 − 40 = 80 good configurations.