# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1452: Crossed lines

From New Scientist #2613, 21st July 2007

How 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}")
```