Sunday Times Teaser 2660 – Oblonging
by Des MacHale
Using A4 sheets of card, I have made rectangles with dimensions in centimetres of 1 x 2, 2 x 3, 3 x 4 and so on up to a maximum size. I needed more than one A4 sheet to do this.
My family managed to lay out all these rectangles with no gaps or overlaps to form a larger rectangle that also had sides that differed by one centimtre.
How many rectangles did I make?
6 Comments
Leave one →
Brian – two thoughts:
(1) Line 1 – the largest possible card is 21×22 (I think the program assumes this).
(2) I think that the program may not exclude the possibility of a set of cards which has total area less than an A4 sheet but cannot be cut from one (I am sure that there is no such set which would give an alternative solution but it could apply to a set of 11 cards – I do not intend to check any more than I intend to check whether the solution oblong can really be made ! )
Hi Tony,
Sorry that comments were unintentionally closed – I have moved and slightly edited your comment. Yes, it should be 21 x 22 (I will change it).
On your second point, I understand your comment but I don’t believe that the puzzle setter had anything more in mind than the simple area check that I have implemented.
I have written a simple brute force program to cover rectangles with these cards but it is too slow to look for solutions for a 55 x 56 rectangle.
However, if we seek to cover rectangles with integral sides whose area is equal to the total of that of of the cards from 1 x 2 to N x (N + 1) inclusive, the only solutions I find for N less than 17 are for N = 3 (4 x 5) and N = 8 (15 x 16 – below).
I agree that the setter would not have expected many solvers to construct a 55×56 cover, although one would need to do so to prove that the solution N=20 is valid . I can only claim to have proved that there is at most one solution and N=20 is the only possibility.
I found easily (using a calculator) that the only solutions to 1/3{N(N+1)(N+2)} = M(M+1) with N at most 21 are N=1(trivially), 3, 8 and 20.
As it happens it is easy to show that solutions N=1, 3, and 8 give sets of cards which fit on an A4 sheet – you have gone a bit further by constructing a large rectangle.Your brute force program would been a convenient way to eliminate N=11 (with total area only slightly less than A4) if that had been a valid solution of the Diophantine equation.
I am intrigued that your brute force program is too slow for 55×56 and wonder whether you have any estimate of how long it would take.
I am vaguely aware that there is some theory on covering rectangles – I think it can be linked to the flow of heat/electricty in networks..
Its hard to estimate the time for a 55 by 56 rectangle but it took 30 minutes to show that there were no rectangles of any shape that would be covered by 17 of the cards. But, even though we only have to consider one target rectangle, my solver would probably still take tens of hours.
There is a lot of information of ‘bin packing’ with rectangles on the net and several algorithms that are much faster than brute force. I have just been trying several of these and none so far have given a solution for our puzzle with 20 cards. But they all apply heuristics and won’t necessarily give a solution even if one exists so I am tempted to leave my brute force solution running on an old machine as I think it might eventually get there.
I found another Python solution, which lists the number of rectangles with two factors for the cumalative area with sides differing by one centimeter:
Program Output
——————-
Number Area Side1 Side2
3 20 4 5
8 240 15 16
20 3080 55 56
34 14280 119 120