Enigmatic Code

Programming Enigma Puzzles

Enigma 1715: Open the box

From New Scientist #2882, 15th September 2012 [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]

Advertisements

10 responses to “Enigma 1715: Open the box

  1. Jim Randell 12 September 2012 at 7:39 pm

    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.

    • Jim Randell 12 September 2012 at 10:21 pm

      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}")
      
      • Jim Randell 14 September 2012 at 7:05 pm

        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))
        
  2. arthurvause 12 September 2012 at 9:49 pm
    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,s
    
    • arthurvause 13 September 2012 at 7:04 pm

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

  3. arthurvause 14 September 2012 at 8:29 am

    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,b
    
    • arthurvause 14 September 2012 at 9:37 am

      Or 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]
      
  4. Jim Randell 14 September 2012 at 10:57 am

    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.

  5. Ogee 19 September 2012 at 5:18 pm

    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

    • Jim Randell 20 September 2012 at 9:21 am

      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!

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: