LogicalAndReasoning PUMaC Intermediate
2014


Problem - 2551
Let there be $320$ points arranged on a circle, labeled $1$, $2$, $3$, $\cdots$, $8$, $1$, $2$, $3$, $\cdots$, $8$, $\cdots$ in order. Line segments may only be drawn to connect points labeled with the same number. What is the largest number of non-intersecting line segments one can draw? (Two segments sharing the same endpoint are considered to be intersecting).

For convenience, let's label these $320$ points, clockwise as $P_1$, $P_2$, $\cdots$, $P_{320}$. Firstly, it is possible to draw $39$ non intersection lines by drawing $\boxed{39}$ lines starting from $P_1$, $P_2$, $\cdots$, $P_{39}$ by connecting to the nearest legitimate ending point anti-clockwise.

Now, let's show that $39$ is the maximum possibility. For this, let's consider the shortest such line $P_aP_b$ where $b > a$. Clearly, we have $a\equiv b\pmod{8}$. Because this line is shortest, there should be no line connecting points $\mathbb{P} = \{$ $P_{a+1}$, $P_{a+2}$, $\cdots$, $P_{b-1}$ $\}$. If this claim does not hold, then such a line must connect two points in $\mathbb{P}$ in order to avoid intersecting with $P_aP_b$. However such a line will be shorter than $P_aP_b$.

Because no point in $\mathbb{P}$ is used, therefore, all of them can be safely removed, together with the starting point $P_a$. This will remove some $8k$ points where $k$ is a positive integer. This will leave $8\times (40-k)$ points among which numbers are still be consecutive in a circular manner. We can then consider the shortest line among the remaining points and repeat the same removal process. Such a removal process can continue util there is $8$ points left in which case no more line can be drawn. Therefore at most $39$ removal processes can be carried out and each process is associated with one line. This means at most $39$ lines can be constructred.

report an error