**From New Scientist #2407, 9th August 2003** [link]

It is day 10 of Frances’s holiday and she is cutting rectangles out of cardboard. She is cutting out every rectangle with whole number sides and area at most 10.

When she has finished she has 15 rectangles, which are:

1×1, 1×2, 1×3, 1×4, 2×2, 1×5, 1×6, 2×3, 1×7, 1×8, 2×4, 1×9, 3×3, 1×10, 2×5.

Frances then tries to fit the 15 pieces together to make a square, with no overlapping pieces and no holes. She finds it is impossible. In fact she tried a similar thing on day 2 of her holiday with all rectangles of area at most 2, on day 3 with area at most 3, …, on day 9 with area at most 9; on each day she found it was impossible to make a square.

Frances continues through her holiday, on day 11 with area at most 11, on day 12 with area at most 12, and so on. Each day she finds it impossible to make a square until one memorable day when she finds it is possible.

Which day of the holiday was that memorable day?

[enigma1251]

### Like this:

Like Loading...

It’s straightforward to find on what day it may be possible to assemble the rectangles into a square, which is what this program does. It runs in 34ms.

Solution:The memorable day was the 43rd day of the holiday.There are 88 rectangles and they would make a 46×46 square.

The program finds when it

maybe possible to assemble the rectangles into a square, but doesn’t actually show that it is possible.I tried to use a variation of my program for

Enigma 17to find a packing of the rectangles into the square, but it took too long.Then I discovered that Eric Huang, one of the authors of several papers on Optimal Rectangle Packing, has made his C++ rectangle packing code available at [ https://code.google.com/p/rectpack/ ], so I downloaded it, got it to compile, and give it this packing problem to chew on, but it didn’t find a solution in a reasonable time either.

Nevertheless, here is an arrangement that shows it is possible.

(and of course any rectangular region of this solution that consists of two or more rectangles can be rearranged to give a further solution, and chunks that form a block the full width (or height) of the square can be moved)).

A heuristic packer may find a solution, or if you sneakily feed the rectangles to my packer in the order and orientation given above it will find a solution. But neither of these is really satisfactory.

If you leave the program above running you will find that the days where the total area of all rectangles is a square number follow the following sequence:

The sides of the corresponding squares are:

Eric Huang’s optimal rectangle packer (rectpack) will pack the top 20 rows of the solution given above instantaneously. I’ve been running it over the bottom 26 rows (using a Virtual Machine, so I can run it overnight and then suspend it during the day when I want to use my laptop) for a while and it has come up with an alternative packing, after using 10d09h52m56s (just short of 250 hours) of CPU time.

Here’s the packing it found:

Now I’ll try it on the full problem, and report back if it finds a packing.

Here is my version, extended to give the sequences that Jim describes above. It uses a standard number theory function that is implemented in my number theory library (which is available at http://ccgi.gladman.plus.com/wp/?page_id=1500 – you will need the latest version as earlier versions have an issue that will affect this enigma).

As implemented the program will take several minutes to produce: