Enigmatic Code

Programming Enigma Puzzles

Enigma 1017: Paint the line

From New Scientist #2173, 13th February 1999 [link]

Pussicato, the great artist, is starting his new commission. The canvas is a horizontal line, 6 metres long, and he has to paint parts of it red according to a rule he has been given. He selects a point P on the line and measures its distance, x metres from the left hand end.

He then works out the number:

1/(x – 1) + 2/(x – 2) + 3/(x – 3) + 4/(x – 4)

If the number is 5 or more then he paints the point P red, otherwise he leaves it unpainted.

For example when x = 2.1 he gets the number 15.47… , which is more than 5, and so he paints P red. And when x = 1.7 he gets –9.28…, which is less than 5, and so he leaves P unpainted.

Pussicato repeats this for every point of the line, except those with x = 1, 2, 3 or 4, which he has been told to leave unpainted.

When he has finished he finds that four parts of the line are painted red and their total length is a while number of metres. (Pussicato could have worked all that out without doing the painting).

What is the total length of the red parts?

[enigma1017]

5 responses to “Enigma 1017: Paint the line

  1. Jim Randell 29 March 2019 at 7:12 am

    If we consider the function:

    f(x) = 1/(x – 1) + 2/(x – 2) + 3/(x – 3) + 4/(x – 4)

    One way to solve this problem is to divide the line into segments, and then colour each segment according to the value of f(x) at some point in the segment.

    In this Python program we divide the line into 1 million segments, and give an answer to the nearest millimetre. It runs in 413ms.

    Run: [ @repl.it ]

    from enigma import irange, number, arg, printf
    
    # the function (for float x)
    f = lambda x: sum(i / (x - i) for i in (1.0, 2.0, 3.0, 4.0))
    
    # divide the line into 1/N segments
    N = number(arg("1_000_000", 0))
    n = 1.0 / float(N)
    
    # count the number of segments painted red
    red = 0
    for i in irange(0, N - 1):
    
      x = float(6 * i + 3) * n
      try:
        v = f(x)
        if not(v < 5.0): red += 1
      except ArithmeticError:
        continue
    
    printf("{d:.3f}m red [{red} of {N} segments]", d=red * n * 6.0)
    

    Solution: The total length of the red parts is 2 metres.

    The program finds that 333,333 of the 1,000,000 segments are coloured red, which is almost exactly a third.

    We can divide the line into segments of length 1 micrometre, and consider 6 million segments, and we would expect exactly 2 million of them to be coloured red. This takes a little longer (1.2s), but gives us the answer we expect:

    % time pypy enigma1017.py 6_000_000                        
    2.000m red [2000000 of 6000000 segments]
    

    To get a faster numerical solution we can consider the graph of f(x).

    The function is undefined at x = 1, 2, 3, 4. So we consider the segments (0, 1), (1, 2), (2, 3), (3, 4), (4, 6), where the function is defined.

    In the (0, 1) segment all the fractions are negative, and as x approaches 1, then f(x) approaches –∞, so in this segment the value of the function is always less than 5. So this segment contributes no red to the finished work.

    In the (1, 2) segment, when x is only a tiny bit larger than 1, then the first fraction give a large positive value, and the remaining fractions contribute much smaller negative values. So the function starts at +∞ at x = 1 and as x approaches 2 the function approaches –∞. Somewhere in the middle of the segment the function will have the value 5. We call this value (1 + x1), and in the interval (1, 1 + x1] the function will have a value greater than or equal to 5. So this segment will contribute a length or x1 of red to the finished work.

    Similarly in the (2, 3) segment, the function goes from +∞ to –∞, and so takes on the value 5, at (2 + x2). So this contributes a value of x2 to the finished work.

    Likewise, in the segment (3, 4) will contribute x3 to the finished work.

    In the segment (4, 6), the function starts at +∞, and as x increases the fractions will get smaller and smaller, so the value of the function would eventually approach 0. If it reaches the value of 5 in the segment (4, 6) then x4 will be less than 2, if not the entire segment will contribute red to the finished work and x4 will be 2.

    So if we find when the function takes on the value 5 in the appropriate segments we can find the total length of red in the finished work.

    The graph actually looks like this: (f(x) in blue, the areas where f(x) ≥ 5 indicated in red)

    We can use the following program to calculate the total length of the red segments. It uses the [[ find_value() ]] function from the enigma.py library and runs in 74ms.

    from enigma import tuples, find_value, printf
    
    # the function (for float x)
    f = lambda x: sum(i / (x - i) for i in (1.0, 2.0, 3.0, 4.0))
    
    # amount of red
    red = 0.0
    
    # consider the segments
    for (a, b) in tuples((1.0, 2.0, 3.0, 4.0, 6.0), 2):
      try:
        # find when f = 5 in the segment (a, b)
        r = find_value(f, 5.0, a, b)
        red += r.v - a
        printf("segment ({a}, {b}): f({r.v:.6f}) = {r.fv:.6f}")
      except ValueError:
        # otherwise: f > 5 for the whole segment
        red += b - a
    
    # output total red
    printf("red = {red:.6f} m")
    

    The four places where the function have has a value of 5 are: (to 6 dp)

    x = 1.098289
    x = 2.197573
    x = 3.331426
    x = 5.372712

    These are the roots of the equation:

    f(x) = 5

    which are also the roots of:

    x⁴ – 12x³ + 49x² – 80x + 216/5 = 0

    Wolfram Alpha can work out the exact values of these: [ link ].

  2. Brian Gladman 29 March 2019 at 2:04 pm

    The graph shows that the red parts of the line are each between a pole and the next root of the polynomial. Their total length is hence sum(roots) – (1 + 2 + 3 + 4) = sum(roots) – 10. And since the sum of the roots is the inverse of the coefficient of x^3 in its expansion, we immediately obtain the total length of the red parts as 2 metres..

    • Jim Randell 30 March 2019 at 8:27 am

      @Brian: That’s neat. I wondered if there was a simpler way to arrive at the answer. The exact form of the roots found by Wolfram Alpha is not pretty.

      I hadn’t come across the result for the sum and product of polynomial roots before. Namely:

      For a polynomial of the form:

      f(x) = a.x^n + b.x^(n – 1) + c.x^(n – 2) + … + z

      The sum of the roots is: –b/a

      The product of the roots is: z/a (when n is even); –z/a (when n is odd).

  3. Jim Randell 30 March 2019 at 9:11 am

    Here’s a Python program using this approach Brian describes above (and the [[ Polynomial() ]] class from enigma.py) to provide an exact answer:

    from fractions import Fraction
    from enigma import Polynomial, irange, printf
    
    # the sum of the roots of a polynomial
    sum_roots = lambda p: Fraction(-p[-2], p[-1])
    
    # form the polynomials, p(x) / q(x) = f(x) - 5
    (x1, x2, x3, x4) = (Polynomial([-k, 1]) for k in irange(1, 4))
    q = x1 * x2 * x3 * x4
    p = (
      (Polynomial([1]) * x2 * x3 * x4) +
      (Polynomial([2]) * x1 * x3 * x4) +
      (Polynomial([3]) * x1 * x2 * x4) +
      (Polynomial([4]) * x1 * x2 * x3) +
      (Polynomial([-5]) * q)
    )
    printf("[p = {p}, q = {q}]")
    
    # the answer is...
    r = sum_roots(p) - sum_roots(q)
    printf("red = {r} m")
    
  4. Brian Gladman 30 March 2019 at 3:24 pm

    I remember the the ‘sum of roots of a polynomial’ from my maths A levels some 60+ years ago!

    Here is a version of this puzzle that uses matplotlib and sympy with Python to produce the graph and the solution.

    from sympy import symbols, cancel, fraction, solveset, N
    import matplotlib.pyplot as plt
    from matplotlib.ticker import MultipleLocator
    
    # set up the function in sympy (line is red when f(x) > 0)
    x = symbols('x')
    e = 1 / (x - 1) + 2 / (x - 2) + 3 / (x - 3) + 4 / (x - 4) - 5
    
    # find its algebraic numerator and denominator
    n, d = fraction(cancel(e))
    print(f"numerator: {n}")
    print(f"denominator: {d}")
    
    # evaluate the sums of its roots and poles as the
    # negatives of the ratios of the coefficients of
    # the x^3 and x^4 terms in the expansions of the 
    # numerator and denominator 
    sum_roots = - n.coeff(x, 3) // n.coeff(x, 4)
    sum_poles = - d.coeff(x, 3)
    print(f"The length of the red parts is {sum_roots - sum_poles} metres.")
    
    # compute the numeric positions of its poles and roots
    roots = [complex(N(x)).real for x in solveset(n)]
    poles = [float(N(x)) for x in solveset(d)]
    
    # data for the function plot
    xx, yy = [], []
    for i in range(0, 601):
      xv = i / 100
      if xv != int(xv):
        yv = 1 / (xv - 1) + 2 / (xv - 2) + 3 / (xv - 3) + 4 / (xv - 4) - 5
        xx.append(xv)
        yy.append(yv)
    
    # set up the graph paper
    ax = plt.subplot()
    ax.set(xlabel='x', title="1 / (x - 1) + 2 / (x - 2) + 3 / (x - 3) + 4 / (x - 4) - 5")
    ax.axis([0, 6, -20, 20])
    ax.xaxis.set_major_locator(MultipleLocator(1))
    ax.xaxis.set_minor_locator(MultipleLocator(0.1))
    ax.yaxis.set_major_locator(MultipleLocator(10))
    ax.yaxis.set_minor_locator(MultipleLocator(1))
    ax.grid(axis='both', which='both', color='0.8', linewidth=1)
    
    # plot and show the graph
    ax.plot(xx, yy, color='k')
    for x0, x1 in zip(poles, roots):
      ax.plot([x0, x1], [0, 0], color='r')
    plt.show()
    

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: