Waste less time on Facebook — follow Brilliant.

Problem 1! IMO 2015

We say that a finite set \(\mathcal{S}\) of points in the plane is balanced if, for any two different points A and B in \(\mathcal{S}\), there is a point C in \(\mathcal{S}\) such that \(AC=BC\). We say that \(\mathcal{S}\) is centre-free if for any three different points A, B and C in \(\mathcal{S}\), there is no points P in \(\mathcal{S}\) such that \(PA=PB=PC\)

(a) Show that for all integers \(n\geq 3\), there exists a balanced set consisting of \(n\) points.

(b) Determine all integers \(n\geq 3\) for which there exists a balanced centre-free set consisting of points.

This is part of the set IMO 2015

Note by Sualeh Asif
2 years ago

No vote yet
1 vote


Sort by:

Top Newest

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. Daniel Liu · 2 years ago

Log in to reply

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. Xuming Liang · 2 years ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...