4
$\begingroup$

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?

$\endgroup$
  • $\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
5
$\begingroup$

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$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry for my terrible counting... $\endgroup$ – WhatsUp Nov 10 '19 at 23:57
  • $\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
  • $\begingroup$ A proof is added. $\endgroup$ – WhatsUp Nov 11 '19 at 0:52
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.