Enigmatic Code

Programming Enigma Puzzles

Enigma 359: Neat odd quad

From New Scientist #1508, 15th May 1986 [link]

Enigma 359

I call ABCD an odd cyclic quadrilateral, or “odd quad” for short. It has four corners A, B, C, D, and four straight sides AB, BC, CD, DA, so it’s a quadrilateral. The corners lie on a circle, so it’s cyclic. And it’s odd because — well, what is its area? I have decided to define that as what the sides cut off from the outside world, that is, the sum of the shaded areas.

neat odd quad has the lengths of its four sides all different positive whole numbers and its area is a whole number too.

Can you find a neat odd quad with an area less than 30? What are the lengths of:

(a) The sides AB, CD, which don’t cross?
(b) The crossing sides BC, AD?

[enigma359]

Advertisements

2 responses to “Enigma 359: Neat odd quad

  1. Jim Randell 26 August 2016 at 8:54 am

    This Python 3 program considers quadrilaterals with increasing perimeter, until it finds one that is a crossed cyclic quadrilateral with an area less than 30. It runs in 214ms.

    # consider crossed cyclic quadrilaterals ABCD, where:
    #   AB = a, BC = b, CD = c, AD = d
    # and AD, BC intersect at X:
    #   BX = b1, CX = b2, AX = d1, DX = d2
    #
    # triangles ABX, CDX are similar
    
    from itertools import count
    from fractions import Fraction as F
    from enigma import irange, is_square, printf
    
    # decompose <t> into <n> different numbers
    def decompose(t, n, s=[]):
      if n == 1:
        if t not in s:
          yield s + [t]
      else:
        for x in irange(1, t - 1):
          if x not in s:
            yield from decompose(t - x, n - 1, s + [x])
    
    # consider increasing perimeters
    for t in count(10):
      for (a, b, c, d) in decompose(t, 4):
        # for uniqueness let's suppose a < c, b < d
        if not(a < c and b < d): continue
    
        k = F(a, c)
        k2 = k * k
    
        # calculate b1, b2, d1, d2
        d1 = F(k * b - k2 * d, 1 - k2)
        if not(d1 > 0): continue
        d2 = d - d1
        b1 = k * d2
        b2 = b - b1
    
        # calculate the area of the quad, and check it is a positive square
        cos = F(b1 * b1 + d1 * d1 - a * a, 2 * b1 * d1)
        area2 = F(b1 * d1 + b2 * d2, 2) ** 2 * (1 - cos ** 2)
        if not(0 < area2 < 900 and area2.denominator == 1): continue
        area = is_square(area2.numerator)
        if not area: continue
    
        printf("a={a} b={b} c={c} d={d}, k={k}, b={b1}+{b2} d={d1}+{d2}, area={area} (sqrt({area2}))")
        exit()
    

    Solution: Yes, there is a neat odd quad with area less than 30. (a) The two non-crossing sides have length 2 and 6. (b) The two crossing sides have length 7 and 9.

    Enigma 359 - Solution

    AB = 2, BC = 9, CD = 6, AD = 7.

    The area of the quadrilateral is 15.

    Note that the angles B and D are right angles, so the line AC is a diameter of the circumcircle, and the triangles ABX, CDX are 3:4:5 triangles.

  2. Brian Gladman 26 August 2016 at 11:51 pm

    Essentially the same with minor variations.

    from itertools import count
    from fractions import Fraction as RF
    
    # format for output
    fs = 'a = {}, c = {}, p = {} ({} + {}), q = {} ({} + {}), r = {}, A = {}.'
    
    # partition an integer <n> into <p> parts 
    def partition(n, p, seq=[]):
      if p == 1:
        if n not in seq:
          yield seq + [n]
      else:
        for i in range(1, n):
          if i not in seq:
            yield from partition(n - i, p - 1, seq + [i])
    
    # consider quadrilaterals in order of increasing perimeter
    for perimiter in count(10):
      # a and c are the outer sides, p and q are the crossing sides
      for a, c, p, q in partition(perimiter, 4):
        if a < c and p < q:
          # the crossing point splits p into (e, f) and q into (g, h)
          # giving two similar triangles (a, g, e) <==> (c, f, h)
    
          # r is the (linear) ratio between the two triangles 
          r = RF(a, c)
          r2 = r * r
          # compute the other sides for the (c, f, h) triangle
          f = (p - r * q) / (1 - r2)
          h = q - r * f
          if 0 < f < p and 0 < h < q:
          
            if True:
              # find the square of the combined area of the two 
              # triangles using Heron's formula
              s = (c + f + h) / 2
              A2 = s * (s - c) * (s - f) * (s - h) * (1 + r2) ** 2
            else:
              # alternative using 1/2 base x height formula
              cos = (f * f + h * h - c * c) / (2 * f * h)
              A2 = (f * h * (1 + r2) / 2) ** 2 * (1 - cos ** 2) 
            
            # check that the area is an integer less than 30
            if A2.denominator == 1 and 0 < A2 < 900:
              A = int(A2.numerator ** 0.5)
              if A2 == A * A: 
                print(fs.format(a, c, p, p - f, f, q, q - h, h, r, A))
                exit()
    

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: