Enigmatic Code

Programming Enigma Puzzles

Enigma 278: Uncle Pinkle’s new system

From New Scientist #1425, 11th October 1984 [link]

Uncle Pinkle has moved house, and he is installing a new triphonic audio-system on his garden lawn. This system consists simply of three transmitters AB and C, each of which is to be exactly M yards from the others.

Uncle Pinkle will sit at a point X, carefully chosen so that the distances XAXB and XC are exact whole numbers of yards.

X must not be in a direct line with any pair of transmitters. [*]

The total XAXBXC is to be as small as possible.

Uncle Pinkle asks me to specify M, and the distances XAXB and XC, to meet his requirements.

Can you help please?

(If you find yourself using a calculator, let alone a computer, you are getting much too big. The rule in italics [*] is not as big a handicap as you may be thinking).

[enigma278]

Advertisements

12 responses to “Enigma 278: Uncle Pinkle’s new system

  1. Jim Randell 5 May 2015 at 8:22 am

    I think the setter is expecting us to assume that M should be a positive integer, otherwise we can just place X at the centre of an equilateral triangle and make AX = BX = CX = 1, and M = √3 to give us a minimum possible total distance of 3.

    This program uses a result that I found on the Wikipedia page for Equilateral Triangles [ http://en.wikipedia.org/wiki/Equilateral_triangle ], namely, that for any point in the plane, X, with distances a, b, c to the vertices A, B, C of an equilateral triangle of side s, we have:

    3(a⁴ + b⁴ + c⁴ + s⁴) = (a² + b² + c² + s²)²

    Which keeps things nicely in the integers.

    This Python program runs in 64ms.

    from itertools import count
    from enigma import irange, printf
    
    # For any point X in the plane, with distances a, b, and c from the
    # vertices A, B, and C respectively of an equilateral triangle:
    #
    #   3(a^4 + b^4 + c^4 + M^4) = (a^2 + b^2 + c^2 + M^2)^2
    #
    # [De, Prithwijit, "Curious properties of the circumcircle and incircle
    # of an equilateral triangle," Mathematical Spectrum 41(1), 2008-2009,
    # 32-35 referenced from <http://en.wikipedia.org/wiki/Equilateral_triangle>]
    
    # we pass in the squares here, so we can do things like:
    # check(1, 1, 1, 3) => True
    # using integers
    def check(a2, b2, c2, M2):
      return 3 * (a2 ** 2 + b2 ** 2 + c2 ** 2 + M2 ** 2) == (a2 + b2 + c2 + M2) ** 2
    
    # decompose total <t> into <n> increasing numbers
    def decompose(t, n, m=1):
      # are we done?
      if n == 1:
        if not(m > t):
          yield [t]
      else:
        for i in irange(m, t // n):
          for s in decompose(t - i, n - 1, i):
            yield [i] + s
    
    # consider increasing sums, a + b + c
    for t in count(3):
      # count solutions
      n = 0
      # decompose the sum into a, b, c
      for (a, b, c) in decompose(t, 3):
        # find possible values for M
        for M in irange(c - a + 1, a + b - 1):
          if check(a ** 2, b ** 2, c ** 2, M ** 2):
            printf("sum={t}, M={M}, a={a} b={b} c={c}")
            n += 1
      # stop if we've found solutions for this t
      if n > 0: break
    

    Solution: M=7; XA=3, XB=5, XC=8 (sum = 16).

    Enigma 278 - Solution

    The question implies that a calculator is not necessary, but I think this method would be a bit tedious without machine assistance, so maybe there is a neater way.

  2. Brian Gladman 5 May 2015 at 6:22 pm
    # With XA = p, XB = q and and XC = r, we have:
    # 
    #   p^2 = x^2 + y^2
    #   q^2 = (x - m)^2 + y^2
    #   r^2 = (x - m.cos(60))^2 + (y - m.sin(60))^2
    #
    # Expanding and substituting where appropriate now gives:
    #
    #   2.m.x = p^2 + m^2 - q^2
    #   2.3^(1/2).m.y = p^2 + m^2 + q^2 - 2.r^2
    #
    # Eliminating x and y now gives:
    #
    #   (p^2 +  m^2 + q^2 - 2.r^2)^2 =  3.{ (2.m.p)^2
    #                 - (p^2 + m^2 - q^2)^2 }
    #
    # which allows r to be obtained from m, p and q
    
    from itertools import count
    
    # for saving the solution for minimum p + q + r
    min_sol, min_mpqr = None, None
    # increase m until a minimum solution is found
    for m in count(1):
      for p in range(1, m):
        for q in range(p, m):
          # compute right hand side of the final expression above
          t2 = 3 * ((2 * m * p) ** 2 - (p ** 2 + m ** 2 - q ** 2) ** 2)
          # and skip values that are not square
          if t2 > 0:
            t = int(t2 ** 0.5 + 0.5)
            if t2 == t ** 2:
              # now solve for r
              for u in (t, - t):
                r2, rem = divmod(p ** 2 + m ** 2 + q ** 2 + u, 2)
                if not rem and r2 >= q ** 2:
                  r = int(r2 ** 0.5 + 0.5)
                  if r2 == r ** 2:
                    if not min_sol or p + q + r < min_sol:
                      min_sol = p + q + r
                      min_mpqr = (m, p, q, r)
      if m > 10:
        break
    print('M = {}, XA = {}, XB = {} and XC = {}'.format(*min_mpqr))
    
    • Jim Randell 6 May 2015 at 10:22 am

      Along similar lines to Brian’s program, we find that given (a, b, c) we can arrive at the following quadratic equation in :

      (M²)² – qM² + (q² – 3r) = 0

      where:

      q = a² + b² + c²
      r = a²b² + a²c² + b²c²

      So for increasing totals t = a+b+c we can then find solutions for using the standard quadratic formula, and look for cases where is a perfect square.

      Here’s my program modified to do this. It’s a bit messier than my first program, but runs faster and produces the same output for t up to 1000.

      from itertools import count
      from enigma import irange, is_square, printf
      
      # For any point X in the plane, with distances a, b, and c from the
      # vertices A, B, and C respectively of an equilateral triangle:
      #
      #   a^4 + b^4 + c^4 + M^4 = a^2 b^2 + a^2 c^2 + a^2 M^2 + b^2 c^2 + b^2 M^2 + c^2 M^2
      #
      # given a, b, c we can write:
      #
      #   p = (a^4 + b^4 + c^4), q = (a^2 + b^2 + c^2), r = (a^2 b^2 + a^2 c^2 + b^2 c^2)
      #   q^2 = p + 2r
      #
      #   p + M^4 = q M^2 + r
      #   M^4 - q M^2 + (p - r) = 0
      #
      # which is a quadratic equation in M^2
      #
      #   2 M^2 = q +/- sqrt(q^2 - 4(p - r))
      #   2 M^2 = q +/- sqrt(q^2 - 4(q^2 - 3r))
      #   2 M^2 = q +/- sqrt(12r - 3q^2)
      
      # decompose total <t> into <n> increasing numbers
      def decompose(t, n, m=1):
        # are we done?
        if n == 1:
          if not(m > t):
            yield [t]
        else:
          for i in irange(m, t // n):
            for s in decompose(t - i, n - 1, i):
              yield [i] + s
      
      # consider increasing sums, a + b + c
      for t in count(3):
        # count solutions
        n = 0
        # decompose the sum into a, b, c
        for (a, b, c) in decompose(t, 3):
          # calculate values for M
          (a2, b2, c2) = (a ** 2, b ** 2, c ** 2)
          q = a2 + b2 + c2
          r = a2 * b2 + a2 * c2 + b2 * c2
          s = is_square(12 * r - 3 * q ** 2)
          if s is None: continue
          for v in set((q + s, q - s)):
            if v < 2: continue
            (M2, x) = divmod(v, 2)
            if x > 0: continue
            M = is_square(M2)
            if M is None or not(c - a < M < a + b): continue
            printf("sum={t}, M={M}, a={a} b={b} c={c}")
            n += 1
        if n > 0: break
      

      Continuing with the interesting solutions line, M=57, XA=65, XB=73, XC=112 (sum=250) is the first solution where each of the distances to the vertices is greater than the sides of the equilateral triangle.

      Via [ http://mathworld.wolfram.com/RationalDistanceProblem.html ] I found that Richard K. Guy in Unsolved Problems in Number Theory, p181, “D19: Rational distances from the corners of a square”, mentions that:

      There are infinitely many solutions of the corresponding problem of integer distances a, b, c from the corners of an equilateral triangle of side t. In each of these one of a, b, c, t is divisible by 3, one by 5, one by 7 and one by 8.

  3. Brian Gladman 5 May 2015 at 8:21 pm

    If I modify my program to look for positions within the triangle, the smallest I find is M = 13, with (7, 7, 9) and the smallest with different distances is M = 19 with (7, 13, 14).

    • Jim Randell 5 May 2015 at 10:17 pm

      I don’t think either of those work. I tried running your program without the early termination condition and the first solution it found with X internal to the triangle was the same as I gave above.

      • Brian Gladman 5 May 2015 at 10:38 pm

        Yes, you are right. I missed an indent level in my modification and, the two solutions I quoted were close enough to correct to appear right when I drew them 😦

  4. Hugh Casement 6 May 2015 at 5:44 pm

    Could it be that the setter of the puzzle was thinking of one of these solutions,
    also involving the numbers 3, 5, 7, 8?

    m = 3. i.e. A and B are at (±1.5, 0), C at (0, 1.5√3)
    X is at (±4, -2.5√3). Distances a, b, c are 5, 7, 8.

    m = 5. i.e. A and B are at (±2.5, 0), C at (0, 2.5√3)
    X is at (±4, -1.5√3). Distances a, b, c are 3, 7, 8.

    Neither very intuitive; nor is the sum a + b + c minimum.

    I reckon to have found further solutions:

    m = 7. i.e. A and B are at (±3.5, 0), C at (0, 3.5√3)
    X is at (±7.5, -4√3). Distances a, b, c are 8, 13, 15.

    m = 8. i.e. A and B are at (±4, 0), C at (0, 4√3)
    X is at (±7.5, -3.5√3). Distances a, b, c are 7, 13, 15.

    m = 13. Distances a, b, c are 7, 8, 15
    (but the coordinates of X are no neater than in your solution).

    And many more with larger numbers.
    I think I’ll stick with good old indoor stereo.

    • Jim Randell 6 May 2015 at 11:25 pm

      @Hugh: Apart from the last one all the solutions you mention have X in line with one of the sides of the equilateral triangle ABC, which the setter disallows with the constraint marked [*].

      In general, for a solution (M, a, b, c) all the permutations of it will be potential solutions, in that they satisfy the equation that identifies X as a point in the plane with integer distances from the vertices of an integer sided equilateral triangle (the defining equation is symmetric in each of the parameters, so the order of the numbers doesn’t matter), but additionally we need to check that X is not in line with one of the sides of the triangle in order for it to be a solution to the puzzle.

      There are certainly many candidate solutions, where (M, a, b, c) are all positive integers, and X is not in line with any of the sides of the equilateral triangle (if you stop my program from ending when it finds the first solution (by sum a+b+c) it keeps generating them, for a+b+c≤1000 it finds 339 solutions).

      The smallest M with multiple different solutions seems to be M=43, e.g.:

      M=43, a=13 b=35 c=48 (sum=96)
      M=43, a=147 b=152 c=185 (sum=484)
      M=43, a=248 b=285 c=287 (sum=820)

      • Hugh Casement 7 May 2015 at 8:59 am

        Oh, sorry! Didn’t notice the alignment (trying hard not to use a calculator, you see).
        I could have mentioned that in your solution the coordinates of X are (±8/7, -15/14√3).
        [wonder whether that displays as intended]
        Did I work that out using only pencil and paper? You must be joking.

        • Hugh Casement 7 May 2015 at 3:08 pm

          Belated insight:
          Initially we ignore the ‘not in line’ restriction and place X somewhere on side AB, so that a + b = m.  cos 60° = 0.5, so the cosine rule reduces to c² = m² + a² – ma.
          Because b = m – a, that’s equivalent to c² = m² + b² – mb.
          If we find an all-integer solution we can then swap m and a (or m and b), placing X on an extension of AB, because cos 120° = -0.5.
          The setter of the puzzle apparently assumed that we would know that you can also swap m and c, putting X outside the triangle and not in line with any side — or inside, as Jim found works with certain larger numbers.  Hence the statement that we wouldn’t need a calculator.

          I found solutions (the last number in each group is the final m):
          8, 3, 5, 7; 15, 7, 8, 13; 21, 5, 16, 19; 35, 11, 24, 21; 40, 7, 33, 37; 48, 13, 35, 43
          and a good few more, as well as multiples of those.  Can’t detect any pattern.

          • Jim Randell 9 May 2015 at 11:09 am

            I was looking to see if the sequence of possible values of M occurred in OEIS, and I found A050931.

            And it’s certainly true that you can generate (by hand) a lot of possible solutions using:

            a < b
            c = a + b
            M² = a² + b² + ab

            And we can do this in a+b+c order, by considering increasing values for c = a+b.

            The first solution that pops out is the 12th candidate tried:

            c=8, a=3, b=5, M=7

            which is the answer to the puzzle.

            The nature of the solutions requires:

            c > M > b > a

            Which means that none of the triangles XAB, XAC, XBC can be degenerate.

            Maybe this is how the setter was expecting us to solve the puzzle.

            However this method doesn’t produce all possible solutions as we won’t find, for example, any solution points internal to the triangle. For example, M=112, a=57, b=65, c=73. Indeed none of the permutations of this solution will be found by this method as none of numbers is the sum of two of the others.

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: