Problem 1! IMO 2015

a) Consider the set of points $O, P_1, P_2, \ldots P_n$ such that $P_kO=r$ for all $1\le k\le n$; and for all $P_i$, there exists a $P_j$ such that $P_iP_j=r$. It is easy to construct this for any $n\ge 3$.

b) I claim that only odd integers $n\ge 3$ satisfy that it can be center-free. For all odd integers $n\ge 3$, a working example is just the vertices of a regular $n$-gon. It remains to prove that it is not possible for even numbers $n\ge 3$.

Note that there are $\dbinom{n}{2} = \dfrac{n(n-1)}{2}$ edges total, and $n$ points, meaning that on average, each point lies on the perpendicular bisector of $\dfrac{n-1}{2}$ edges. When $n$ is even, this means that there exists a point $P$ that lies on the perpendicular bisector of $\dfrac{n}{2}$ edges. Consider the edges that have $P$ on their perpendicular bisector. At least two edges share a point, because if no edge shared a point there can be at most $\dfrac{n}{2}-1$ edges as there are only $n-1$ available points. But then we're done; since two edges share a point, and $P$ is a perpendicular bisector of both these edges, then the distance between $P$ to the three points that make up these two edges is the same, contradiction.

We can prove (b) using double counting(refer to Daniel's solution for the rest), here's the basic outline:

Our object being counted will be $(P, \{ A,B\})$ satisfying $PA=PB$, the number of which will be denoted by $k$. On one hand, every combination of two points(i.e. $\{A,B\}$) has at least one $P$ since the set is balanced; this gives $k\ge C(n,2)=\frac {n(n-1)}{2}$. On the other hand, every point has at most $\lfloor \frac {n-1}{2}\rfloor$ combinations of two points (If it has more, then by PHP there exists two combinations that share a point, contradicting the centre-free condition); this gives $k\le n\lfloor \frac {n-1}{2}\rfloor$. Together we have:

$\frac {n(n-1)}{2}\le n\lfloor \frac {n-1}{2}\rfloor$

Clearly this inequality only holds when $n$ is odd.