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?
-
$\begingroup$ The full lines must not intersect, or just the line segments between the two numbers? $\endgroup$ – aschepler Nov 10 '19 at 23:45
-
$\begingroup$ Just the line segments. Updated the text. $\endgroup$ – Dmitry Kamenetsky Nov 10 '19 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$.
-
-
$\begingroup$ All good! Can you do better or can you prove that this is the optimal? $\endgroup$ – Dmitry Kamenetsky Nov 10 '19 at 23:58
-
-
1$\begingroup$ 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. $\endgroup$ – WhatsUp Nov 11 '19 at 1:00
-
1$\begingroup$ Thank you. I suspected it was the answer but wasn't sure how to prove it. $\endgroup$ – Dmitry Kamenetsky Nov 11 '19 at 1:02