12
$\begingroup$

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\times n$ where $m,n\geqslant 2$?

For example;

$2\times2$ there is only $1$ square possible:

enter image description here

$3\times2$ there are only $2$ squares possible and $3\times3$ there are $6$ squares shown as below:

enter image description here enter image description here enter image description here

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

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

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) = (ma) (na)

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 a into 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 bounding-box positions and possible squares in bounding box

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 · (ma) (na);    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 mn)

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)

$\endgroup$
  • $\begingroup$ So what is the formula which is symmetric in n and m (recall that you assumed n<=m)? $\endgroup$ – Matsmath May 16 '17 at 13:00
  • $\begingroup$ I assumed nm so that I didn't have to use min(n, m) when I determine the number of square positions and the upper bound for the sums. I don't know whether there really is a symmatric formula. $\endgroup$ – M Oehm May 16 '17 at 13:14
  • $\begingroup$ In “k is the edgel length of the grid, m and n are the numbers of pegs along the adge” are edgel and adge technical terms, or typos? $\endgroup$ – James Waldby - jwpat7 May 16 '17 at 16:52
  • 1
    $\begingroup$ No, they are typos, of course. It should be "edge" in both cases. As I get older, I get sloppier and sloppier at typing and it bugs me. $\endgroup$ – M Oehm May 16 '17 at 17:02
  • $\begingroup$ Nice! This formula in m and n is really nice as well. $\endgroup$ – Wen1now May 17 '17 at 22:33
15
$\begingroup$

I will deal with the $n\times n$ case only

Summarising this :)

Let $T_n$ be the total number of squares (including tilted ones) on a square grid and let $N_n$ be the number of 'normal' squares, oriented such that the sides of these squares are parallel to the sides of the original grid. I claim that $T_n=T_{n-1}+N_n$ by providing a bijection between tilted squares in a $n\times n$ grid and all squares in a $(n-1)\times (n-1)$ grid. For any square in a $(n-1)\times (n-1)$ grid, fix the top right corner (top takes priority - so a diagonal square would just be the top corner) and move the vertex that is counterclockwise around from it down one unit. Then this forms a side of a new square (such that the top right vertex is still the top right vertex). This is non-trivially a bijection, but it is not that hard to prove either so I leave it as an exercise.

Bijection picture (appropriated from brilliant.org): enter image description here

So since $N_n = \frac{n(n+1)(2n+1)}{6}$ (which can be found just about anywhere) we can sum the first $n$ things to find $T_n$. This turns out to be

$\frac{n(n+1)^2(n+2)}{12}$

I believe. We could check - base case n=1 both sides are equal.

Assume that it is equal for $n$. Then increasing by 1 gives

$\frac{n(n+1)^2(n+2)}{12} + \frac{2(n+1)(n+2)(2n+3)}{12}$, which, after some algebraic manipulation should yield $\frac{(n+1)(n+2)^2(n+3)}{12}$ which is what we wanted.

So the number of squares on a $n\times n$ grid is a neat

$\frac{n(n+1)^2(n+2)}{12} \square$

Mathematics can be so beautiful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.