We call a set of squares with sides parallel to the coordinate axes and vertices with integer coordinates friendly if any two of them have exactly two points in common. We consider friendly sets in which each of the squares has sides of length . Determine the largest possible number of squares in such a friendly set.
, 2014
Solution
No two such vertices can lie on the same horizontal or vertical line, as the squares with these vertices would otherwise have a line segment in common, and not just two points.
We see that the highest possible number of possible vertices of other squares in the interior of the chosen square is equal to the number of horizontal (and vertical) lines with integer coordinates crossing the interior of the square, i.e. . The largest possible number of squares in the friendly set is therefore .
This number is indeed obtainable, e.g. if the squares are ordered diagonally as shown in Figure 1.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.