Skip to main content
OlympiadHQ

Browse · harp

Print

smc

counting and probability senior

Problem

The set is defined by the points with integer coordinates, , . How many squares of side at least have their four vertices in ?
problem
(A)
(B)
(C)
(D)
(E)
Solution
Consider any square that meets the requirements described in the problem. Then, take the vertices of the square and translate them to the first quadrant (This is the "mapping" described in Solution 2). For example, consider a square with vertices and : After following the mapping described in Solution 2, the square looks like this: The position of each vertex within their corresponding grid has not changed.For example, the point is still the top-left point in a grid, albeit a change in quadrant. Trying this out with a couple of other squares, we see that the following property holds: Therefore the logical inverse is true: But how many "unmapped" squares, to be exact? This might seem complicated at first, but with some intuitive thinking, we realize that there are exactly "unmapped" squares that correspond with a "mapped" square. This is because given a "mapped" square, there are choices for the vertex that will remain in the first quadrant; but once that point is chosen, there is only distribution of the other vertices that will result in a square. So, we want four times the number of squares we can make in the first quadrant grid. We divide our counting method into two cases: squares with side length after mapping (which means all four vertices are in the same position relative to their own grids) and squares with side length after mapping. Case 1: There are such squares of length (this is equivalent to counting the number of points on the grid). However, in this scenario, all of the vertices have been mapped onto the same point. So instead of choices for the first quadrant vertex, there is only one. Subsequently there are only such squares that correspond to them. Case 2: Let a square with sides parallel to the axes be known as squares. These squares can have side length or . However, the number of squares possible depends on the side length. For example, there is only possible square of side length , but squares of side length . To be exact, there are possible squares of side length . So, the total number of squares is But what about "tilted" squares? Notice that "tilted squares" can always be inscribed (drawn within) another, bigger square. Let a square inscribed within an square be called a square. How many squares are there? Well, this also depends on the side length. We only want squares whose vertices are lattice points (integer value coordinates), so the number of squares should increase along with side length. We defined squares to be inscribed within squares, so we can say that all squares have their vertices on the side on an square. Consider an square with side length . There are other lattice points along the side of the square, not counting the vertices. Therefore, we can say that there are possible squares for every square with side length . We can multiply times the number of squares to get the number of squares. This is total squares. But we need to add these two quantities to get the number of squares for Case 2: By distributive property, the expression becomes Solving, we get "mapped" squares, both and . Multiplying this by to get the corresponding number of "unmapped" squares, then adding to get the number of squares for Case 1, we get .
Final answer
E