Enigmatic Code

Programming Enigma Puzzles

Enigma 1336: Rectangles

From New Scientist #2495, 16th April 2005

George has a rectangular piece of paper, 3 inches by 4 inches, marked with a 1-inch grid. He is wondering in how many ways he can mark a rectangle (which may be a square) on it, following the grid lines.

He has identified eight [*] different possible sizes and shapes, and various different places in which each can be marked, ranging from 1 to 17 different positions per shape. The total is 60.

He now has a larger rectangular piece of paper of integer dimensions (more than 100 square inches) and he has tackled the same problem. Instead of 60, he has calculated a much larger number which is the product of four consecutive primes.

What are the dimensions of this piece of paper?

[*] I think there is a mistake in this puzzle, in that it should read “He has identified nine different possible sizes and shapes…”. It all seems to make sense if you make that change.

[enigma1336]

Advertisements

3 responses to “Enigma 1336: Rectangles

  1. Jim Randell 29 March 2014 at 7:54 am

    With the wording of the problem saying there were eight different sizes and shapes. I thought there might be some little wrinkle like the entire 3×4 rectangle not counting as you can’t mark it out. But to get a shape with only one possible position I had to include it, and that gave me nine different shapes with between 1 and 17 possible positions to give a total of 60 rectangles (the shapes and counts being: 1×1 = 12, 1×2 = 17, 1×3 = 10, 1×4 = 3, 2×2 = 6, 2×3 = 7, 2×4 = 2, 3×3 = 2, 3×4 = 1).

    So it might be clearer to think of the puzzle as counting the number of different (size/shape) rectangles that can be made on a corresponding grid of nails, by placing a rubber band around some of the pins to make a rectangular shape with sides parallel to the axes of the grid. (There are other rectangles possible that don’t have sides parallel to the axes, but these are not considered in this problem).

    This problem is quite similar to Enigma 1452, where we derived the following equation:

    R(n, m) = n m (n + 1) (m + 1) / 4

    Using this equation the program below counts the number of rectangles that can be made on a grid of the given size, and looks at increasing size grids until one that satisfies the conditions is found. It runs in 32ms. It’s only slightly slower to constructively count the rectangles for each case.

    from itertools import count
    from enigma import irange, factor, is_prime, first, printf
    
    # consider paper of dimensions n x m
    def R(n, m):
      return n * m * (n + 1) * (m + 1) // 4
    
    assert R(3, 4) == 60
    
    def generate():
      for m in count(1):
        for n in irange(1, m):
          if not(m * n > 100): continue
          t = R(n, m)
          fs = factor(t)
          if len(fs) != 4: continue
          if len(set(fs)) != 4: continue
          if any(x not in fs and is_prime(x) for x in irange(fs[0], fs[-1])): continue
    
          yield (n, m, t, fs)
    
    for (n, m, t, fs) in first(generate()):
      printf("{n} x {m} => {t} {fs}")
    

    Solution: The piece of paper is 10″ × 13″.

    There are 5005 possible rectangles in a 10 × 13 rectangle.

    Enigma 1723 is a similar puzzles that counts squares on a grid including non-orthogonal squares.

  2. Tessa Fullwood 4 April 2014 at 3:09 pm

    Jim I agree, there are 9 possible ‘shapes’ on a 4×3 grid. I don’t know why the puzzle setter wrote 8, just a slip UP, What took the time for me solving this was coming up with R(n,m).

    Thanks for continuing to post the enigmas.

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: