Enigmatic Code
Programming Enigma Puzzles
Enigma 1715: Open the box
Posted by on 12 September 2012
From New Scientist #2882, 15th September 2012 [link] [link]
I started with a rectangular piece of card a whole number of centimetres long by a whole number of centimetres wide, one of those numbers being a prime. Then I cut out an identical small square from each corner of the card and discarded the four squares. I folded up the four “flaps” on the remaining piece of card to form an open-topped box, choosing the size of the cut squares so that the volume of this open box was the biggest possible. Having made the box, I found that the length of its rectangular base was four times its width.
What were the dimensions of the original piece of card?
[enigma1715]
Enigmatic Code 
The following Python does a bit of calculus to find solutions.
To check cards up to 300cm in size it takes 93ms.
from enigma import Primes, irange, sqrt, printf import sys # let's consider card up to 300cm max dimension MAX = 300 if len(sys.argv) < 2 else eval(sys.argv[1]) primes = Primes(MAX) # find cards of dimension a x b, where one side is a prime for b in irange(2, MAX): for a in range(1, b): # one of the values is a prime if not((a in primes) ^ (b in primes)): continue # if the squares cut from the corners are of side c # then the volume of the box is: # v = (a - 2c)(b - 2c)c # => v = 4c^3 - 2(a + b)c^2 + abc # to find the minimum we differentiate it: # dv/dc = 12c^2 - 4(a + b)c + ab # and this has roots at... p = 16 * pow(a + b, 2) q = 48 * a * b r = sqrt(p - q) c1 = (4 * (a + b) + r) / 24 c2 = (4 * (a + b) - r) / 24 for c in (c1, c2): # the square must fit on the card if not(0 < 2 * c < a): continue # to see if it's a maximum we check the second derivative: # d2v/dc2 = 24c - 4(a + b) d2 = 24 * c - 4 * (a + b) # which will be negative for a maximum if not(d2 < 0): continue # what is the ratio of the base of the box? r = (b - 2 * c) / (a - 2 * c) # is it (close enough to) 4? e = 1e-9 if not(4 - e < r < 4 + e): continue # OK, we've found a solution printf("a={a} b={b} c={c} r={r}")Solution: The card is 3 cm × 8 cm.
If you can’t do differentiation you can get the SymPy library to do it for you.
import sympy from enigma import Primes, irange, printf import sys # let's consider card up to 30cm max dimension MAX = 30 if len(sys.argv) < 2 else eval(sys.argv[1]) primes = Primes(MAX) c = sympy.symbols('c') # find cards of dimension a x b, where one side is a prime for b in irange(2, MAX): for a in range(1, b): # one of the values is a prime if not((a in primes) ^ (b in primes)): continue # if the squares cut from the corners are of side c # then the volume of the box is: v = (a - 2 * c) * (b - 2 * c) * c # to find the minimum we differentiate it: d = v.diff(c) d2 = d.diff(c) # and this has roots at... for x in sympy.solve(d, c): # the square must fit on the card if not(0 < 2 * x < a): continue # to see if it's a maximum we check the second derivative # which will be negative for a maximum if not(d2.subs(c, x) < 0): continue # what is the ratio of the base of the box? if (b - 2 * x) != 4 * (a - 2 * x): continue # OK, we've found a solution printf("a={a} b={b} c={x}")If you don’t know calculus here’s a solution that uses numerical approximations to find the maximum volume for the box. It runs in 215ms.
import sys from enigma import irange, Primes, printf MAX = 300 if len(sys.argv) < 2 else eval(sys.argv[1]) # volume of the box def volume(a, b, c): return (a - 2*c) * (b - 2*c) * c # find the max value of c between c1 and c2 (within e) def max_c(a, b, c1, c2, e): # chop the range into 5 d = (c2 - c1) / 4.0 while d > e: # which division has the highest value? c, mv, mc = c1, 0.0, 0.0 while not(c > c2): v = volume(a, b, c) if v > mv: mv, mc = v, c c += d # half the range d /= 2 # and centre it on the highest value so far c1, c2 = mc - d, mc + d return mc primes = Primes(MAX) # possible dimensions of the card (up to MAX) for b in irange(2, MAX): for a in range(1, b): # one of the values is a prime if not((a in primes) ^ (b in primes)): continue # find which c gives the maximum volume c = max_c(a, b, 0.0, float(a) / 2.0, 1e-9) # determine the ratio of the sides of the base of the box r = (b - 2 * c) / (a - 2 * c) # is it (close enough) to 4? if 4.0 - 1e-6 < r < 4.0 + 1e-6: printf("a={a} b={b} [c={c} r={r} v={v}]", v=volume(a, b, c))primes = [3,5,7,11,13,17,19] for a in primes: for b in range(3,20): if b not in primes: s=( (a+b) - (a*a+b*b-a*b)**0.5)/6 if b-2*s == 4*(a-2*s) or a-2*s == 4*(b-2*s): print a,b,sOnly the first turning point of the graph of volume vs. square length,s, needs to be considered, as the graph always has the form shown in this diagram:
Of course, I should have included 2 in the list of primes, but initially had assumed that the square length was restricted to being a whole number of centimetres.
Another way of approaching the problem is as follows:
Starting from the formula for volume, v = (a-2s)(b-2s)s , ( a,b are the sides of the original rectangle, s is the length of the square cut out from each corner),
The maximum volume is the first turning point of the function, i.e. the lower root of
dv/ds = 12s^2 -4(a+b)s + ab = 0
which is s= ( (a+b) – sqrt(a^2 + b^2 – ab) )/6
Assuming a<b, the lengths of the rectangular box is 4 times the width gives the equation
4(a-2s) = b-2s
produces the equation
sqrt(a^2 + b^2 – ab) = 2b – 3a
so (a^2 + b^2 – ab) is a perfect square. The solution can be found from this information with the following code:
primes = [2,3,5,7,11,13,17,19] squares = {n*n:n for n in range(1,20)} for (a,b) in [sorted((x,y)) for x in primes for y in set(range(1,20))-set(primes)]: d= a*a + b*b - a*b if d in squares and squares[d] == 2*b-3*a: print a,bOr even more simply, avoiding the need to generate a list of squares:
primes = [2,3,5,7,11,13,17,19] print [(a,b) for (a,b) in [sorted((x,y)) for x in primes for y in set(range(1,20))-set(primes)] if a*a + b*b - a*b == (2*b-3*a)**2]Or you can plug it into Wolfram Alpha [link] (I could get it to do the calculus separately, but not along with the other constraints), which tells you the solution is:
b = 8a/3, c = 2a/9
Additionally a and b must be positive integers and one of them must be prime.
From the formula for b it follows that a must be a multiple of 3 (as 8 is not divisible by 3), and b must be composite (as 8 is), hence a must be prime, and a multiple of 3.
So: a = 3, b = 8, c = 2/3.
You can do this in your head, doesn’t need any calculus. Start with base L = W/4. Height = h.
If you increment the small square, h goes up increasing volume. L goes down, decreasing volume by twice as much. W decreases volume by 4 times as much, so volume stays constant when h = 0.1L. That makes the card 1.2L x 0.45L, ratio of card sides 120/45 reduces to 8/3 one of which is prime
I think I see your argument, and it seems that this is a similar technique to differentiation from first principles. It’s been a long while since I did this at school, but I think you would formalise it like this:
At the maximum volume the base of the box is w × 4w and has height h.
So the volume is: v = w × 4w × h = 4w²h.
The dimensions of the card are: a = w + 2h, b = 4w + 2h, 0 < h < a/2.
If the height is changed by a small amount, e, the volume of the box becomes:
v' = (w − 2e) × (4w − 2e) × (h + e)
expanding:
v' = 4w²h − 10ewh + 4e²h + 4ew² − 10e²w + 4e³
So: (v' − v) / e = −10wh + 4eh + 4w² − 10ew + 4e²
As e tends to 0 this tends to the derivative: −10wh + 4w²
As the volume is at a maximum we set the derivative to zero, hence:
0 = 4w² − 10wh = 2w(2w − 5h)
As w is non-zero it follows that at the maximum 2w = 5h, hence: h = 2w/5.
So considering the ratio a : b:
a : b = w + 2h : 4w + 2h
= w + 4w/5 : 4w + 4w/5
= 9w/5 : 24w/5
= 3 : 8
and the solution follows.
Well done for being able to do this in your head!