Yacoby's Wanderings | Problem 85

Project Euler - Problem 85

In Problem 85 is is required to find the size of a rectangular grid that contains 2 000 000 rectangles (or as near as possible to it)

Looking at the problem in a simpler instance, how many rectangles can fit into a 5x1 rectangle. Drawing it out on a piece of paper we can see that a single block can fit in 5 different places, a double block can fit in 4 different places etc. Generalizing it for a nx1 rectangle, a block of the size kx1 can fit into a nx1 rectangle (n + 1) - k times.

Therefor, the number of different rectangles that can fit into a n*1 block is

$1 + 2 + 3 + .. n = \sum_{r = 1}^{n} r = \frac{n(n+1)}{2}<br /><br />$

Given this we can assume that the number of possibilities for a n*1 and a 1*n rectangle are the same, the number of possibilities for a n*k rectangle are the number of possibilities for a k*1 rectangle multiplied by the number of possibilities for a n*1 rectangle

So the total number of possibilities, P, for a k*n board is:

$P = \sum_{r = 1}^{k} r \sum_{r = 1}^{n} r\\ = \frac{k(k+1)}{2}\frac{n(n+1)}{2}\\ = \frac{1}{4}k(k+1)n(n+1)$

Given that we are finding the size of the board where there are 2 000 000 possible rectangles, P = 2 000 000. So we need to find S when S is minimized and n and k are integers.

$\frac{1}{4}k(k+1)n(n+1) = 2 000 000\\S = |\frac{1}{4}k(k+1)n(n+1) - 2 000 000|$

We do need to be sure about the upper bounds for n and k are. If we let k = 1

$\frac{1}{4}(1)(1 + 1)(n)(n + 1) = 2 000 000\\n(n + 1) = 4 000 000\\n^2 + n - 4 000 000 = 0\\x \approx \pm 2000$

As we know that the maximum value that could possibly be required for n and k is 2000, we can then try and find the minimum value of S

A quick program in D provides the answer.

import std.math;
import std.stdio;

void main(string[] args){
	double best = double.max;
	int bestN, bestK;

	for ( int n = 1; n <= 2_000; n++ ){
		for ( int k = 1; k <= 2_000; k++ ){
			if ( k > n ){
				break;
			}

			double s = abs((1/4.0)*n*(n+1)*k*(k+1) - 2_000_000);
	
			if ( s < best ){
				bestN = n;
				bestK = k;
				best = s;
			}
		}
	}
	
	writefln("(%d, %d)", bestN, bestK);
}