S2T2

Jim Randell 4:39 pm on 16 February 2024 Permalink Reply
Tags: by: Howard Williams ( 42 ), flawed ( 52 )   

• 

  Jim Randell 4:59 pm on 16 February 2024 Permalink | Reply

  Note: See my comment below for a better program that solves the intended puzzle (and can also be used to find the multiple solutions for the original puzzle where the plate can have non-integer sizes).

  If the coins have diameter of 1, then in hexagonal packing the distance between the centres of alternate rows is (√3)/2.

  This Python program considers increasing sized squares until we achieve an 8% better yield from hexagonal packing vs. square packing.

  It runs in 56ms. (Internal runtime is 342µs).

  Run: [ @replit ]

  from enigma import (irangef, inf, intf, divf, sqrt, printf)
  
  r34 = sqrt(3, 4)
  
  # pack the coins in a square of side <x>
  # return (<number in square packing>, <number in hex packing>)
  def pack(x):
    n = intf(x)  # number of rows in square packing
    ns = n * n
    h = divf(x - 1, r34) + 1  # number of rows in hex packing
    nh = n * h
    if x % 1 < 0.5: nh -= divf(h, 2)
    return (ns, nh)
  
  # consider increasing sheet size
  for x in irangef(1.0, inf, step=0.01):
    if not (x % 1 < 0.5): continue
    (ns, nh) = pack(x)
    # does hex packing give 8% more coins? (nh/ns = 1.08)
    if 100 * nh == 108 * ns:
      printf("{d} additional coins [x={x:.2f}: ns={ns} nh={nh}]", d=nh - ns)
      break
  

  Solution: [see my comment below]

  LikeLike

  • 

    Frits 12:31 pm on 17 February 2024 Permalink | Reply

    @Jim, as must be a divisible by 25 I thought you would use a different step.

    The puzzle doesn’t ask for the first solution (you use “break”).
    I am always in favour of exploring the full solution space. I still have to figure out if we can use a break based on logic

    LikeLike

    • 

      Jim Randell 12:55 pm on 17 February 2024 Permalink | Reply

      @Frits: You can remove the [[ break ]] to look for further solutions. But eventually you reach a point where the hexagonal packing is always better than an 8% improvement so you can stop then (without finding any further layouts – although there is a range of square sizes that give the required solution).

      LikeLike

• 

  NigelR 9:35 am on 18 February 2024 Permalink | Reply

  It seems odd – bordering on bizarre – that, to make this teaser work in the way that most seem to be interpreting it, you have to assume that the original sheet is bigger than it needs to be by 0.33 of the coin diameter, or some 6.6%. By extension, and also noting that the puzzle is curiously worded: ‘… by shifting some rows…’ rather than: ‘…by shifting alternate rows..’, there are several solutions possible. For example, strictly consistent with the teaser as worded and using the same assumption, there is a valid solution for a much larger plate but leaving the first n rows unchanged. Only the last few rows are shifted, with a full row being added on the bottom. This yields the same required increase in coin number, but with the original sheet being oversized by a smaller percentage!

  LikeLike

  • 

    Jim Randell 9:53 am on 18 February 2024 Permalink | Reply

    @NigelR: Would that be “best that can be done” with that size of square though?

    I supposed the size of square depends on the pressing machine rather than the coins, as it may be used to make coins of several different sizes. And presumably the unused metal is then recycled into new plates.

    LikeLike

    • 

      NigelR 11:10 am on 18 February 2024 Permalink | Reply

      @Jim: Point taken – while my scheme would yield the right gain in coin number, it would not be optimal so is not a valid solution. I’m still troubled by the apparently arbitrary size of the original plate….!!

      LikeLike

• 

  Frits 10:43 am on 18 February 2024 Permalink | Reply

  I followed the same method as Jim and Brian but am not convinced that this is a correct approach as the wording of the puzzle isn’t fully clear to me.

  from fractions import Fraction as RF
  
  # final number of coins = 27/25 * n^2 so n must be a multiple of 5
  n = 5
  while True:
   
    # final situation: m rows with m * n - m / 2 coins and m > n
    # (starting with a row of n coins followed by a row of n - 1 coins, etc)
  
    # we may have a solution if m * n - m / 2 equals 1.08 * n^2
    # or m = (54 * n^2) / (50 * n - 25)
    # or m = 1.08 * n + 27 / (100 * n - 50) + 0.54
  
    # assume diameter coin is 1
    # height of <m> packed rows: 1 + (m - 1) * sqrt(0.75)
    # squeeze as many rows as possible (sheet is less than (n + 1) x (n + 1):
    # n + 1 - sqrt(0.75) <= height of m rows < n + 1
   
    # n + 1 - sqrt(0.75) <= 1 + (m - 1) * sqrt(0.75) < n + 1
   
    # n <= m * sqrt(0.75)
  
    # as 1.08 * sqrt(0.75) < 1 every increment of 1 of n will result in
    # an increment of the height of less than 1
    # thus as soon for a certain <n> the height is less than <n> we can
    # stop processing
  
    # final number of rows
    m = RF(54 * n**2, 50 * n - 25)
    # whole number of rows?
    if m.denominator == 1:
      # if we can't squeeze in one more row
      if n + 1 - 3**.5 / 2 <= (h := 1 + (m - 1) * 3**.5 / 2) < n + 1:
        print(f"answer: {m * n - m // 2 - n**2} coins")
   
    # when can we stop processing?
    if not (2 * n <= m * 3**.5):
      break
  
    n += 5
  

  LikeLike

• 

  Pete Good 5:40 pm on 19 February 2024 Permalink | Reply

  Jim,
  I solved this teaser analytically by deriving two quadratic equations for the number of coins pressed after Newton’s change. The first equation assumes that an even number of rows can be pressed and the second one assumes that an odd number of rows can be pressed. The first quadratic equation has a whole number solution and the second has none. The solution follows directly from this result.

  LikeLike

• 

  Jim Randell 12:58 pm on 20 February 2024 Permalink | Reply

  It seems the way the setter intended the puzzle to work is that that square plate is an exact number of coin diameters across, and the alternate packing consists of some (but not necessarily every other) shifted, shorter rows.

  I have added a note to the puzzle text.

  LikeLike

  • 

    Jim Randell 1:40 pm on 20 February 2024 Permalink | Reply

    Here is a Python program that solves the intended puzzle:

    Run: [ @replit ]

    from enigma import (Accumulator, irange, irangef, inf, sqrt, intf, divf, printf)
    
    r3 = sqrt(3)
    
    # consider increasing sheet size
    for x in irangef(1.0, inf, step=1.0):
      n = intf(x)
      ns = n * n  # square packing
    
      # find maximal packing for some shifted rows
      acc = Accumulator(fn=max)
      f = x % 1
      # max number of rows in hex packing
      m = divf(x - 1, 0.5 * r3) + 1
      # consider the number of shifted rows
      for s in irange(0, divf(m, 2)):
        # calculate the number of unshifted rows we can fit in
        u = s + intf(x - 1 - s * r3) + 1
        nh = u * n + s * (n - 1 if f < 0.5 else n)
        acc.accumulate_data(nh, (u, s))
      (nh, (u, s)) = (acc.value, acc.data)
    
      # can we fit in 8% more coins?
      if 100 * nh == 108 * ns:
        printf("{d} additional coins [x={x:.2f} u={u} s={s}: ns={ns} nh={nh}]", d=nh - ns)
        break
    

    Solution: 32 additional coins per plate can be produced.

    If the coins have diameter 1 and the plate measures 20 × 20, then the original square packing produces 400 coins per sheet.

    However, by shifting 8 of the rows, we have room for 2 more unshifted rows, for a total of 432 coins, and this is an 8% increase over the original packing.

    

    And this is the only solution if the size of the plate is constrained to be an exact multiple of the coin diameter.

    ---

    However if size of the plate is not so constrained there are 2 further solutions.

    If we change the step at line 6 to allow non-integer square sizes (and remove the break statement), we can find the three sizes of square that give us a possible solution. The smallest is that found by my original program, and the largest is an integer sized square that gives the intended answer.

    Here is a diagram of square packing and hexagonal packing with a 5.4 × 5.4 sheet:

    

    This is a full hexagonal packing, where every other row is shifted (and this was how I originally interpreted the puzzle, and was the solution found by my original program above).

    We get 25 coins/sheet using square packing and 27 coins/sheet using hexagonal packing, an 8% increase.

    The minimal size square that gives this configuration is: (5√3)/2 + 1 ≈ 5.3301…

    But for squares of size 5.5 or larger the alternate rows in the hexagonal packing do not have to be reduced by one coin (as specified by the puzzle text). So the square size must be in the range 5.33… < x < 5.50.

    ---

    And with a 10.47 × 10.47 square, the square packing gives 100 coins, but by shifting 2 rows we have room for an extra row:

    

    This alternate packing has 108 coins, which is also an 8% increase.

    LikeLike