# Prime parallel rows for the first 20 numbers

Two positive integers can be joined with a straight segment if their sum is a prime and the segment doesn't intersect any other segments. What is the most number of pairs you can join if you can place numbers from 1 to 20 in two parallel rows?

• The full lines must not intersect, or just the line segments between the two numbers? Nov 10, 2019 at 23:45
• Just the line segments. Updated the text. Nov 10, 2019 at 23:48

20 09 08 03 10 19 12 05 06 07
17 14 15 16 13 18 11 02 01 04

This results in

28 pairs.

Note that

no triangle allowed.

A proof of optimality:

Without loss of generality, assume that the two rows are located on integral points on the plane, on the lines $$y = 0$$ and $$y = 1$$, respectively. Also assume that the points on each row are consecutive (e.g. from $$(0, 0)$$ to $$(9, 0)$$, etc.).

Connect all the pairs. This creates a planar graph. Let $$e$$ be the number of edges (i.e. line segments), and let $$g$$ be the number of "holes", i.e. loops created by the line segments. These are called "faces" in the link cited below.

We then have Euler's formula, which states $$20 - e + g = 1$$ (note that our definition of $$g$$ excludes the outer, infinitely large region).

So it suffices to show that $$g \leq 9$$. But we know that the area of each "hole" is a half integer (e.g. by Pick's theorem), and their sum is $$\leq 9$$ (the area of the convex hull, which must have area $$9$$, again by Pick's theorem).

Moreover, since triangles are not allowed, no hole can have area $$\frac{1}{2}$$ (again by Pick's theorem), and hence every hole has area $$\geq 1$$.

• Sorry for my terrible counting... Nov 10, 2019 at 23:57
• All good! Can you do better or can you prove that this is the optimal? Nov 10, 2019 at 23:58
• A proof is added. Nov 11, 2019 at 0:52
• I'm actually a bit curious: did you already know the solution before posting the question? This is indeed an interesting puzzle and could be a very good question in math contests. Nov 11, 2019 at 1:00
• Thank you. I suspected it was the answer but wasn't sure how to prove it. Nov 11, 2019 at 1:02