Enigmatic Code

Programming Enigma Puzzles

Enigma 454: Stepped rectangles

From New Scientist #1605, 24th March 1988 [link]

Enigma 454

Oölith the Rational, on conquering the town of Major-Minor, the two parts of which are separated by a river, decreed that two piazzas be built, one (the larger of the two) in Major and one in Minor. They were to be stepped rectangles (see diagram) of square slabs, each measuring 1 groddly by 1 groddly. Each piazza was to contain a number of slabs equal to the perimeter in groddlies multiplied by the king’s age (an exact number of years).

The vizier explained to the grand mason appointed to this task: “A stepped rectangle is a plane array of square slabs laid edge to edge with no overlap. The sides of the figure are zig-zag: if you imagine walking around its perimeter clockwise, you must turn alternately left and right except at the four extreme corners, at each of which you must make exactly two consecutive right turns.”

The mason knew the king’s age (he was in his twenties) and realised that exactly and only two different stepped rectangles were possible which would fit the conditions.

How many slabs did he require to build:

(a) the Major piazza;
(b) the Minor piazza?

[enigma454]

5 responses to “Enigma 454: Stepped rectangles

  1. Jim Randell 29 June 2018 at 8:20 am

    A bit of analysis gives us an easy way to look for possible dimensions of stepped rectangles, for a given value of the King’s age.

    If we measure a “stepped rectangle” by the number of points touching the enclosing rectangle (so the diagram in the puzzle shows a 3×4 rectangle), then the perimeter of an m × n stepped rectangle is:

    P(m, n) = 4(m + n – 1)

    and the number of slabs required is:

    S(m, n) = mn + (m – 1)(n – 1) = 2mn – m – n + 1

    So, if the age of the king is k, we want:

    S(m, n) = k × P(m, n)
    2mn – m – n + 1 = 4k(m + n – 1)
    n = (4k + 1)(m – 1) / (2m – 4k – 1)

    The numerator is always non-negative (m > 0), so to get a reasonable value for n we require the denominator to be positive:

    m > 2k + 1/2

    This Python program runs in 70ms.

    Run: [ @repl.it ]

    from itertools import count
    from enigma import irange, unpack, printf
    
    # perimeter: P(n, m) = 4(n + m - 1)
    P = lambda n, m: 4 * (n + m - 1)
    
    # slabs required: S(n, m) = mn + (m - 1)(n - 1) = 2mn - m - n + 1
    S = lambda n, m: 2 * m * n - m - n + 1
    
    # consider possible ages for the king
    for k in irange(20, 29):
    
      # collect possible (n, m) results
      rs = list()
    
      # consider values for m
      for m in count(2 * k + 1):
        # determine n
        (n, r) = divmod((4 * k + 1) * (m - 1), 2 * m - 4 * k - 1)
        if n < m: break
        if r != 0: continue
        rs.append((m, n))
    
      # did we find exactly 2 results?
      printf("[k={k}, {n} results]", n=len(rs))
      if len(rs) == 2:
        for (m, n) in sorted(rs, key=unpack(S), reverse=1):
          printf("-> {m}x{n}: p={p}, s={s}", p=P(m, n), s=S(m, n))
    

    Solution: (a) The Major piazza requires 641,520 slabs. (b) The Minor piazza requires 23,328 slabs.

    The King is 27. The perimeter of the Major piazza is 23,760, and the perimeter of the Minor piazza is 864.

    The Minor piazza is very close to square being a 108×109 rectangle, but the Major piazza is over 100 times longer in one dimension than the other, it is a 55×5886 rectangle.

    Here is a scale diagram of the two piazzas, next to each other:

    • Hugh Casement 29 June 2018 at 9:46 am

      It seems that, for any age k, the squarest piazza measures 4k by (4k + 1).
      The most unsquare has shorter side 2k + 1.
      Only k = 27 (among the twenties) has no solutions in between.

      • Jim Randell 30 June 2018 at 8:34 am

        OEIS A045753 [ https://oeis.org/A045753 ] gives a list of possible values k for the age of the king that will give only two possible rectangles, with dimensions (m, n) = (4k, 4k + 1) and (m, n) = (2k + 1, 2k(4k + 1)).

        So we can use the following program:

        from enigma import irange, Primes, printf
        
        # perimeter: P(n, m) = 4(n + m - 1)
        P = lambda n, m: 4 * (n + m - 1)
        
        # slabs required: S(n, m) = mn + (m - 1)(n - 1) = 2mn - m - n + 1
        S = lambda n, m: 2 * m * n - m - n + 1
        
        # primes up to 4k + 1
        primes = Primes(118)
        
        # consider possible ages for the king
        for k in irange(20, 29):
        
          k4 = 4 * k
          if k4 - 1 in primes and k4 + 1 in primes:
            printf("[k={k}]")
            (m, n) = (2 * k + 1, 2 * k * (k4 + 1))
            printf("major: {m}x{n}: p={p}, s={s}", p=P(m, n), s=S(m, n))
            (m, n) = (k4, k4 + 1)
            printf("minor: {m}x{n}: p={p}, s={s}", p=P(m, n), s=S(m, n))
        
  2. Brian Gladman 29 June 2018 at 8:26 am
    from collections import defaultdict
    from number_theory import divisor_pairs 
    
    # Let the bounding rectangle be sqrt(2).m wide and sqrt(2).n long so that
    # its area is 2.m.n slabs.  To get the area of the slabs we have to reduce
    # this by (m - 1) half slabs on two sides, (n - 1) half slabs on the other
    # two sides and by four quarter slabs at the four quarters.  So the number
    # of slabs used is 2.m.n - m - n + 1 = {(2.m - 1).(2.n - 1) + 1} / 2 . The
    # perimeter consists of (m - 1) pairs of slab sides on two sides, (n - 1)
    # pairs of slab sides on the other two sides and one slab side at each of
    # the four corners, making 4.(m + n - 1) in total. 
    #
    # If the king's age is k, we are hence looking for integer solutions of:
    #
    #     {(2.m - 1).(2.n - 1) + 1} / 2 == 4.k.(m + n - 1)
    #
    # which, with p = 2.m - 1 and q = 2.n - 1, becomes:
    #
    #     p.q + 1 == 4.k.(p + q)
    #
    # This can be put in the form:
    #
    #     (p - 4.k).(q - 4.k) == (4.k - 1).(4.k + 1)
    #
    # which we need to solve for 20 <= k < 30, looking for k values that 
    # yield exactly two solutions.  We can find one solution immediately
    # by associating (p - 4.k) with (4.k - 1) and (q - 4.k) with (4.k + 1)
    # to give m = 4.k and n = 4.k + 1. A second solution can be found by
    # associating (p - 4.k) with 1 and (q - 4.k) with (4.k - 1).(4.k + 1)
    # giving m = 2.k + 1 and n = 2.k.(4k + 1). If k is such that 4.k - 1
    # and 4.k + 1 are prime, these are the only solutions in integers and
    # the only age in the twenties that gives two primes is 27.
    
    # store solutions for ages 20 to 29
    a2mn = defaultdict(list)
    for k in range(20, 30):
      for p, q in divisor_pairs(16 * k * k - 1):
        m, r = divmod(p + 4 * k + 1, 2)
        n, s = divmod(q + 4 * k + 1, 2)
        if not (r or s):
          a2mn[k].append((m, n))
    
    # for saving the two solutions found
    sol = []
    # look for a king's age that gives exactly two solutions
    for k, v in a2mn.items():
      if len(v) == 2:
        for m, n in v:
          # compute the number of slabs and the perimeter
          s = ((2 * m - 1) * (2 * n - 1) + 1) // 2
          p = 4 * (m + n - 1)
          sol.append((s, p, k, m, n))
    
    for (s, p, k, m, n), ltr in sorted(zip(sol, 'ab'), reverse=True):
      print(f'({ltr}) {s:,} slabs, perimeter {p:,} (m = {m}, n = {n}, age = {k}).')
    
    • Jim Randell 29 June 2018 at 9:30 am

      @Brian: That’s a neat analysis.

      I think we can simplify the code a little. As (4k)² – 1 is odd, then any factorisation will also be odd, so the calculation of m and n will not have a remainder, and each factorisation will lead to a valid rectangle.

      Here’s a combination of our two programs:

      from enigma import irange, divisors_pairs, unpack, printf
      
      # perimeter: P(n, m) = 4(n + m - 1)
      P = lambda n, m: 4 * (n + m - 1)
      
      # slabs required: S(n, m) = mn + (m - 1)(n - 1) = 2mn - m - n + 1
      S = lambda n, m: 2 * m * n - m - n + 1
      
      # consider possible ages for the king
      for k in irange(20, 29):
      
        # calculate (m, n) by factorising (4k)^2 - 1
        k4 = 4 * k
        rs = list(divisors_pairs(k4 * k4 - 1))
      
        # did we find exactly 2 results?
        printf("[k={k}, {n} results]", n=len(rs))
        if len(rs) == 2:
          # convert the factors to rectangle dimensions
          fn = lambda x: (x + k4 + 1) // 2
          rs = list((fn(a), fn(b)) for (a, b) in rs)
          # output the results (largest S first)
          for (m, n) in sorted(rs, key=unpack(S), reverse=1):
            printf("-> {m}x{n}: p={p}, s={s}", p=P(m, n), s=S(m, n))
      

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: