Question

How many squares can you make using any four points?

Answer 1

This question is directly related to How Many Squares on the Peg Solitaire.

Is it possible to formulate with a given dimension of equal ranged points m×nm×n where m,n⩾2m,n⩾2?

For example;

2×22×2 there is only 11 square possible:



3×23×2 there are only 22 squares possible and 3×33×3 there are 66 squares shown as below:



share improve this question

askedMay 16 '17 at 8:52



Oray
12k●3●32●120

Looks like something that's polynomial in two variables - if so, plugging in lots of small m and n would give you the answer – boboquack May 16 '17 at 9:11

add a comment

2 Answers

order by                          active                         oldest                         votes                     

up vote14down voteaccepted

For the general case, let's assume that 2 ≤ n ≤ m.

Every possible square has an axis-aligned boundary box that is a square of edge length a. Such a square can fit into the n × m grid at

  P(a) = (m − a) (n − a)

positions, see illustration below (left). If we define each square by the edge of its north-west corner (dx, dy), dx > 0, dy ≥ 0; the edge length of the bounding box is

  a = dx + dy .

There are a possibilities to split each ainto dx and dy as shown below (right). (Note that dx can't be zero, because such a square would be a 90° rotation of an axis-aligned square that has already been accounted for by the case where dy is zero.)

   

Possible edge lengths of bounding boxes are 0 < a < n. Therefore, the number of squares that fit into a grid of n × m nodes is:

  N = ∑a a · (m − a) (n − a);    a = 1,..., n − 1
   = ∑a (a³ − (m + n) a² + m n a)

Using the well-known (i.e. easily googleable) Faulhaber formulas, we get:

  N= ¹/₄ (n − 1)² n²   − ¹/₆ (n − 1) (n (2n − 1) (m + n)   + ¹/₂ (n − 1) n² m

and after a bit of rearranging and simplifying:

  N(n, m) = ¹/₁₂ (n − 1) n (n + 1) (2 m − n)

My approach is different from (and perhaps less elegant than) Wen1now's, but it arrives at the same solution. There's a difference in nomenclature; k is the edge length of the grid, m and n are the numbers of pegs along the edge as in the question. If we set n = m = k + 1, we get:

  N(k) = ¹/₁₂ k (k + 1)² (k + 2)

Answer 2

only one square we can make