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 A and B and move both of them to the midpoint of A and B.
We say that an arrangement of n tokens is collapsible if it is possible to end up with all n tokens at the same point after a finite number of moves. Prove that every arrangement of n tokens is collapsible if and only if n is a power of 2.
Solution
Solution:
For a given positive integer n, consider an arrangement of n tokens in the plane, where the tokens are at points A1,A2,…,An. Let G be the centroid of the n points, so as vectors (after an arbitrary choice of origin), G=nA1+A2+⋯+An Note that any move leaves the centroid G unchanged. Therefore, if all the tokens are eventually moved to the same point, then this point must be G.
First we prove that if n=2k for some nonnegative integer k, then all n tokens can always be eventually moved to the same point. We shall use induction on k.
The result clearly holds for n=20=1. Assume that it holds when n=2k for some nonnegative integer k. Consider a set of 2k+1 tokens at A1,A2,…,A2k+1. Let Mi be the midpoint of A2i−1 and A2i for 1≤i≤2k.
First we move the tokens at A2i−1 and A2i to Mi, for 1≤i≤2k. Then, there are two tokens at Mi for all 1≤i≤2k. If we take one token from each of M1,M2,…,M2k, then by the induction hypothesis, we can move all of them to the same point, say G. We can do the same with the remaining tokens at M1,M2,…,M2k. Thus, all 2k+1 tokens are now at G, which completes the induction argument.
(Here is an alternate approach to the induction step: Given the tokens at A1,A2,…,A2k+1, move the first 2k tokens to one point G1, and move the remaining 2k tokens to one point G2. Then 2k more moves can bring all the tokens to the midpoint of G1 and G2.)
Now, assume that n 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 n−1 tokens at 0 and one token at 1. We observed that if we can move all the tokens to the same point, then it must be the centroid of the n points. Here, the centroid is at n1. 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 2am, where m is an integer and a is a nonnegative integer.)
Proof. Consider two dyadic rationals 2a1m1 and 2a2m2. Then their average is 21(2a1m1+2a2m2)=21(2a1⋅2a22a2⋅m1+2a1⋅m2)=2a1+a2+12a2⋅m1+2a1⋅m2 which is another dyadic rational.
On this real number line, a move corresponds to taking a token at x and a token at y and moving both of them to 2x+y, the average of x and y. At the start, every token is at a dyadic rational (namely 0 or 1), which means that after any number of moves, every token must still be at a dyadic rational.
But n is not a power of 2, so n1 is not a dyadic rational. (Indeed, if we could express n1 in dyadic form 2am, then we would have 2a=mn, which is impossible unless m and n are powers of 2.) This means that it is not possible for any token to end up at n1, let alone all n tokens.
We conclude that we can always move all n tokens to the same point if and only if n 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.