返回题库

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

HMMT February 2019 — Guts Round — Problem 12

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

  1. [ 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#

解析

英文解析

  1. [ 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.