PUMaC 2013 · 组合（A 组） · 第 1 题

PUMaC 2013 — Combinatorics (Division A) — Problem 1

[ 3 ] A regular pentagon can have the line segments forming its boundary extended to lines, giving an arrangement of lines that intersect at ten points. How many ways are there to choose five points of these ten so that no three of the points are colinear?

解析

[ 3 ] A regular pentagon can have the line segments forming its boundary extended to lines, giving an arrangement of lines that intersect at ten points. How many ways are there to choose five points of these ten so that no three of the points are colinear? Solution There are five lines and five points, each point straddling two lines. Since no line contains more than two points, then, each line must contain exactly two points. Considering each point as an intersection of two lines in the set { a, b, c, d, e } of lines, the points can be expressed as a cycle of lines: eg, { ab, bd, de, ec, ca } or { a, b, d, e, c } . Two cycles correspond to the same set of points only when they are a rotation or reflection of another cycle, as two points are the same, ab = cd , only if a = c, b = d or a = d, b = c . There are 4! = 24 cycles for 12 arrangements.