Enigmatic Code

Programming Enigma Puzzles

Enigma 1452: Crossed lines

From New Scientist #2613, 21st July 2007

Enigma 1553How many rectangles can be seen in this 4-by-4 grid shown above? In fact there are exactly 100.

I made a much larger square grid with lines dividing it into little squares (a three-figure number of little squares, in fact) and I calculated the number of rectangles which could be seen in this new grid. I then cut the grid along one of the lines in order to make two rectangular pieces and I calculated the number of rectangles visible in each of my two new pieces. The total of these two numbers was exactly two-thirds of the number visible in my original large square grid.

What was the size of my original grid before I cut it?

[enigma1452]

Advertisements

2 responses to “Enigma 1452: Crossed lines

  1. Jim Randell 11 March 2013 at 9:24 am

    This Python program counts the number of smaller rectangles in the larger rectangles, by considering the number of top-right corners for any bottom-left corner. It runs in 59ms.

    from enigma import irange, printf
    
    # count the rectangles in an n x m rectangle
    def R(n, m):
      r = 0
      for i in irange(0, n - 1):
        for j in irange(0, m - 1):
          r += (n - i) * (m - j)
      return r
    
    # start with a square grid with a 3-digit number of unit squares
    for n in irange(10, 31):
      r = R(n, n)
      # divide the square
      for i in irange(1, n // 2):
        r1, r2 = R(n, i), R(n, n - i)
        if 3 * (r1 + r2) == 2 * r:
          printf("[n={n} i={i}] r={r} r1={r1} r2={r2}")
    

    Solution: The original grid was 27 × 27.

    • Jim Randell 11 March 2013 at 9:25 am

      You can avoid doing the counting by deriving an equation for R(n,m). The sum of integers from 1 to n is T(n), where:

      T(n) = ½ n (n + 1)

      and it follows that:

      R(n,m) = ¼ n m (n + 1) (m + 1)

      and the condition we are looking for is:

      R(n, i) + R(n, n – i) = ⅔ R(n, n) where i < n

      which simplifies to:

      n (n + 1) = 6 i (n – i)

      The following Python program finds the solution using this equation in 34ms.

      from enigma import irange, printf
      
      # doing the maths we get:
      # R(n, m) = n * m * (n + 1) * (m + 1) // 4
      # and R(n, i) + R(n, n - i) = (2/3) R(n, n) when:
      # n * (n + 1) = 6 * i * (n - i)
      
      # start with a square grid with a 3-digit number of unit squares
      for n in irange(10, 31):
        a = n * (n + 1)
        for i in irange(1, n // 2):
          b = 6 * i * (n - i)
          if a == b:
            printf("n={n} i={i}")
      

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: