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 fivepoints in { ( x, y ) | 1 ≤ x, y ≤ 5 } blue such that the distance between any two blue points is not aninteger.
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.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
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 fivepoints in { ( x, y ) | 1 ≤ x, y ≤ 5 } blue such that the distance between any two blue points is not aninteger.
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 mustmake a permutation of 1 , 2 , 3 , 4 , 5 that avoid the pattern of 3-4-5 triangles. It is not hard to usecomplementary 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 rowor column (i.e. a pair that is in the 3-4-5 position). If such a pair of points is included in the choiceof 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 thentwo 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.