Sunday Times Teaser 2556 – Dotty Squares

by Andrew Skidmore

Published: 18 September 2011 (link)

On a piece of paper I have drawn a neat, evenly spaced square array of 36 dots, namely six rows of six.

If I were to ask you how many squares are formed, you might say just 25, for the array seems to consist of 25 little squares. However, lots of sets of four of the dots form the vertices of a square.

How many ways are there of choosing four of the dots so that they form the vertices of a square?

One Comment Leave one →

Brian Gladman permalink

This is an interesting teaser as it is easy to miss the fact that there are squares whose sides are not parallel to the sides of the grid. After some effort it is possible to work out that the total number of squares for a grid of \(n\) by \(n\) dots is given by \(n^2(n^2-1)/12\), which generates the sequence 0, 1, 6, 20, 50, 105, 196, … as given here in the The On-Line Encyclopedia of Integer Sequences (the count for rectangles rather than squares is given here). When this teaser was first published, I wrote one of my first Python programs to count the number of squares and rectangles in a square grid of dots. I have just dug it out and improved it a bit so here it is:


from itertools import product
from collections import defaultdict
from math import gcd

# Count the squares (or the rectangles) that can be made by
# joining the dots on a regular square grid of dots
def count_rectangles(hdots, vdots, square=False):
  # for counting squares (rectangles)
  cnt = 0
  # for counting squares/rectangles of each area
  d = defaultdict(int)
  
  # count rectangles located at dot (i, j) and in a 90 degree
  # quadrant to avoid double counting rectangles 
  for i, j in product(range(hdots - 1), range(vdots - 1)):
    
    # k is the number of dots right for the next corner of
    # the rectangle; l is the number of dots down
    for k, l in product(range(1, hdots - i), range(vdots - j)):

      # skip if the point is beyond the area of the dots
      if not (0 <= i + k < hdots and 0 <= j + l < vdots):
        continue

      # we have set the lengths of two sides of the square/rectangle
      # but we need to consider the lengths of its other two sides;
      # for counting the squares there is only one length since the
      # length of all the sides is the same; for counting rectangles,
      # however, if the other two sides pass through any dots there
      # will then be a number of rectangles that need to be counted
      
      # calculate the number of rectangles (dots) on the side faces
      g = 1 if square else gcd(k, l)
      # calculate the area of the smallest rectangle (i.e. with side 
      # lengths of sqrt(k^2 + l^2) and (1 / g) times this) 
      ar = (k * k + l * l) // g
      mu = 0
      while not (square and mu):
        mu += 1
        # test bottom two corners of rectangles to ensure
        # that they are within the dotted area
        m, n = i - mu * l // g, j + mu * k // g
        if not (0 <= m < hdots and 0 <= n < vdots and
            0 <= m + k < hdots and 0 <= n + l < vdots):
          break
        cnt += 1
        d[mu * ar] += 1
  return cnt, d

for dots in range(1, 21):
  cnt, d = count_rectangles(dots, dots, square=True)
  # output the sequence(s) in the style of the On-Line 
  # Encyclopedia of Integer Sequences (https://oeis.org/)
  if True:
    print('{0:d}{1:s}'.format(cnt, ', '), end='')
  else:
    # output the counts and the counts for each square
    # or rectangle area
    print(dots, cnt)
    for ar in sorted(d):
      print('  ', ar, d[ar])

from itertools import product

from collections import defaultdict

from math import gcd

# Count the squares (or the rectangles) that can be made by

# joining the dots on a regular square grid of dots

def count_rectangles(hdots, vdots, square=False):

# for counting squares (rectangles)

cnt = 0

# for counting squares/rectangles of each area

d = defaultdict(int)

# count rectangles located at dot (i, j) and in a 90 degree

# quadrant to avoid double counting rectangles

for i, j in product(range(hdots - 1), range(vdots - 1)):

# k is the number of dots right for the next corner of

# the rectangle; l is the number of dots down

for k, l in product(range(1, hdots - i), range(vdots - j)):

# skip if the point is beyond the area of the dots

if not (0 <= i + k < hdots and 0 <= j + l < vdots):

continue

# we have set the lengths of two sides of the square/rectangle

# but we need to consider the lengths of its other two sides;

# for counting the squares there is only one length since the

# length of all the sides is the same; for counting rectangles,

# however, if the other two sides pass through any dots there

# will then be a number of rectangles that need to be counted

# calculate the number of rectangles (dots) on the side faces

g = 1 if square else gcd(k, l)

# calculate the area of the smallest rectangle (i.e. with side

# lengths of sqrt(k^2 + l^2) and (1 / g) times this)

ar = (k * k + l * l) // g

mu = 0

while not (square and mu):

mu += 1

# test bottom two corners of rectangles to ensure

# that they are within the dotted area

m, n = i - mu * l // g, j + mu * k // g

if not (0 <= m < hdots and 0 <= n < vdots and

0 <= m + k < hdots and 0 <= n + l < vdots):

break

cnt += 1

d[mu * ar] += 1

return cnt, d

for dots in range(1, 21):

cnt, d = count_rectangles(dots, dots, square=True)

# output the sequence(s) in the style of the On-Line

# Encyclopedia of Integer Sequences (https://oeis.org/)

if True:

print('{0:d}{1:s}'.format(cnt, ', '), end='')

else:

# output the counts and the counts for each square

# or rectangle area

print(dots, cnt)

for ar in sorted(d):

print(' ', ar, d[ar])

Sunday Times Teaser 2556 – Dotty Squares

by Andrew Skidmore

Published: 18 September 2011 (link)

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta