S2T2

Jim Randell 9:28 am on 6 June 2021 Permalink Reply
Tags: by: Peter Harrison ( 6 )   

• 

  Jim Randell 9:29 am on 6 June 2021 Permalink | Reply

  For a quadrilateral with given sides, the maximal area occurs when the quadrilateral is cyclic, and is given by the formula:

  A = (1/4)√((−a + b + c + d)(a − b + c + d)(a + b − c + d)(a + b + c − d))

  (Which is a generalisation of Heron’s Formula, known as Brahmagupta’s formula).

  We are interested in cases where: A = 2000.

  Which means were are interested in when:

  (−a + b + c + d)(a − b + c + d)(a + b − c + d)(a + b + c − d) = 64000000

  And as each of a, b, c, d are integers, so are the terms on the LHS, so we can consider factorisations of the RHS into 4 integer factors, and then solve the resulting 4 equations to give us candidate side lengths.

  The [[ divisor_tuples() ]] function is borrowed from Enigma 1062.

  This Python program runs in 162ms.

  from enigma import (divisors_pairs, matrix, as_int, seq_all_different, printf)
  
  # find ordered k-tuples that multiply to give n
  def divisor_tuples(n, k, s=[]):
    if k == 1:
      if not (s and n < s[-1]):
        yield s + [n]
    else:
      for (a, b) in divisors_pairs(n):
        if not (s and a < s[-1]):
          yield from divisor_tuples(b, k - 1, s + [a])
  
  # find maximal quadrilateral with area A
  def solve(A):
    # coefficients of a, b, c, d in the factors
    eqs = [
      (-1, +1, +1, +1),
      (+1, -1, +1, +1),
      (+1, +1, -1, +1),
      (+1, +1, +1, -1),
    ]
    # factorise (4A)^2
    for fs in divisor_tuples(16 * A * A, 4):
      # and solve the equations (for positive integers)
      try:
        ns = list(as_int(x, '+') for x in matrix.linear(eqs, fs))
      except ValueError:
        continue
      else:
        yield sorted(ns)
  
  # collect solutions consisting of different integers
  ss = sorted((ns for ns in solve(2000) if seq_all_different(ns)), key=sum)
  
  # output solutions
  for ns in ss:
    printf("{ns} -> {t}", t=sum(ns))
    break  # we only need the smallest solution
  

  Solution: The first quadrilateral has sides of length: 5 cm, 55 cm, 65 cm, 85 cm.

  The minimal perimeter is 210 cm, and the sides are all multiples of 5cm. One possible quadrilateral with these side lengths looks like this:

  

  This is the collection of side lengths with the smallest perimeter. But the program finds 8 possible collections (ordered by perimeter):

  210: (5, 55, 65, 85)
  240: (20, 40, 70, 110)
  288: (16, 19, 119, 134)
  294: (22, 47, 83, 142)
  308: (26, 29, 104, 149)
  330: (5, 40, 125, 160)
  486: (43, 83, 118, 242)
  504: (2, 124, 127, 251)

  If the setter choose the next smallest perimeter for Teasers 2001 – 4000, the quadrilateral will have sides: 20 cm, 40 cm, 70 cm, 110 cm (perimeter = 240 cm), which are all multiples of 10 cm.

  LikeLike

• 

  Hugh Casement 10:01 am on 6 June 2021 Permalink | Reply

  I reckon to have found a near-solution with a shorter perimeter.
  If a = 39, b = 42, c = 47, d = 52, then the perimeter is 180 and the area is about 2000.008 units.
  It takes only a very slight deviation from cyclic to reduce that to 2000.

  LikeLike

  • 

    Jim Randell 10:32 am on 6 June 2021 Permalink | Reply

    For all practical purposes this is a viable answer (and a nicer looking quadrilateral).

    If I’ve calculated correctly you would have to be able to measure and cut the wooden strip to an accuracy of about 2e-14 cm to disallow this. Which I think is about 1/1000000 th the width of an atom.

    LikeLike

• 

  GeoffR 5:38 pm on 6 June 2021 Permalink | Reply

  I tried a brute force solution in MiniZinc, experimenting with the upper bound value of the four sides.

  I found setting an upper bound of 150 produced four out of five of Jim’s smallest perimeter solutions, but missed the perimeter of 294. It did, however, find the same two lowest perimeters of 210 and 240.

  I found the Chuffed Solver was necessary to run it satisfactorily, and it took several seconds to run.

  % A Solution in MiniZinc
  include "globals.mzn";
  
  var 1..150:a; var 1..150:b; var 1..150:c; var 1..150:d; 
  constraint all_different([a, b, c, d]);
  
  % Using Jim's version of the Brahmagupta formula for maximising the area
  constraint (-a + b + c + d) * (a - b + c + d) * (a + b - c + d) 
  * (a + b + c - d) == 64000000;
  
  % Minimising the perimeter finds different solutions
  solve minimize(a + b + c + d);
  
  output [" Four sides = " ++ show([a, b, c, d]) ++ 
  ", Perimeter = " ++ show(a + b + c + d)  ];
  
  %  Four sides = [104, 29, 26, 149], Perimeter = 308
  %  ----------
  %  Four sides = [16, 119, 19, 134], Perimeter = 288
  % ----------
  %  Four sides = [40, 110, 20, 70], Perimeter = 240
  % ----------
  %  Four sides = [55, 5, 85, 65], Perimeter = 210  <<< first quadrilateral
  % ----------
  % ==========
  
  
  

  LikeLike

  • 

    Frits 3:57 pm on 7 June 2021 Permalink | Reply

    Adding the following is a bit faster

    set of int: forbidden = {3, 7, 9};
    
    var 1..999: p1 = -a + b + c + d;
    var 1..999: p2 = a - b + c + d;
    var 1..999: p3 = a + b - c + d;
    var 1..999: p4 = a + b + c - d;
    
    % numbers may not end on 3, 7 or 9
    constraint forall( [p1 mod 10 != i | i in forbidden] );
    constraint forall( [p2 mod 10 != i | i in forbidden] );
    constraint forall( [p3 mod 10 != i | i in forbidden] );
    constraint forall( [p4 mod 10 != i | i in forbidden] );
    

    Also adding the following slows it down again but it does report all 8 solutions (with 1..300 for a,b,c,d) with the Chuffed Solver.

    set of int: forbidden2 = {3, 7};
    
    % numbers may not be multiples of 3 or 7
    constraint forall( [p1 mod i != 0 | i in forbidden2] );
    constraint forall( [p2 mod i != 0 | i in forbidden2] );
    constraint forall( [p3 mod i != 0 | i in forbidden2] );
    constraint forall( [p4 mod i != 0 | i in forbidden2] );
    

    LikeLike

  • 

    Frits 7:38 pm on 9 June 2021 Permalink | Reply

     
    constraint a < b /\ b < c /\ c < d; 
    
    is a lot faster than 
    
    constraint all_different([a, b, c, d]);
    

    LikeLike

• 

  GeoffR 7:15 am on 8 June 2021 Permalink | Reply

  @Frits: Yes, interesting code enhancements.
  If the UB of a,b,c,d is set to 100, it produces the single smallest answer.

  LikeLike

• 

  Frits 5:14 pm on 9 June 2021 Permalink | Reply

  Runs a lot faster with PyPy than with Python 3.9.

  T = 64000000
  
  # loop over perimeter (sum of the side lengths)
  # as from (4 * sqrt(2000))
  for P in range(179, 999999):
    for a in range(1, P // 4 + 1):
      for b in range(a + 1, (P - a) // 3 + 1):
        for c in range(b + 1, (P - a - b) // 2 + 1):
          d = P - (a + b + c)
          p1 = -a + b + c + d
          p2 = a - b + c + d
          p3 = a + b - c + d
          p4 = a + b + c - d
        
          if p1 * p2 * p3 * p4 != T: continue
  
          print(f"side lengths {a}, {b}, {c}, {d} with perimeter {P}")  
          exit()
  

  (Modified as per comment below).

  LikeLike

  • 

    Jim Randell 5:22 pm on 9 June 2021 Permalink | Reply

    @Frits: You can start looking for perimeters at [[ intc(4 * sqrt(2000)) ]] = 179, as a square has the minimal perimeter for a given area.

    LikeLike

• 

  GeoffR 8:54 pm on 9 June 2021 Permalink | Reply

  A straight translation of my MiniZinc programme for the single solution.

  
  from enigma import Timer
  timer = Timer('ST2000', timer='E')
  timer.start()
  
  for a in range(1,100):
    for b in range(a+1,100):
      for c in range(b+1,100):
        for d in range(c+1, 100):
          if (-a + b + c + d) * (a - b + c + d) \
             * (a + b - c + d) * (a + b + c - d) == 64000000:
            print(f"4 Sides/Perimeter: {a}, {b}, {c}, {d}, {a+b+c+d}")
            timer.stop()      
            timer.report()
            exit()  
  
  # 4 Sides/Perimeter: 5, 55, 65, 85, 210
  # ST2000] total time: 0.4669819s (466.98ms)
  
  

  LikeLike