Sunday Times Teaser 3029 – Square Jigsaw
by Victor Bryant
Published Sunday October 11 2020 (link)
I chose a whole number and asked my grandson to cut out all possible rectangles with sides a whole number of centimetres whose area, in square centimetres, did not exceed my number. (So, for example, had my number been 6 he would have cut out rectangles of sizes 1×1, 1×2, 1×3, 1×4, 1×5, 1×6, 2×2 and 2×3.) The total area of all the pieces was a three-figure number of square centimetres.
He then used all the pieces to make, in jigsaw fashion, a set of squares. There were more than two squares and at least two pieces in each square.
What number did I originally choose?
6 Comments
Leave one →
This gives possible solutions but doesn’t prove that the squares can actually be constructed.
Here is one of many solutions.
Lovely recursive function. I found that it is possible to remove the ‘if’ statement at line eleven by substituting ‘x’ for ‘mns’ in line 13:
yield from sum_sqs(area – x * x, x, mxs, sq + (x,))
The ‘sorted’ in line 18 seems redundant. Relic from an earlier version where all the rectangles were printed out?
How did you do the 29×29 puzzle? Manually or Pythonically? Either way it’s impressive.
Thanks John,
That is a simplification and it is also possible to avoid calculating area – x * x twice (see my update above). The rectangle sort was useful in debugging but, as you say, it serves no other purpose.
I found the 29×29 square with a program. Fitting shapes inside other shapes comes up a lot so I have a standard bit of code for doing this.
Even better!
BTW I won’t be posting my smoke-belching, coal-fired code this week.
Brian
Does your fitting program produce and/or count all possible essentially different tilings?
How long does it take to run?
Have you got a program to colour the square with 4 colours to illustrate the 4-Colour Theorem?
It takes about eight minutes to find one solution. It does not count solutions and I don’t have a program for allocating colours. EDIT I have now recoded it and the run time per solution is down to a few seconds.