**From New Scientist #2466, 25th September 2004**

If you are told to draw a rectangle along the lines of a sheet of graph paper such that its area is 40 squares you could choose rectangles measuring 8×5, 10×4, 20×2 or 40×1. Whether you chose the 8×5 or the 10×4 you would find that a diagonal drawn across your rectangle would pass though 12 of the squares.

(1) What is the smallest number of squares of the graph paper that can be the area of THREE different rectangles whose diagonals each pass through the same number of squares?

(2) How many squares does each of those diagonals pass through?

[enigma1308]

### Like this:

Like Loading...

This Python program counts the number of squares crossed by the diagonal in an arbitrary grid, and looks for the first set of rectangles with the same area that provide N different ways of achieving the same number. It solves the N=3 case in 352ms.

Solution:(1) the area of the rectangles is 144 squares; (2) the diagonals pass through 24 squares.The dimensions of the three rectangles are 24×6, 18×8 and 16×9, as shown below:

The N=4 case requires rectangles with an area of 3024 squares (36×84, 42×72, 48×63, 54×56), with the diagonals each passing through 108 squares.

The N=5 case requires rectangles with an area of 3600 squares (30×120, 40×90, 45×80, 48×75, 50×72), with the diagonals each passing through 120 squares.

The N=6 case requires rectangles with an area of 32400 squares (90×360, 120×270, 135×240, 144×225, 150×216, 162×200), with the diagonals passing through 360 squares.

The N=7 case requires rectangles with an area of 129600 squares (180×720, 240×540, 270×480, 288×450, 300×432, 320×405, 324×400), with the diagonals passing through 720 squares.

After that my program takes too long to run.

Here is my Mma Code

It finds N=8 in 39 seconds, with 176400 squares and these rectangles, the format is

{a x b, GCD[a , b],No Squares cut}

{210 x 840, 210, 840}

{280 x 630, 70, 840}

{315 x 560, 35, 840}

{336 x 525, 21, 840}

{350 x 504, 14, 840}

{360 x 490, 10, 840}

{392 x 450, 2, 840}

{400 x 441, 1, 840}

There is a quick way to check how many squares are cut, it is a + b – gcd[a,b] where a and b are the size of the rectangle. To look for the various N change the [Max[f]==3 to 4 etc.

Paul.

p.s. the GCD[a , b] is 1 more than the number of nodes the line passes through.

Thanks. Using the computed formula

measure(a, b) = a + b - gcd(a, b)makes my program much faster than constructively counting the squares that the diagonal passes through.