Enigmatic Code

Programming Enigma Puzzles

Enigma 1035: Connected numbers

From New Scientist #2191, 19th June 1999 [link]

Take a large sheet of paper and write on it the numbers, 5, 6, 7, …, 999998, 999999, 1000000. You are now going to draw lines that connect pairs of the numbers as follows. Start with 5. Split 5 into two numbers, both larger than 1, in as many ways as you can. So 5 = 2 + 3. Multiply the two numbers together. Now 2 × 3 = 6, so draw a line connecting 5 and 6. The next number is 6. Now 6 = 2 + 4 = 3 + 3 and 2 × 4 = 8 and 3 × 3 = 9, so draw a line connecting 6 and 8 and another connecting 6 and 9. The next number is 7 = 2 + 5 = 3 + 4, and so we draw a line that connects 7 and 10 and another connecting 7 and 12.

Repeat the procedure for 8, 9, 10, …, in turn. Note that when a product is larger than 1000000 then no line is drawn, for example: 500002 = 2 + 500000 = 3 + 499999 = …, so a line is drawn connecting 500002 and 1000000 but no line is drawn for 3 × 499999 = 1499997.

1) When your diagram is complete, are there two numbers, both less than 250000, such that there is no path along the lines connecting one to the other?

Now for your second task, take another piece of paper. You want to write the numbers 5, 6, 7, …, 98, 99, 100 on it, and then copy onto it, from your first piece of paper, all the lines connecting numbers which are both less than or equal to 100.

2) Can you complete your second task in such a way that no two of the lines in fact cross?

[enigma1035]

One response to “Enigma 1035: Connected numbers

  1. Jim Randell 23 November 2018 at 8:30 am

    Here is a proof of the first part of the problem using mathematical induction.

    Suppose we use the following as our inductive hypothesis:

    For all numbers between 5 and n there is a path between any pair of them using lines that link numbers between 5 and 1,000,000.

    At n=5 the hypothesis is trivially true.

    Now want to show that the hypothesis holds for n (where n < 250,000) if it holds for all lower numbers.

    If n is composite (say it can be factored into a and b), then we can link it directly to the number (a + b), which is necessarily less than n and greater than or equal to 5.

    However if n is prime we can’t directly link it to a lower number, but we can link it to higher number number of the form 2(n – 2), 3(n – 3), 4(n – 4), …, and if one of these numbers is less than 1,000,000 and links to a number less than n, then there is a path that links n into the set of lower numbers.

    This Python program looks for primes that do not have a viable path.

    It runs in 767ms, and doesn’t find any numbers that cannot be linked in.

    Run: [ @repl.it ]

    from enigma import irange, divisors_pairs, Primes, arg, number, printf
    
    N = number(arg("1_000_000", 0))
    M = number(arg("250_000", 1))
    printf("[N={N} M={M}]")
    
    # link x to a number less than n
    # return a shortest path
    def solve(x, n, N, s=[]):
      ss = [[x]]
      while ss:
        s = ss.pop(0)
        x = s[-1]
        # are we done?
        if x < n:
          return s
        # add in downward links
        for (a, b) in divisors_pairs(x):
          if a < 2: continue
          y = a + b
          if y < n:
            return s + [y]
          if y not in s:
            ss.append(s + [y])
        # add in upward links
        for k in irange(2, x // 2):
          y = k * (x - k)
          if y > N: break
          if y not in s:
            ss.append(s + [y])
    
    # attempt to link all primes between 6 and M - 1
    for n in Primes(M).range(6):
      s = solve(n, n, N)
      if not s:
        printf("*** IMPOSSIBLE: {n} ***")
    

    Solution: (1) No, there is no pair of numbers, both less than 250,000, that cannot be linked together (using numbers less than 1,000,000).

    The first prime we encounter, 7, requires the most steps, as we only have a choice of two numbers to link it to (5 or 6):

    7 → [3, 4] → 12 ← [2, 6] ← 8 ← [2, 4] ← 6

    Most primes can be linked via 2(n – 2) or 3(n – 3), for example:

    353 → [2, 351] → 702 ← [3, 234] ← 237

    And here is how we can link the largest primes less than 250,000, without including numbers more than 1,000,000:

    249973 → [3, 249970] → 749910 ← [5, 149982] ← 149987
    249989 → [2, 249987] → 499974 ← [3, 166658] ← 166661

    If we reduce the ceiling from 1,000,000 to 749,900 then we find that 249,973 cannot be linked to a lower number.

    % python enigma1035.py 749_900
    [N=749900 M=250000]
    *** IMPOSSIBLE: 249973 ***
    

    The smallest prime that needs to link via a number greater than (or equal to) 1,000,000 is:

    333451 → [3, 333448] → 1000344 ← [4, 250086] ← 250090

    So keeping the ceiling at 1,000,000 we can extend the result to:

    There is no pair of numbers, both less than 333,451, that cannot be linked together (using numbers up to 1,000,000).

    ::


    The second part of the puzzle deals with numbers between 5 and 100, and asks whether the links between these numbers form a “Planar Graph” [ https://en.wikipedia.org/wiki/Planar_graph ].

    There are various algorithms for determining if a graph is planar, but they all sounded a bit complicated. I found a package called “planarity” [ https://pypi.org/project/planarity/ ] that implements one of the algorithms and used that.

    The following Python program finds the links between the specified numbers, and then feeds the graph into the checker. Which produces a simple Yes/No answer.

    from enigma import irange, arg, printf
    
    # valid numbers (from 5 to N)
    N = arg(100, 0, int)
    ns = set(irange(5, N))
    
    # collect the links
    links = set()
    for n in ns:
      for k in irange(2, n // 2):
        m = k * (n - k)
        if m not in ns: continue
        printf("{n} -> {m}")
        links.add((n, m))
    
    # check for planarity
    import planarity
    graph = planarity.PGraph(links)
    f = graph.is_planar()
    printf("is_planar = {f}")
    

    Solution: (2) No, the lines cannot be drawn with no crossings.

    We can demonstrate this as follows:

    If instead of considering all the numbers between 5 and 100 (96 numbers) we just consider the following 13 numbers: (6, 7, 8, 9, 10, 11, 12, 14, 16, 18, 24, 28, 32), this is a subgraph of the original graph (every edge of the subgraph must appear in the original graph, so if the subgraph is non-planar the parent graph is also non-planar).

    We can draw the graph as the following diagram:

    This particular diagram is clearly non-planar, but we can show that it is not possible to draw a planar diagram for this graph.

    We can remove the (10, 16) edge (and the graph is still a subgraph of the original graph), and the remaining edges can be laid out as follows:

    From which we see that there is an embedded minor including (8, 18, 24) and (9, 11, 12) that forms the “utility graph” (K3,3), which is non-planar. [ https://en.wikipedia.org/wiki/Three_utilities_problem ]

    It follows that the parent graph must also be non-planar (if it wasn’t it would give us a way to represent K3,3 using a planar diagram, and this is not possible).

    I haven’t shown that this is the smallest non-planar subgraph, so there may be a smaller subgraph (with fewer than 13 elements) that has K3,3 embedded in it that can be used to show the non-planarity of the parent graph.

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: