Enigmatic Code

Programming Enigma Puzzles

Enigma 1308: Passing through

From New Scientist #2466, 25th September 2004

Enigma 1308 - 8x5

Enigma 1308 - 10x4

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]

Advertisements

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:

    Enigma 1308 - Solution 24x6

    Enigma 1308 - Solution 18x8

    Enigma 1308 - Solution 16x9

    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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: