Prove that $S$ has at most $n$ free points

57 Views Asked by At

Problem Statement:

Given $m = 2n$, let $S$ be a set of $m$ points on a circle with no two diametrically opposite. Say that $x \in S$ is free if fewer than $n$ points on $S - x$ lie in the semicircle clockwise from $x$. Prove that $S$ has at most $n$ free points.

I was wondering how this can be proven with the pigeonhole principle

1

There are 1 best solutions below

0
On

Hint: Show that 2 diametrically opposite points cannot both be free points.

Hence, the result follows from PP.