Enigmatic Code

Programming Enigma Puzzles

Enigma 1308: Passing through

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]

4 responses to “Enigma 1308: Passing through”

1. Jim Randell 19 July 2014 at 7:20 am

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.

```from itertools import count
from fractions import Fraction as F
from collections import defaultdict
from enigma import irange, compare, divisor_pairs, printf

# count how many squares the diagonal of an a x b rectangles passes through
def measure(a, b):
# identify where the diagonal crosses x and y lines
As = list(F(y * b, a) ** 2 + y ** 2 for y in irange(1, a))
Bs = list(x ** 2 + F(x * a, b) ** 2 for x in irange(1, b))
# identify the squares the diagonal passes through
(x, y, n) = (0, 0, 0)
while True:
n += 1
r = compare(As[y], Bs[x])
if r <= 0: y += 1
# if we pass through a junction we're done
if r == 0: return n * (a // y)
if r >= 0: x += 1

assert measure(5, 8) == measure(4, 10) == 12

import sys
N = (3 if len(sys.argv) < 2 else int(sys.argv[1]))
S = (1 if len(sys.argv) < 3 else int(sys.argv[2]))

# consider increasing number of squares
for n in count(S):
# count the different rectangles
rs = list(divisor_pairs(n))
# ignore numbers with too few rectangles
if len(rs) < N: continue
# compute the measures
r = defaultdict(list)
for (a, b) in rs:
m = measure(a, b)
r[m].append((a, b))
printf("[n={n} ({a}, {b}) => {m}]")
# find measures with N different rectangles
ms = list((k, v) for (k, v) in r.items() if not(len(v) < N))
if ms:
for (k, v) in ms:
printf("n={n} {v} => {k}")
break
```

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.

2. Paul 19 July 2014 at 2:20 pm

Here is my Mma Code

```Do[a=Divisors[n];
b=n/a;
c=Cases[Partition[Riffle[a,b],2],{a_,b_}/;a<=Sqrt[n]];
d=GCD@@@c;
e=Partition[Flatten[Riffle[c,d]],3];Do[AppendTo[e[[q]],Total[e[[q,1;;2]]]-e[[q,3]]],{q,1,Length[e]}];
f=Last/@Tally[e[[All,4]]];If[Max[f]==3,
g=Cases[Tally[e[[All,4]]],{a_,b_}/;b==Max[f]];
Print[Cases[e,{a_,b_,c_,d_}/;d==g[[1,1]]]]],{n,10,144}]//Timing

{6 x 24, 6, 24}
{8 x 18, 2, 24}
{9 x 16, 1, 24}

{0.031200,Null}
```

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.

• Paul 19 July 2014 at 2:34 pm

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

• Jim Randell 20 July 2014 at 9:14 am

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.