Maths Olympiad Prep

Library / /52 of 61

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Canada

Problem:

Consider an arrangement of tokens in the plane, not necessarily at distinct points. We are allowed to apply a sequence of moves of the following kind: Select a pair of tokens at points AA and BB and move both of them to the midpoint of AA and BB.

We say that an arrangement of nn tokens is collapsible if it is possible to end up with all nn tokens at the same point after a finite number of moves. Prove that every arrangement of nn tokens is collapsible if and only if nn is a power of 2.

Solution

Solution:

For a given positive integer nn, consider an arrangement of nn tokens in the plane, where the tokens are at points A1,A2,,AnA_{1}, A_{2}, \ldots, A_{n}. Let GG be the centroid of the nn points, so as vectors (after an arbitrary choice of origin),
G=A1+A2++Ann \vec{G}=\frac{\vec{A}_{1}+\vec{A}_{2}+\cdots+\vec{A}_{n}}{n}
Note that any move leaves the centroid GG unchanged. Therefore, if all the tokens are eventually moved to the same point, then this point must be GG.

First we prove that if n=2kn=2^{k} for some nonnegative integer kk, then all nn tokens can always be eventually moved to the same point. We shall use induction on kk.

The result clearly holds for n=20=1n=2^{0}=1. Assume that it holds when n=2kn=2^{k} for some nonnegative integer kk. Consider a set of 2k+12^{k+1} tokens at A1,A2,,A2k+1A_{1}, A_{2}, \ldots, A_{2^{k+1}}. Let MiM_{i} be the midpoint of A2i1A_{2 i-1} and A2iA_{2 i} for 1i2k1 \leq i \leq 2^{k}.

First we move the tokens at A2i1A_{2 i-1} and A2iA_{2 i} to MiM_{i}, for 1i2k1 \leq i \leq 2^{k}. Then, there are two tokens at MiM_{i} for all 1i2k1 \leq i \leq 2^{k}. If we take one token from each of M1,M2,,M2kM_{1}, M_{2}, \ldots, M_{2^{k}}, then by the induction hypothesis, we can move all of them to the same point, say GG. We can do the same with the remaining tokens at M1,M2,,M2kM_{1}, M_{2}, \ldots, M_{2^{k}}. Thus, all 2k+12^{k+1} tokens are now at GG, which completes the induction argument.

(Here is an alternate approach to the induction step: Given the tokens at A1,A2,,A2k+1A_{1}, A_{2}, \ldots, A_{2^{k+1}}, move the first 2k2^{k} tokens to one point G1G_{1}, and move the remaining 2k2^{k} tokens to one point G2G_{2}. Then 2k2^{k} more moves can bring all the tokens to the midpoint of G1G_{1} and G2G_{2}.)

Now, assume that nn is not a power of 2. Take any line in the plane, and number it as a real number line. (Henceforth, when we refer to a token at a real number, we mean with respect to this real number line.)

At the start, place n1n-1 tokens at 00 and one token at 11. We observed that if we can move all the tokens to the same point, then it must be the centroid of the nn points. Here, the centroid is at 1n\frac{1}{n}. We now prove a lemma.

Lemma. The average of any two dyadic rationals is also a dyadic rational. (A dyadic rational is a rational number that can be expressed in the form m2a\frac{m}{2^{a}}, where mm is an integer and aa is a nonnegative integer.)

Proof. Consider two dyadic rationals m12a1\frac{m_{1}}{2^{a_{1}}} and m22a2\frac{m_{2}}{2^{a_{2}}}. Then their average is
12(m12a1+m22a2)=12(2a2m1+2a1m22a12a2)=2a2m1+2a1m22a1+a2+1 \frac{1}{2}\left(\frac{m_{1}}{2^{a_{1}}}+\frac{m_{2}}{2^{a_{2}}}\right)=\frac{1}{2}\left(\frac{2^{a_{2}} \cdot m_{1}+2^{a_{1}} \cdot m_{2}}{2^{a_{1}} \cdot 2^{a_{2}}}\right)=\frac{2^{a_{2}} \cdot m_{1}+2^{a_{1}} \cdot m_{2}}{2^{a_{1}+a_{2}+1}}
which is another dyadic rational.

On this real number line, a move corresponds to taking a token at xx and a token at yy and moving both of them to x+y2\frac{x+y}{2}, the average of xx and yy. At the start, every token is at a dyadic rational (namely 00 or 11), which means that after any number of moves, every token must still be at a dyadic rational.

But nn is not a power of 2, so 1n\frac{1}{n} is not a dyadic rational. (Indeed, if we could express 1n\frac{1}{n} in dyadic form m2a\frac{m}{2^{a}}, then we would have 2a=mn2^{a}=m n, which is impossible unless mm and nn are powers of 2.) This means that it is not possible for any token to end up at 1n\frac{1}{n}, let alone all nn tokens.

We conclude that we can always move all nn tokens to the same point if and only if nn is a power of 2.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.