1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
solutions = [] for n in range(2, 40): # the cumulative area of n rectangles ca = n * (n + 1) * (n + 2) // 3 for d in range(2, ca): # find two factors of ca differing by one if ca % d == 0 and ca == d * (d + 1): solutions.append((n, ca, d, d + 1)) print("Number Area Side1 Side2") for a in solutions: print('{0[0]:>6d}{0[1]:>7d}{0[2]:>6d}{0[3]:6d}'.format(a)) |

Program Output

——————-

Number Area Side1 Side2

3 20 4 5

8 240 15 16

20 3080 55 56

34 14280 119 120

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 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..

]]>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).

]]>(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 ! ) ]]>

1 2 3 4 5 6 7 8 9 10 11 12 |
# the dimensions of the largest possible card is 21 x 22 cm for max_card in range(1, 22): # the total area of cards up to size max_card x (max_card + 1) area = sum(i * (i + 1) for i in range(1, max_card + 1)) # this area is larger than that of an A4 sheet if area > 21 * 30: # solve width * (width + 1) = area for the width value width = (round((4 * area + 1) ** 0.5) - 1) // 2 if width * (width + 1) == area: print('{:d} cards were made.'.format(max_card)) |