Enigmatic Code

Programming Enigma Puzzles

Enigma 1723: Four lots of dots

From New Scientist #2890, 10th November 2012 [link]

The picture shows 16 dots drawn in an evenly spaced 4-by-4 square array. How many squares can be made using four of the dots as the vertices? In fact there are 20, including the one shown.

I have now drawn another square array of the same type but with a larger number of dots. This time the number of squares possible is four times the number of dots.

How many dots have I drawn?

[enigma1723]

3 responses to “Enigma 1723: Four lots of dots

  1. Jim Randell 7 November 2012 at 6:12 pm

    The following Python program is a constructive approach that counts the number possible squares on the grid. It runs in 44ms.

    If you want a fast non-constructive approach it turns out there is a simple formula that generates the required sequence (see OEIS sequence A002415).

    from itertools import count
    from enigma import irange, printf
    
    # a square with diagonal (x1, y1) - (x2, y2)
    def square(n, x1, y1, x2, y2):
      # consider the square with doubled co-ordinates
      # determine the centre of the square
      (cx, cy) = (x1 + x2, y1 + y2)
      # translate the centre to the origin
      (x, y) = (2 * x1 - cx, 2 * y1 - cy)
      # determine the other corners of the translated square
      # rejecting any that lie off the grid
      vs = set(((x1, y1), (x2, y2)))
      for (xn, yn) in ((y, -x), (-y, x)):
        (x, r) = divmod(cx + xn, 2)
        if r > 0 or x < 0 or x > n: return None
        (y, r) = divmod(cy + yn, 2)
        if r > 0 or y < 0 or y > n: return None
        vs.add((x, y))
      return vs
    
    # count the number of squares for an (n+1) x (n+1) grid
    def squares(n):
      r = 0
      # starting point of the diagonal is x1, y1
      for y1 in irange(0, n):
        for x1 in irange(0, n):
          # end point is x2, y2
          for y2 in irange(y1, n):
            for x2 in irange(x1 + 1, n):
              # make the square with this diagonal
              if square(n, x1, y1, x2, y2): r += 1
      return r
    
    # try increasing grid sizes
    for n in count(2):
      s = squares(n - 1)
      n2 = n * n
      printf("{n}x{n} grid, {n2} dots, {s} squares")
      if n == 4: assert s == 20 # check we get the right value when n=4
      if s == 4 * n2: break
    

    Solution: You have drawn 49 dots.

    Using the formula S(n) = n²(n² – 1)/12, we are looking for the value of n² where S(n) = 4n², so n²(n² – 1) = 48n², or n² – 1 = 48, hence n² = 49.

    • Jim Randell 12 November 2012 at 2:54 pm

      Here’s a different way of counting the squares:

      from itertools import count, product
      from enigma import irange, printf
      
      # count the number of squares with offset (a, b)
      def nsquares(n, a, b):
        r = 0
        # start at <x1, y1> on the grid and consider the other 3 vertices
        for (x1, y1) in product(irange(0, n - 1), irange(0, n - 1)):
          (x2, y2) = (x1 + a, y1 + b)
          if x2 > n or y2 > n: continue
          (x3, y3) = (x2 - b, y2 + a)
          if y3 > n: continue
          (x4, y4) = (x3 - a, y3 - b)
          if x4 < 0: continue
          r += 1
        return r
      
      # count the number of squares for an (n+1) x (n+1) grid
      def squares(n):
        r = 0
        # consider squares with horizontal offset of a
        # and vertical offset b (where a + b <= n)
        for b in irange(0, n - 1):
          for a in irange(1, n - b):
            r += nsquares(n, a, b)
        return r
      
      # consider increasing grids
      for n in count(2):
        s = squares(n - 1)
        n2 = n * n
        printf("{n}x{n} grid, {n2} dots, {s} squares")
        if n == 4: assert s == 20 # check we get the right value when n=4
        if s == 4 * n2: break
      

      It turns out that nsquares(n, a, b) = [(n + 1) – (a + b)]2, so the sequence we are generating is:

      S(n) = sum(csum(i2 for i in range(1, n)))

      where csum() is the cumulative sum function from the enigma.py library.

      And if you crunch the maths you get: S(n) = (n4 – n2)/12.

  2. Brian Gladman 8 November 2012 at 5:09 pm

    Here is my version.

    # x_max and y_max are the width and height of the grid with grid
    # points (x, y) such that 0 <= x <= x_max and 0 <= y <= y_max.
    from itertools import product, count
    
    # for a square with vertexes on grid points (x0, y0) and (x1, y1),
    # check that the remaining two vertexes are both within the grid
    def check(x0, y0, x1, y1, x_max, y_max):
      if 0 <= x0 + y0 - y1 <= x_max and 0 <= y0 + x1 - x0 <= y_max:
        if 0 <= x1 + y0 - y1 <= x_max and 0 <= y1 + x1 - x0 <= y_max:
          return True
      return False
    
    def cnt_sq(x_max, y_max):
      cnt = 0
      # place the first grid point
      for x0, y0 in product(range(0, x_max), range(0, y_max)):
        # the second grid point must be right of the first to
        # avoid counting duplicate squares
        for x1 in range(x0 + 1, x_max + 1):
          # and it must not be below the first
          for y1 in range(y0, y_max + 1):
            # check that the other two vertexes are within the grid
            if check(x0, y0, x1, y1, x_max, y_max):
              cnt += 1
      return cnt
    
    for n in count(1):
      # look for an n value such that the number of squares
      # is four times the number of grid points
      if cnt_sq(n, n) == 4 * (n + 1) ** 2:
        print('Answer =', (n + 1) ** 2)
        break
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: