PUMaC 2014 · 组合（B 组） · 第 4 题

PUMaC 2014 — Combinatorics (Division B) — Problem 4

[ 4 ] Let there be 320 points arranged on a circle, labled 1 , 2 , 3 , ..., 8 , 1 , 2 , 3 , ..., 8 , ... in order. Line segments may only be drawn to connect points labelled with the same number. What thethe largest number of non-intersecting line segments one can draw? (Two segments sharing the same endpoint are considered to be intersecting).

解析

[ 4 ] Let there be 320 points arranged on a circle, labled 1 , 2 , 3 , ..., 8 , 1 , 2 , 3 , ..., 8 , ... in order. Line segments may only be drawn to connect points labelled with the same number. What thethe largest number of non-intersecting line segments one can draw? (Two segments sharing the same endpoint are considered to be intersecting). Solution: Let us label the points p , ..., p . Let us consider the shortest line segment p p . We see 1 320 a b that there are no lines from points on the smaller sector of the circle defined by this line, p ∈ { p , p , ..., p } . Assuming the contrary that there is a line from p . Since any line pq a +1 a +2 b − 1 2 must be in the same sector, as otherwise pq will intersect p p , we see that | pq | < | p p | which a b a b is contradictory. Since there are no point between p and p , we can effectively, remove this section, leaving the a b points p , ..., p , p , ..., p . Since a ≡ b (mod 8), we see that some 8 k points are removed, 1 a b +1 320 for k ∈ N . We now consider the shortest line in the remaining set of points. After recursive removal of at least 8 points for each line removed, we can remove at most 39 such lines, leaving 8 points 1 , 2 , ..., 8 on which no further removal is possible. We see that 39 is possible, with line segment between p and p for k = { 1 , ..., 39 } . 4 k 320 − 4 k