# Sunday Times Teaser 2806 – Jack’s Jigsaw

*by Des MacHale*

#### Published: 3 July 2016 (link)

I made Jack a jigsaw. I started with a rectangle of card that I had cut from an A4 sheet and then I cut the rectangle into pieces. There were some square pieces of sizes (in centimetres) 1×1, 2×2, 3×3 … with the largest having side equal to Jack’s age. The remaining pieces were rectangles of sizes 1×2, 2×3, 3×4, … with the largest length amongst them again being Jack’s age. Then Jack succeeded in putting them together again to form a rectangle, but the perimeter of his rectangle was smaller than the perimeter of my original rectangle.

What were the lengths of the sides of my original rectangle?

5 Comments
Leave one →

Here are two (of many) arrangements for the two rectangles:

Hi Brian,

What is the simplest & quickest way for me to be able to use Mathjax here or in any text editor?

Hi Trevor,

MathJax is enabled on this site so all you have to do it is use a backslash character followed by an opening ‘(‘ to enable a Latex expression and then close the expression with a backslash and a closing ‘)’. This is for inline expressions, for example, \(e=mc^2\) but square brackets can be used instead to give display expressions, for example, \[\sin^2 x + \cos^2 x \equiv1\] ou need to know Latex but there is a lot of useful material on the web to help with this (see for example this). I find it takes quite a bit of editing, which is fine for me as I have full access. And, although I have comment editing enabled, the editor messes up MathJax code by removing the backslashes and I haven’t yet found a solution for this. But if you try it and it fails, I will be able to correct it for you. Do let me know if I can offer further help.

Original card = x * y (x < 30, y < 22)

(i) 1×1 + 2×2 + 3×3 + …. + nxn = \(\sum_{i=1}^n i^2 = n(n+1)(2n+1)/6\)

(ii) 1×2 + 2×3 + 3×4 + ….+ (n-1)xn = \(\sum_{i=2}^n (i^2 – i) = \sum_{i=2}^n i^2 – \sum_{i=2}^n i = (n-1)n(n+1)/3\)

Now (i) +(ii) gives x * y = \(n(n+1)(4n-1)/6\), where n = Jack’s age.

So here is my simple code to find equal areas and different perimeters:

And here is the output:

10 5 4 50 15

19 5 5 95 24

23 7 6 161 30

28 9 7 252 37

21 12 7 252 33

18 14 7 252 32

25 21 9 525 46

We need a value of n (for Jack) that gives at least two different rectangles, which means that n is equal to 7 with three possible rectangles. However, since none the 5 largest pieces can pair along the shortest side of the 28 x 9 rectangle, they must lie side by side along its longest side. But this is impossible because their minimum width is 29. This hence leaves the 21 x 12 rectangle (perimeter 66cm) as the original card and the 18 x 14 rectangle (perimeter 64cm) as Jack’s rearrangement.

Another way of tackling this sort of problem is to treat it as an Exact Cover problem for which Donald Knuth introduced an efficient algorithm which he calls Dancing Links (DLX).

David Goodger provides two implementations of the DLX algoriithm in his PolyForm Puzzler application, both of which can be used to solve this teaser but they are relatively slow. Fortunately, however, Kenneth Waters has developed a Python extension here that provides a consdierable improvement in speed. Here is solution for this puzzle that uses this extension.

It solves the teaser in less than a second and is fast enough to find all the different ways of fitting the pieces into the two rectangles – 20624 solutions for the 12 x 21 rectangle and 5228 for the 14 x 18 rectangle.