Enigmatic Code

Programming Enigma Puzzles

Enigma 460: Tear me off a strip

From New Scientist #1611, 5th May 1988 [link]

I had a rectangular block of stamps four stamps wide. I tore off one stamp. Then I tore off two stamps. Then I tore off three stamps, and so on, and so on. Each time, the stamps which I tore off formed a rectangle of their own, in one piece. And, following this pattern, the last piece I required (which needed no tearing off because it exhausted my supply of stamps) was also a rectangle. And only when I was forced to was any of these rectangles a strip one stamp wide. (So, for example, the four stamps and the subsequent non-primes were not in thin strips).

Each time, after tearing off the stamps, the remaining stamps were in one piece and formed either a rectangle or an L-shaped piece.

How many stamps did I start with?

[enigma460]

One response to “Enigma 460: Tear me off a strip

  1. Jim Randell 10 August 2018 at 8:21 am

    I think there is more than one solution to this puzzle, but I still found it quite fun to solve.

    If we consider a slightly different problem, that of laying out a set of tiles with area 1, 2, 3, 4, 5, … into a contiguous area such that the resulting block is always rectangular, we find that by using 1×k tiles for the odd numbers and 2×k tiles for the even numbers we can add the odd numbers to the bottom of the existing rectangle, and add the even numbers to right side of the rectangle. Giving us a layout like this:

    (To continue the pattern we would place a 1×9 tile along the bottom, then a 2×5 tile on the right, and so on).

    We can see from this that both the rectangle formed from the 1-7 tiles and the rectangle formed from the 1-8 tiles is a 4×n rectangle, and the tiles for the composite numbers (4, 6, 8) are not formed from 1×k strips.

    So if we start with a 4×7 rectangle of stamps and tear off collections of stamps corresponding to the tiles in the diagram, the remaining block of stamps will always be L-shaped, until we finish by separating the blocks of 6 and 7 stamps.

    Similarly, if we start with a 4×9 rectangle of stamps, we can tear off collections until we separate the blocks of 7 and 8 stamps.

    So this gives us two possible solutions to the puzzle: 28 stamps in a 4×7 block (7 tiles), and 36 stamps in a 4×9 block (8 tiles).

    We also see that as blocks of stamps are torn off, the total number of stamps we have removed forms the sequence of triangular numbers: 1, 3, 6, 10, 15, 21, 28, 36, …

    And so we can only have started with a rectangular block of stamps that is 4 stamps wide when these numbers are divisible by 4: T(7)=28, T(8)=36, T(15)=120, T(16)=136, T(23)=276, T(24)=300, …

    Also, for composite numbers, we cannot use a tile that is a single stamp wide in one dimension. So by the time we get to tearing off a block of 25 stamps we are trying to remove a 5×5 block, but this is not possible from a 4×k block, so the numbers of blocks we can remove are limited to those given above: 7, 8, 15, 16, 23, 24.

    The following Python 3.6 program tries to find a solution using all possible blocks of stamps, and verifies that only the 7 tile and 8 tiles solution given above are possible. It considers 72 different collections of tiles in total. Run time is 1.28s.

    Run: [ @repl.it ]

    from itertools import count, product
    from enigma import divisors_pairs, filter2, unpack, irange, first, join, printf
    
    # is the region of the grid <g> defined by the value <v> rectangular?
    def is_rectangular(g, v):
      bounds = None
      # consider each row
      for r in g:
        # find indices containing v
        js = list(j for (j, x) in enumerate(r) if x == v)
        if js:
          # there are values on this row
          if len(js) + js[0] == js[-1] + 1:
            # indices are consecutive
            if bounds:
              # bounds don't match existing bounds
              if bounds != (js[0], js[-1]): return False
            else:
              # set the bounds
              bounds = (js[0], js[-1])
          else:
            # indices are not consecutive
            return False
        else:
          # there are no values on this row
          if bounds is not None:
            bounds = (-1, -1)
      # looks OK
      return True
    
    # update the grid at (i, j) placing a tile (a, b) turning v to u
    def update(g, i, j, a, b, v, u):
      g = list(g)
      for p in irange(i, i + a - 1):
        r = list(g[p])
        for q in irange(j, j + b - 1):
          if r[q] == v:
            r[q] = u
          else:
            return None
        g[p] = r
      return g
    
    # place tile <ts> into grid <g>
    def solve(g, ts, ps=[]):
      if not ts:
        yield ps
      else:
        # place the next tile (in some orientation)
        for (a, b) in set([ts[0], ts[0][::-1]]):
          for (i, r) in enumerate(g):
            for (j, v) in enumerate(r):
              if v == 0 and not(i + a > len(g)) and not(j + b > len(r)):
                g1 = update(g, i, j, a, b, 0, 1)
                if g1 and (is_rectangular(g1, 0) or is_rectangular(g1, 1)):
                  yield from solve(g1, ts[1:], ps + [(a, b, i, j)])
    
    # possible tiles
    tiles = list()
    # total area
    t = 0
    # consider tile with n squares
    for n in count(1):
      # find possible tile shapes
      ts = list(divisors_pairs(n))
      # if possible don't use tiles with dimension 1
      if len(ts) > 1: ts.pop(0)
      # remove tiles that won't fit in the grid
      (_, ts) = filter2(unpack(lambda a, b: a > 4), ts)
      # stop if there are no possible tiles for n
      if not ts: break
      tiles.append(ts)
      # calculate area
      t += n
      (k, r) = divmod(t, 4)
      if r != 0: continue
      # try to solve the grid
      printf("[n={n}] t = {t} = 4x {k}")
      for ts in product(*tiles):
        g = list([0] * k for _ in irange(0, 3))
        # place the 1x1 tile in the top left corner
        g[0][0] = 1
        # find the first solution for this set of tiles
        ss = first(solve(g, ts[1:], [(1, 1, 0, 0)]))
        if ss:
          # output the solution
          for s in ss:
            printf("{n} tiles, 4x {k} grid -> ({ts})", ts=join((f"{a}x{b}" for (a, b) in ts), sep=", "))
            printf("-> {s}", s=join((f"{a}x{b} @({x},{y})" for (a, b, x, y) in s), sep=", "))
          # we're done with this number of tiles
          break
    

    Solution: You started with 28 stamps (in a 4×7 block) or 36 stamps (4×9 block).

    The published solution is 36 stamps.

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: