HMMT-Feb 2019 guts, Problem 12

Bob is coloring lattice points in the coordinate plane. Find the number of ways Bob can color five points in $\{(x, y) \mid 1 \leq x, y \leq 5\}$ blue such that the distance between any two blue points is not an integer.

Solution: 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 \times 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 \times 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. $\fbox{80}$.

Answer: 80