### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 177,959 hits

Advertisements

Programming Enigma Puzzles

18 November 2012

Posted by on **From New Scientist #2653, 26th April 2008**

Dick has a box of rectangular tiles. Each is a different size, the dimensions being 1 × 3, 2 × 4, 3 × 5, 4 × 6 and so on.

He takes some tiles out of the box, first the 1 × 3, then the 2 × 4, then the 3 × 5, and so on, with the aim of fitting together all those that he has taken into a rectangle that has no gaps and no overlaps.

Assuming he takes more than one tile out of the box, how many tiles must he take out to create (a) the smallest possible rectangle, and (b) the next smallest possible rectangle?

[enigma1491]

Advertisements

%d bloggers like this:

This is a slightly different approach from my original Perl program that I wrote when the puzzle came out [link]. It’s shorter and faster and runs (under PyPy) in 9.2s. If I’d started off using this approach I probably wouldn’t have bothered writing the C version.

Solution:(a) 9 tiles; (b) 11 tiles.The solution for 9 tiles is a 15×25 grid (for example):

And for 11 tiles it is a 22×29 grid (for example):

If you stop the program from returning as soon as it has found a solution the program finds 336 possible tilings for the 15×25 grid and 64 possible tilings for the 22×29 grid (although this takes no account of symmetrical solutions, so you can divide these numbers by 4 to get the number of essentially different solutions – 84 for the 15×25 grid and 16 for the 22×29 grid).

The next smallest two possible tilings are both with 14 tiles and are for a 25×49 grid and a 35×35 grid.