PUMaC 2014 · 个人决赛（B 组） · 第 2 题

PUMaC 2014 — Individual Finals (Division B) — Problem 2

Let P , P , ..., P be points on the plane. There is an edge between distinct points P , P if 1 2 n x y and only if x | y . Find the largest n , such that the graph can be drawn with no crossing edges.

解析

Let P , P , ..., P be points on the plane. There is an edge between distinct points P , P if 1 2 n x y and only if x | y . Find the largest n , such that the graph can be drawn with no crossing edges. Solution: We see that n = 14. The construction for n = 14 is as below: 1 For n 15 We see that there are at least the following 3 paths between 2 and 3: 2 6 3, 2 12 3 and 2 10 5 15 3. We see that these three paths are clearly distinct. Hence it will seperate the plane into 3 regions. We see that no matter which region 1 falls into, the region is enclosed by 2 of the 3 paths and rd for any edge between 1 and the number on the 3 path, it must intersect the first two that encloses 1. Thus there will always be crossing edges.