Enigmatic Code

Programming Enigma Puzzles

Enigma 100: Parkin in a cake-tin

From New Scientist #1244, 12th March 1981 [link]

Enigma 100Jessie makes parkin in a rectangular slab, but I store it in a round tin. She will make the rectangle in any proportions I specify. In the past I have specified 1 × 1 or 4 × 1. If it’s 4 × 1, I cut the slab in half and rearrange the two pieces as the sketch shows. In either case the proportion of the tin’s are filled is 2/𝜋: about 0.6366.

Parkin keeps best if the tin is as full as possible, and I have been wondering if I could improve on that proportion of 0.6366, by specifying a differently proportioned slab. Can you help me?

You can’t put one piece on top of another. And you are allowed only to make one straight cut in the slab before putting the pieces in the tin.

How many times the width of the slab should I ask Jessie to make its length?

[enigma100]

Advertisements

2 responses to “Enigma 100: Parkin in a cake-tin

  1. Jim Randell 18 June 2013 at 10:15 am

    By considering fitting half the parkin in a semicircular tin, we see that a 4:1 block of parkin does indeed yield a usage of 2/𝜋 (≈ 0.6366), but immediately this can be improved on by adding an extra triangle of parkin on one end (so the original slab would be cut obliquely).

    Enigma 100 - Diagram 1

    This increases the usage of the tin to (2 + (√2 – 1))/𝜋 (≈ 0.7025) and requires the length of the original slab of parkin to be 3 + √2 (≈ 4.414) times its width.

    But this isn’t the maximum possible usage for this arrangement. By considering the arrangement with a variable sized rectangular block:

    Enigma 100 - Diagram 2

    we determine that the usage of the minimally sized circular tin is:

    u = \frac{3x\; +\; \sqrt{x^{2}+1}}{\pi \left( x^{2}+1 \right)}

    the graph of which looks like this:

    Enigma 100 - Graph

    We can find the maximum of this expression numerically (using the find_max() function from my enigma.py library), which takes 40ms:

    from enigma import pi, sqrt, find_max, printf
    
    # usage
    u = lambda x: (3 * x + sqrt(x * x + 1)) / (pi * (x * x + 1))
    
    # find the maximum usage
    m = find_max(u, 0.0, 2.0)
    
    # the ratio of width to height is then...
    x = m.v
    w = 3 * x + sqrt(x * x + 1)
    
    printf("max usage = {m.fv}, ratio = {w}")
    

    or symbolically (using the SymPy library), which takes 684ms:

    from sympy import symbols, sqrt, pi, solve
    from enigma import printf
    
    x = symbols('x')
    
    r = 3 * x + sqrt(x * x + 1)
    u = r / (pi * (x * x + 1))
    
    d = u.diff()
    d2 = d.diff()
    
    # find inflection points
    for s in solve(d, x):
      # at the maximum d2 will be negative
      if not(d2.subs(x, s) < 0): continue
      # calculate the maximum usage
      m = u.subs(x, s).simplify()
      printf("max usage = {m} = {f}", f=float(m))
      # and the ratio of width to height
      sr = r.subs(x, s).simplify()
      printf("ratio = {sr} = {f}", f=float(sr))
    

    to get the following result (which is the published solution, although I haven’t shown there isn’t a different cutting strategy which might give a better packing, but I don’t think there is):

    Solution: The original parkin slab should be 3.711 times its width. The exact value is calculated from the following formula:

    r = \sqrt{\frac{1}{2}\left( 19\; +\; \sqrt{73} \right)}

    This uses 0.7144 of the tin. The exact value is given by the following formula:

    u = \frac{4\left( 3\sqrt{19\; -\; \sqrt{73}}\; +\; \sqrt{35\; -\; \sqrt{73}} \right)}{\pi \left( 35\; -\; \sqrt{73} \right)}

  2. Hugh Casement 4 July 2015 at 2:36 pm

    If we rename your √(x² + 1) as r, and your x as √(r² – 1), the result is the same, of course, but it allows us to see a bit more easily how the dimensions of the slab compare with the radius r of the tin (which is less easy to vary in practice).

    If we bake a slab of dimensions ½√3 ≈ 0.866 times r by 3r, a ratio of √12 ≈ 3.4642, and if it is permitted to make three straight cuts, then the resulting four pieces fit together in a hexagon, with a packing factor of 1.5√3/π ≈ 0.827.

    I made a diagram almost as pretty as yours, but don’t see how to upload it.
    Imagine a hexagon inscribed in a circle and divided along the x and y axes.

    Does anyone have a recipe for parkin?

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: