S2T2

Jim Randell 4:38 pm on 9 October 2020 Permalink Reply
Tags: by: Victor Bryant ( 108 )   

• 

  Jim Randell 5:17 pm on 9 October 2020 Permalink | Reply

  (See also: Enigma 1251, Enigma 1491).

  If the squares are composed of at least two pieces, they must be at least 3×3.

  This Python program works out the only possible original number that can work, but it doesn’t demonstrate the the rectangles can be assembled into the required squares.

  It runs in 44ms.

  Run: [ @repl.it ]

  from enigma import irange, inf, printf
  
  # generate rectangles with area less than n
  def rectangles(n):
    for i in irange(1, n):
      if i * i > n: break
      for j in irange(i, n // i):
        yield (i, j)
  
  # decompose t into squares
  def decompose(t, m=1, ss=[]):
    if t == 0:
      yield ss
    else:
      for k in irange(m, t):
        s = k * k
        if s > t: break
        yield from decompose(t - s, k, ss + [k])
  
  # make squares from the rectangular pieces, with total area A
  def fit(rs, A):
    # determine the maximum dimension of the rectangles
    m = max(j for (i, j) in rs)
    for n in irange(m, A):
      if n * n > A: break
      # decompose the remaining area into squares
      for ss in decompose(A - n * n, 3):
        if len(ss) < 2: continue
        yield ss + [n]
  
  # consider the chosen number
  for n in irange(2, inf):
    # collect the rectangles and total area
    rs = list(rectangles(n))
    A = sum(i * j for (i, j) in rs)
    if A < 100: continue
    if A > 999: break
  
    # fit the rectangles in a set of squares
    for ss in fit(rs, A):
      printf("n={n}, A={A} -> ss={ss}")
  

  Solution: The original number was 29.

  The rectangles cut out are:

  1× 1, 2, 3, …, 29
  2× 2, 3, …, 14
  3× 3, …, 9
  4× 4, 5, 6, 7
  5× 5

  With a total area of 882 cm².

  The 1×29 piece must fit into a square of size 29×29 or larger, but this is the largest square we can make, so there must be a 29×29 square, which leaves an area of 41 cm². This can be split into squares as follows:

  41 = 3² + 4² + 4²
  41 = 4² + 5²

  It turns out that it only possible to construct a packing using the second of these.

  I used the polyominoes.py library that I wrote for Teaser 2996 to assemble the rectangles into a viable arrangement of squares. It runs in 19 minutes. (The adapted program is here).

  Here is a diagram showing one way to pack the rectangles into a 4×4, 5×5 and a 29×29 square:

  

  LikeLike

  • 

    Frits 2:27 pm on 10 October 2020 Permalink | Reply

    @Jim,

    Wouldn’t it be easier to use the chosen number n as maximum dimension (line 23)?

    LikeLike

    • 

      Jim Randell 11:51 am on 11 October 2020 Permalink | Reply

      @Frits: Probably. When I started writing the program I was thinking about a constructive solution, that would produce a packing of the rectangles into the required squares. This is a cut-down version of the program which finds possible sets of squares to investigate – fortunately the solutions found all correspond to the same original number, so if there is an answer we know what it must be.

      And it turns out that we don’t need to examine the set of rectangles to determine the maximum dimension, so we could just pass it in. In fact we don’t need to collect the rectangles at all. Here’s a better version of the cut-down program:

      from enigma import irange, inf, divisors_pairs, printf
      
      # decompose t into squares
      def decompose(t, m=1, ss=[]):
        if t == 0:
          yield ss
        else:
          for k in irange(m, t):
            s = k * k
            if s > t: break
            yield from decompose(t - s, k, ss + [k])
      
      # find at least 3 potential squares with total area A
      # that can accomodate a rectangle with max dimension m
      def fit(A, m):
        for n in irange(m, A):
          a = A - n * n
          if a < 18: break
          # decompose the remaining area into at least 2 squares
          # with minimum dimension 3
          for ss in decompose(a, 3):
            if len(ss) > 1:
              yield ss + [n]
      
      # collect rectangles with increasing area
      A = 0
      for n in irange(1, inf):
        # add in rectangles of area n
        A += sum(i * j for (i, j) in divisors_pairs(n))
      
        # look for 3-digit total area
        if A < 100: continue
        if A > 999: break
      
        # find a set of squares with the same area
        for ss in fit(A, n):
          printf("n={n} A={A} -> ss={ss}")
      

      I did complete a program that finds a viable packing, but it takes a while to run (19 minutes).

      I’ll post the diagram with the answer later.

      LikeLike

      • 

        Frits 5:59 pm on 11 October 2020 Permalink | Reply

        @Jim, a nice solution with the divisor pairs.
        I think we can only form one 3×3 square at most (out of 3 possibilities).

        LikeLike

• 

  Frits 1:29 pm on 10 October 2020 Permalink | Reply

  I did a manual check to see if the reported squares can be formed in 2-D with the rectangular pieces.

   
  # select numbers from list <li> so that sum of numbers equals <n>
  def decompose(n, li, sel=[]):
    if n == 0:
      yield sel
    else:
      for i in {j for j in range(len(li)) if li[j] <= n}:
        yield from decompose(n - li[i], li[i:], sel + [li[i]])     
          
  # squares under 1000, square 2x2 can't be formed from rectangles                 
  squares = [n*n for n in range(3, 32)]
  
  rectangles = lambda n: [(i, j) for i in range(1, n + 1) 
                          for j in range(i, n + 1) if i * j <= n]
  
  area = lambda li: sum(i * j for (i, j) in li)
  
  # candidates with three-figure number area; area must be
  # at least largest square (i*i) plus the 2 smallest squares 9 and 16
  cands = lambda: {i: area(rectangles(i)) for i in range(7, 32) 
                   if area(rectangles(i)) in range(100, 1000) and
                      area(rectangles(i)) >= i * i + 25}
  
  # check if solution exist for candidates
  for (n, a) in cands().items(): 
    # biggest square should be at least n x n due to 1 x n piece
    for big in range(n, 32):
      # list of squares to consider (excluding the biggest square)
      sq = [x for x in squares if x <= a - (big * big) - 9]
      # select squares which together with biggest square will sum to area <a>
      for s in decompose(a - (big * big), sq):
        if len(s) > 1:
          print(f"number chosen = {n}, area={a}, squares={s + [big * big]}")
  

  LikeLike