Project Euler Problem 85

Solution

Answer: 2772

Let a grid have width $m$ and height $n$, measured in unit squares.

We want to count how many different rectangles can be formed inside the grid.

Step 1: Count rectangles in an $m \times n$ grid

A rectangle is determined by choosing:

• two distinct vertical grid lines,
• two distinct horizontal grid lines.

An $m \times n$ grid has:

• $m+1$ vertical grid lines,
• $n+1$ horizontal grid lines.

So the number of rectangles is

$$\binom{m+1}{2}\binom{n+1}{2}.$$

Using

$$\binom{k}{2}=\frac{k(k-1)}2,$$

we get

$$R(m,n) = \frac{m(m+1)}2 \cdot \frac{n(n+1)}2.$$

So

$$R(m,n)=\frac{m(m+1)n(n+1)}4.$$

The target is:

$$R(m,n)\approx 2{,}000{,}000.$$

We are asked for the grid area

$$A=mn$$

whose rectangle count is nearest to two million.

---

Step 2: Verify the small example

For a $3\times2$ grid:

$$R(3,2) = \frac{3\cdot4}{2}\cdot\frac{2\cdot3}{2} = 6\cdot3 = 18.$$

This matches the problem statement.

---

Step 3: Strategy

The rectangle count grows roughly like

$$\frac{m^2n^2}{4},$$

so values near the target will have dimensions around a few dozen.

A brute-force search over reasonable ranges is perfectly feasible.

For each pair $(m,n)$:

1. compute the rectangle count,
2. compute the difference from $2{,}000{,}000$,
3. keep the best grid.

---

Python Implementation

TARGET = 2_000_000

best_diff = float('inf')
best_area = None
best_dims = None

# Search reasonable grid sizes.
# 100 is safely large enough.
for m in range(1, 101):
    for n in range(1, 101):

        # Number of rectangles in an m x n grid
        rectangles = (m * (m + 1) * n * (n + 1)) // 4

        diff = abs(rectangles - TARGET)

        # Update best solution if closer
        if diff < best_diff:
            best_diff = diff
            best_area = m * n
            best_dims = (m, n)

print("Best dimensions:", best_dims)
print("Area:", best_area)
print("Rectangle count:",
      (best_dims[0] * (best_dims[0] + 1) *
       best_dims[1] * (best_dims[1] + 1)) // 4)
print("Difference:", best_diff)

---

Code Walkthrough

TARGET = 2_000_000

The desired rectangle count.

---

best_diff = float('inf')
best_area = None
best_dims = None

These variables store the best solution found so far.

• best_diff = smallest difference from target,
• best_area = corresponding grid area,
• best_dims = dimensions of that grid.

---

for m in range(1, 101):
    for n in range(1, 101):

Try all grid sizes from $1$ to $100$.

This is more than enough because rectangle counts grow quadratically.

---

rectangles = (m * (m + 1) * n * (n + 1)) // 4

Implements

$$R(m,n)=\frac{m(m+1)n(n+1)}4.$$

Integer division is exact because the product is always divisible by 4.

---

diff = abs(rectangles - TARGET)

Distance from two million.

---

if diff < best_diff:

If this grid is closer than any previous one, store it.

---

Small Example Check

For $m=3$, $n=2$:

(3 * 4 * 2 * 3) // 4 = 18

Correct.

---

Result of the Search

The closest rectangle count occurs for a grid:

$$36 \times 77$$

with area

$$36 \cdot 77 = 2772.$$

Its rectangle count is:

$$\frac{36\cdot37\cdot77\cdot78}{4} = 1{,}999{,}998,$$

which is only $2$ away from two million.

No exact solution exists.

---

Final Verification

• Rectangle count is extremely close to $2{,}000{,}000$.
• Area magnitude is reasonable for dimensions around $40$-$80$.
• Symmetry check: $36\times77$ and $77\times36$ give the same result.
• Difference $=2$ is minimal.

Answer: 2772