Enigmatic Code

Programming Enigma Puzzles

Enigma 1313: Triangles

From New Scientist #2471, 30th October 2004

Draw a triangle ABC.  On the side AB mark the point P such that AP=(2/5)AB, on BC mark Q such that BQ=(2/5)BC and on CA mark R such that CR=(2/5)CA.

Draw the lines AQ, BR and CP.  Call the point where AQ and BR cross X, the point where BR and CP cross Y and the point where CP and AQ cross Z.

If you did the appropriate calculations you would find that the area of triangle XYZ is 1/19 of the area of triangle ABC.

I went through the whole procedure above again, but, this time with each occurrence of the number 2/5 replaced by the number k, which is between 0 and 1/2.  This time I found that the area of triangle XYZ was 1/37 of the area of triangle ABC.

What was the number k?

[enigma1313]

Advertisements

2 responses to “Enigma 1313: Triangles

  1. Jim Randell 29 June 2014 at 8:11 am

    This Python program uses the SymPy to do the maths. It runs in 444ms.

    from sympy import symbols, sqrt, sin, pi, simplify, Rational, Eq, solve
    from enigma import printf
    
    def degrees(d):
      return pi * d / 180
    
    # as the procedure works with any triangle we will consider the case
    # where ABC is an equilateral triangle with sides of unit length
    # 
    # we're interested in the ratio of the areas of XYZ and ABC
    #
    # R = area(XYZ) / area(ABC)
    #
    # now:
    #
    # area(XYZ) = area(ABC) - 3 area(ABX)
    #
    # so:
    #
    # R = 1 - 3 area(ABX)/area(ABC)
    #
    # and:
    #
    # area(ABC) = sqrt(3) / 4
    
    ABC = sqrt(3) / 4
    printf("area(ABC) = {ABC}")
    
    # now:
    #
    # area(ABX) = area(ABQ) - area(BQX)
    #
    # and:
    #
    # area(ABQ) = (1/2) AB BQ sin(angle(ABQ))
    
    k = symbols('k')
    ABQ = k * sin(degrees(60)) / 2
    printf("area(ABQ) = {ABQ}")
    
    # to calculate area(BQX) we consider the line RD parallel to AQ which
    # creates a triangle BDR similar to BQX.
    #
    # area(BQX) = r^2 area(BDR), where r is the ratio of the side lengths
    # of the similar triangles [*]
    #
    # r = BQ / BD
    #
    # and:
    #
    # BQ = k, BD = BC - DC, BC = 1
    #
    # to calculate DC consider the similar triangles RDC and AQC
    #
    # DC/QC = RC/AC
    #
    # and QC = 1 - k, RC = k, AC = 1, so:
    #
    # DC = k(1 - k) = k - k^2
    #
    # hence:
    #
    # BD = BC - DC = 1 - k + k^2
    #
    # so:
    #
    # r = k / (1 - k + k^2)
    
    r = k / (1 - k + k ** 2)
    printf("r = {r}")
    
    # now:
    #
    # area(RDC) = (1/2) RC DC sin(angle(RCD))
    #           = (1/2) k  (BC - BD) sin(60 degrees)
    #
    # BC = 1, BD = 1 - k + k ^ 2
    
    RDC = simplify(k * (1 - (1 - k + k ** 2)) * sin(degrees(60)) / 2)
    printf("area(RDC) = {RDC}")
    
    # and:
    #
    # area(BDR) = area(BCR) - area(RDC)
    
    BDR = simplify(ABQ - RDC)
    printf("area(BDR) = {BDR}")
    
    # and so area(BQX) [*]
    
    BQX = simplify((r ** 2) * BDR)
    printf("area(BQX) = {BQX}")
    
    # and finally area(ABX)
    
    ABX = simplify(ABQ - BQX)
    printf("area(ABX) = {ABX}")
    
    # so for R
    
    R = simplify(1 - 3 * ABX / ABC)
    printf("R = {R}")
    
    # check known points:
    # k = 0 or k = 1 => R = 1, k = 1/2 => R = 0, k = 2/5 => R = 1/19
    for (k0, R0) in ((0, 1), (1, 1), (Rational(1, 2), 0), (Rational(2, 5), Rational(1, 19))):
      Rs = R.subs({k: k0})
      printf("k={k0} => R={Rs}")
      assert Rs == R0
    
    # and solve R = 1/37 for k
    for s in solve(Eq(R, Rational(1, 37)), k):
      if s.is_real:
        printf("R=1/37 => k={s} {S}", S=('[SOLUTION]' if 0 < s < Rational(1, 2) else ''))
    

    Solution: k = 3/7.

    Here’s a diagram that explains how the maths works:

    Enigma 1313 - Diagram

    I’ve used an equilateral triangle, but a similar approach will work with any triangle and give the same result.

    The equation derived for the ratio of the areas is:

    R = \frac{3k\left( k - 1 \right)}{k^2 - k + 1} + 1

    which, as can be seen in this graph, starts at R=1 when k=0, drops to R=0 at k=½ and then rises back to R=1 at k=1, which is how we would expect it to behave.

    Enigma 1313 - Graph

  2. Jim Randell 29 June 2014 at 8:21 am

    And here’s a constructive numerical solution in Python using the find_value() function from the enigma.py library. It uses a simple right angled triangle for the construction (although any triangle (A, B, C) could be specified in the calculation of R). After the numerical calculation it finds the closest rational approximation with a denominator of 1000 or less to give as the answer. It runs in 46ms.

    from fractions import Fraction
    from enigma import sqrt, find_value, printf
    
    # tolerance
    t = 1e-9
    
    # area of a triangle defined by three points
    def area((x1, y1), (x2, y2), (x3, y3)):
      return abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0
    
    # a point a fraction of the way along a line
    def fraction(f, (x1, y1), (x2, y2)):
      return (x1 + f * (x2 - x1), y1 + f * (y2 - y1))
    
    # where do two lines intersect?
    def intersect((x1, y1), (x2, y2), (x3, y3), (x4, y4)):
      x12 = x1 - x2
      x34 = x3 - x4
      y12 = y1 - y2
      y34 = y3 - y4
      a = x1 * y2 - y1 * x2
      b = x3 * y4 - y3 * x4
      d = x12 * y34 - y12 * x34
      return ((a * x34 - x12 * b) / d, (a * y34 - y12 * b) / d)
    
    # do the procedure
    def R(k):
    
      # place the corners of the large triangle
      A = (0.0, 0.0)
      B = (1.0, 0.0)
      C = (0.0, 1.0)
    
      # compute the area of ABC
      ABC = area(A, B, C)
    
      # P is k along AB, ...
      P = fraction(k, A, B)
      Q = fraction(k, B, C)
      R = fraction(k, C, A)
    
      # X is at the intersection of AQ and BR, ...
      X = intersect(A, Q, B, R)
      Y = intersect(B, R, C, P)
      Z = intersect(A, Q, C, P)
    
      # compute the area of XYZ
      XYZ = area(X, Y, Z)
    
      # return the ratio
      return XYZ / ABC
    
    # check known points (k=0, 1, 1/2, 2/5)
    for (k0, R0) in [(0.0, 1.0), (1.0, 1.0), (0.5, 0.0), (2.0 / 5.0, 1.0 / 19.0)]:
      r = R(k0)
      assert abs(r - R0) < t
    
    # and find k (between 0 and 1/2) when R = 1/37
    r = find_value(R, 1.0 / 37.0, 0.0, 0.5, t=t)
    # and find a rational approximation to the answer
    k = Fraction.from_float(r.v).limit_denominator(1000)
    
    printf("R = 1/37 (~ {r.fv}) at k ~ {k} (~ {r.v})")
    

    This code uses the ability to specify pairs as the formal arguments in function definitions, which Python 2.7.6 doesn’t seem to have a problem with, but it doesn’t work in Python 3.4.0, which is a shame as I thought it was rather a neat (and useful) trick. (PEP 3113 [ http://legacy.python.org/dev/peps/pep-3113/ ] explains their removal in Python 3, and how to work around it ).

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: