### Random Post

### Recent Posts

- Tantalizer 450: Marriage problems
- Enigma 1057: Recycled change
- Enigma 452: Figure out these letters
- Puzzle 46: I lose my specs
- Enigma 1058: A row of colours
- Enigma 451: Double halved
- Tantalizer 451: Death rates
- Enigma 1059: Century break
- Enigma 450: A pentagonal problem
- Puzzle 48: Verse on the island

### Recent Comments

Jim Randell on Tantalizer 450: Marriage … | |

Brian Gladman on Enigma 1057: Recycled cha… | |

Jim Randell on Enigma 1057: Recycled cha… | |

geoffrounce on Enigma 452: Figure out these… | |

Jim Randell on Enigma 452: Figure out these… |

### Archives

### Categories

- article (11)
- enigma (1,183)
- misc (2)
- project euler (2)
- puzzle (46)
- site news (46)
- tantalizer (50)
- teaser (3)

### Site Stats

- 184,975 hits

Advertisements

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.