### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,270)
- misc (3)
- project euler (2)
- puzzle (67)
- site news (50)
- tantalizer (69)
- teaser (7)

### Site Stats

- 206,371 hits

Programming Enigma Puzzles

10 August 2018

Posted by on **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]

%d bloggers like this:

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×ktiles for the odd numbers and2×ktiles 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×nrectangle, and the tiles for the composite numbers (4, 6, 8) are not formed from1×kstrips.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×kblock, 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 ]Solution:You started with 28 stamps (in a 4×7 block) or 36 stamps (4×9 block).The published solution is 36 stamps.