[Soln] 2015 IMO Problem 1

2015 IMO 1. 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, C in \mathcal{S}, there is no point 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 n points.


You should spend the first few minutes playing around with simple diagrams to make sure that you understand what being “balanced” and “centre-free” means. (If you get the definition wrong, whatever solution you have falls apart!)

In playing around with the diagrams, you may come up with an equivalent definition for being “balanced”: \mathcal{S} is balanced if, for any two different points A and B in \mathcal{S}, there is a point C in \mathcal{S} such that C lies on the perpendicular bisector of AB. This alternate definition will come in handy when thinking about whether a set is balanced or not.

Let’s tackle (a) first. (The earlier parts are usually easier than the later parts.) Always try out simple configurations first and hope that they satisfy the given property. The first configuration you might try is n equally-spaced points on a line:

IMO_2015_1_01

It should be clear that this configuration is not balanced as there are no points which lie on the perpendicular bisector of the 2 points highlighted in red.

The next configuration you might try is the regular n-gon:

IMO_2015_1_02

Interesting: The n-gon seems to be balanced for odd n but fails to be balanced for even n. It doesn’t take much work to prove that this observation is indeed true. (Remember: you must prove that it is true! You can’t just state it as an observation and expect to score points.)

It remains for us to find balanced sets of size even n. A good starting point will be to find a balanced set for n = 4. After some fiddling around, either with 4 random points or building on the balanced set for n = 3, you may discover that the following configuration is a balanced set (it is in fact the only possible balanced set for n = 4):IMO_2015_1_03

We now have a configuration for n = 4. Can I generalise this? It’s not immediately obvious how we can get a configuration for n = 6, 8, \dots from here. (At this point you may ask why generalising is important. Generalising is important because we are asked to find balanced sets for ALL even n. This means that we need some procedure to generate a balanced set of size n for any n, and we have to prove that it is indeed a balanced set. Without some sort of general procedure, this task is impossible.)

The pictures below show some attempts at obtaining balanced sets of even n from either nice patterns or other balanced sets. Unfortunately none of them worked out (highlighted points are examples of pairs of A and B whose perpendicular bisector does not pass through any other point of \mathcal{S}) 😦

IMO_2015_1_04

The configuration works for n = 6 but does not generalise to n = 8

The configuration works for n = 6 but does not generalise to n = 8

Reflections of an odd n-gon to build on the balanced set of size n

Reflections of an odd n-gon to build on the balanced set of size n

OK, so back to the drawing board. We are trying to find a set of points such that they lie on each other’s perpendicular bisector. Maybe we can find a set of points such that many of their perpendicular bisectors will intersect? This thought may lead us to think about the centre of a circle: any two points on the circle will have their perpendicular bisector pass through the centre! In fact, we may see that the case of n = 4 can be obtained in this fashion:

IMO_2015_1_07
Let’s say we start with a basic configuration of 1 point on the centre of the circle and the remaining n - 1 points on the circle itself. If I choose any two points on the circle itself, clearly the centre of the circle lies on the perpendicular bisector. It remains to ensure that for any line segment joining the centre of the circle to a point on the circle, a point of \mathcal{S} lies on its perpendicular bisector.

This is easy to guarantee with the following construction. Start off with the 4 points that form the balanced set for n = 4. Denote the centre of the circle by O. If the total number of points is less than n, add 2 points A and B on the circle such that \triangle OAB is an equilateral triangle. It can be seen that the resulting set is still a balanced set. (In your solution, you must justify why it is indeed balanced, it is not good enough to claim that this construction “obviously” works.)

Here are some possible configurations for n = 6, 8, 10 to give a better idea of the construction:

IMO_2015_1_08

And we are done with part (a)! 🙂

On to part (b). For which integers n \geq 3 does there exist a centre-free balanced set of n points?

The first step is to check if any of the balanced sets we have generated so far are already centre-free. It is easy to check that for odd n, the n-gon configuration is indeed a centre-free balanced set. Awesome!

We are now left to figure out if there are centre-free balanced sets of even n size. Clearly there is no centre-free balanced set of size 4, and the balanced sets that our construction for even n gives is not centre-free (the centre of the circle is well, a centre). This may lead us to the guess that there are no even-sized centre-free balanced sets.

How would we prove such a thing? Well, recall that every perpendicular bisector of 2 points in \mathcal{S} must pass through a point of \mathcal{S}. There seem to be a lot more perpendicular bisectors than points, so maybe we can get some sort of impossibility proof from there?

To be precise, let n = 2k for some integer k \geq 2. There are 2k points in \mathcal{S} and \binom{2k}{2} = k(2k - 1) perpendicular bisectors that have to pass through them. By the Pigeonhole Principle, this means that one of the points (call it P) must lie on at least

\lceil \displaystyle\frac{k(2k-1)}{2k} \rceil = \lceil \displaystyle\frac{2k-1}{2} \rceil = k perpendicular bisectors.

Let \{ A_1, B_1 \}, \dots \{ A_k, B_k \} be the k pairs of points whose perpendicular bisectors pass through P. Clearly none of the A_i‘s and B_i‘s can be P itself. However, there are only 2k-1 remaining points to choose from. Hence, there must be 2 pairs, say \{ A_1, B_1 \} and \{A_2, B_2\} which overlap, i.e. have a common element. Since they are distinct pairs, we can conclude that the set \{ A_1, B_1, A_2, B_2 \} has size 3, and all the points in this set have the same distance from P, implying that P is a centre.

Hence, there are no centre-free balanced sets of even size. The answer to (b) is odd n. Done!

Advertisements
This entry was posted in Grade 12, Intl/Regional and tagged , , , . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s