### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,270)
- misc (3)
- project euler (2)
- puzzle (67)
- site news (50)
- tantalizer (69)
- teaser (7)

### Site Stats

- 206,371 hits

Programming Enigma Puzzles

23 November 2018

Posted by on **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]

%d bloggers like this:

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

Suppose we use the following as our inductive hypothesis:

At

n=5the hypothesis is trivially true.Now want to show that the hypothesis holds for

n(wheren < 250,000) if it holds for all lower numbers.If

nis composite (say it can be factored intoaandb), then we can link it directly to the number(a + b), which is necessarily less thannand greater than or equal to 5.However if

nis prime we can’t directly link it to a lower number, but we can link it to higher number number of the form2(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 thann, then there is a path that linksninto 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 ]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):

Most primes can be linked via

2(n – 2)or3(n – 3), for example:And here is how we can link the largest primes less than 250,000, without including numbers more than 1,000,000:

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.

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

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

::

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.

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.