Note that the sum of the coordinates of the points is constant, so the desired point must be the centroid. To show that $n$ a power of $2$ works, proceed by induction on $\log_2 n$ by pairing up points and sending each pair to their midpoints, resulting in $2$ identical sets of $\frac{n}{2}$ points, which can be sent to their (identical) centroids by induction as desired. Now if $n$ is not a power of $2$, consider the set of points consisting of $1$ copy of $(1,0)$ and $n-1$ copies of $(0,0)$. The centroid is then $(\frac{1}{n},0)$. Note that the given operation, when applied to these points, will only allow the coordinates to be reduced fractions with a denominator a power of $2$. But $n$ is not such a number, so this arrangement is not collapsible.

Here's a solution very similar to the above. The if part is identical ,so i am going to give a slightly different proof for the only if part. We want to show that if $n$ has an odd divisor other than $1$,then there exists an arrangement of $n$ points which is not collapsible. Let's put the tokens in the number line,more specifically put $2$ tokens at number $2$,and the next tokens in progressive powers of two one by one.Let the number where the token is located by the weight of the token. Initially the total weight is $2^n$. Furthermore,it is easy to see that the total weight remains invariant at every operation. If somehow,me manage to get all the tokens end up at one single point ,then this means that there exist positive integers $t$ and $s$ such that $\frac{n \cdot t}{2^s}=2^n$ or $n \cdot t=2^{n+s}$,which is a contradiction since the $LHS$ has an odd divisor other than $1$,but the $RHS$ does not. Hence,$n$ must be a power of two.

Amir Hossein wrote: 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$. Nice Problem! We set up the co-ordinate plane. Let the weight of a token be the sum of its $x$ and $y$ coordinates. Note that the total weight of all the tokens remains invariant.Thus if the arrangement is collapsible, the tokens will meet at point with co-ordinates $((x_1+x_2+...x_n)/n , (y_1 +y_2 +..y_n)/n)$. Let us take an arrangement of $n$ tokens with $(n-1)$ of them at one point and $1$ token at another point. Its easy to see that no matter what the coordinates of the point are, every time we ' fuse' $2$ points, the new coordinates are of form $a/2^k$ .This the final point they meet will also be of this form. Also we can choose $s$ and $t$ the coordinates of the set of $n-1$ points and the lone point such that $n$ and $(x_1 +x_2 +..x_n)$ are coprime forcing $n=2^k$ for some integer $k$. Now we prove any arrangement of $2^k$ tokens is collapsible. For this we proceed by Induction. Base case is obvious. Now we make pairs of points which is possible and fuse every pair.(Points with same coordinate fuse to become the same point). Now we get $2^{k-1}$ packets of fused points. Now we apply induction and on these points and thus each point's partner moves along with it throughout. Thus we can fuse all points and the arrangement is 'collapsible'. Hence proved!

If $n=2^k$, $n$ tokens are obviously collapsible. If not, note that the tokens have to meet at their centroid. Take $n-1$ copies of $(0,0)$ and one copy of $(1,0)$. They have to meet at $(\frac{1}{n},0)$, but all locations of each token have coordinates of the form $(\frac{a}{2^k},0)$. Therefore, $n$ must be a power of $2$ for this set of tokens to be collapsible. Done.

If part is very trivia. If $n=2^k $ we can find even number of point where they containing odd numbers of tokens.We can pair this odd number such that in every pair $2 $ elements { $2^x-(2m+1), 2m+1$} sum up at $2^x$. Repeatedly applying this proccess we can obtain at a moment such that in every points there must have$ 2^t $coins for a positive $t$.

This is a Combinatorical function equation .First we are going to plug in some special points to see $n$ must be a power of $2$.For this we notice that if points have integer coordinate then any point achived by taking mean of points have a rational coordinate with denomiter a power of $2$.However the sum of coordinates still invarient with this moves so if one can have all the points in one place the coordinate of that point will be the mean of all $n$ points.This motivates a lot of constructions for example $n-1$ points on $(0,0)$ and one point on $(0,k)$ which quickly implies that $n$ should be a power of $2$.Now for showing every power of $2$ is collapsible we make use of induction let $n=2^k$ we induct on $k$.The base case is trivial.for inductive step split $2^{k+1}$ points into two parts with $2^k$ points.Apply the inductive hypopeties to bot now we have two position that in every of them there are $2^k$ points.Now just pair points in different positions and apply the move to each pair.

I'm just thinking out loud here, but this should be relatively easy to generalize, shouldn't it? By that I mean: If, instead of utilizing pairs of tokens, a move is defined by selecting k tokens and moving all of them to their geometric centre, then we can prove that every arrangement of n tokens is collapsible if and only if n is a power of k. Correct? In addition, we should be able to trivially extrapolate our proof to show that this is true for an arrangement of tokens in any m-dimensional space, and not just a plane. Correct?

SixForty wrote: I'm just thinking out loud here, but this should be relatively easy to generalize, shouldn't it? By that I mean: If, instead of utilizing pairs of tokens, a move is defined by selecting k tokens and moving all of them to their geometric centre, then we can prove that every arrangement of n tokens is collapsible if and only if n is a power of k. Correct? In addition, we should be able to trivially extrapolate our proof to show that this is true for an arrangement of tokens in any m-dimensional space, and not just a plane. Correct? Lemma: At some point, the tokens must be in an arrangement where exactly $\frac{n}{2}$ tokens are at 2 points if it is collapsible for every arrangement of tokens. Proof: We know that right before the last move, the tokens must be at 3 points where there is 1 token at 1 point, another token at 1 point, and n-2 tokens at the midpoint of these. The only way to get to this state which works for every arrangement is for $\frac{n}{2}$ tokens to be at 2 points and to move points to the midpoint of these until the midpoint has n-2 tokens. This is because if there was a different way, then it wouldn't be true for every arrangement because if you moved one of the points you are using, the outcome would be different. Since there should be n/2 tokens at 2 points, this means that n/2 tokens should also be collapsible for every arrangement. 2 tokens is clearly collapsible, so the next collapsible number of tokens for every arrangement of them can be $a_n$ where $a_1=2$, and $a_n=2a_{n-1}$, which is the same recursive formula for the powers of 2. This can be generalized for any dimension.

adamov1 wrote:

"Now if $n$ is not a power of $2$, consider the set of points consisting of $1$ copy of $(1,0)$ and $n-1$ copies of $(0,0)$. The centroid is then $(\frac{1}{n},0)$. Note that the given operation, when applied to these points, will only allow the coordinates to be reduced fractions with a denominator a power of $2$. But $n$ is not such a number, so this arrangement is not collapsible." I don't quite understand the logic of this part of the solution, if you are trying to prove that any arrangement of $n$ tokens, where $n$ is not a power of 2, is non-collapsible, how can you just consider one specific example to arrive at a conclusion for any arrangement of $n$ tokens?

Anyone??

Amir Hossein wrote: 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$. Nice problem. If $n = 2^k$ for $k \in \mathbb{N}$, we induct on $k$ with $k = 1$ base case and see that if for all $k_1 \leq k$ we can make all tokens coincide, then for $n = 2^{k_1+1}$ tokens, we randomly pair up tokens and move each pair of tokens to their midpoint, and complete using induction hypothesis. If $n$ is not a power of $2$, then we consider the usual Cartesian plane co-ordinates and place $n-1$ tokens at the origin and $1$ token at $(0,1)$. If all tokens are coinciding, then it must be at point $(0, \frac{1}{n})$ but given any moment, the co-ordinate of any point is of form $(0, \frac{z}{2^p})$ for $(z, p) \in \mathbb{Z}_{\geq 0}$ but this means it can never be $(0, \frac{1}{n})$ which is the desired conclusion @below khina has mentioned it, but still here you go, look at bold words below Amir Hossein wrote: 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$.

@above How did you just consider one specific set up, being $n - 1$ tokens at the origin and 1 token at $(0, 1)$ and draw a conclusion about all arrangements?

@above It asks to prove that it holds for ALL configurations if and only if $n$ is a power of $2$. What they did is prove that there exists SOME configuration when $n$ isn't a power of $2$, that doesn't work. This implies that it doesn't hold that ALL configurations work, which is what they want to prove for when $n$ isn't a power of $2$.

Please ??? provide a graph theory solution to these 2 P1 Suppose in a group of n people each one has at most 3 enemies Prove that the group can be partitioned into 2 subgroups ST each member has at most 1 enemy in the subgroup to which he belongs P2 2n people have assembled together around a circular table, each one having at most n-1 enemies and at least n friends Show that there exists a circular arrangement of these 2n people where no hostile pair sits adjacent to each other Please help this noob

@2above OHHHHH, ty for explaining!

Imagine the tokens as points on a number line, label them $a_1, a_2, \cdots, a_k$. Notice that if $k=2^{n}$ for integer $n,$ then the algorithm for collapsing is simple: just average the two on the left, the two on the right, the remaining two on the left, the remaining two on the rights, etc. It is easy to see that all the numbers will come to be $\frac{a_1+a_2\cdots a_k}{k}$ because $k$ is a power of $2$. We now prove that all other arrangements don't hold. An invariant is the sum, so this means that the number that all of the $a_i$ for $1\leq I\leq k$ collapse to is fixed, namely, it is $\frac{a_1+a_2+\cdots a_k}{k}$. Notice that the process given in the problem always results in averages with weights of $\frac{1}{2^c}$ for some integer on some number of $a_i$. Therefore, if $k$ is not a power of $2$(and it is easy to choose specific values of $a_i$ so that the numerator and denominator of the fraction are relatively prime, so there is no chance of the "odd" part of the denominator cancelling out) then there is no way to achieve such an average, so we are done.

$\textbf{1. }$ Every arrangement of $n$ tokens is collapsible if $n$ is a power of $2$. We prove this by induction. Base case. One token is collapsible. Inductive assumption. We have $2^{n+1}$ tokens on each of the points $S=\{(a_n,b_n)\}$. Inductive step. We can divide $S$ into two equinumerous subsets $S_1$ and $S_2$. The $n$th element of $S_1$ and the $n$th element of $S_2$ are paired, and for each pairing, we collapse the tokens. Then it reduces to a $2^n$ token configuration. $\blacksquare$ $\textbf{2. }$ Some arrangement of $n$ tokens is not collapsible if $n$ is not a power of $2$. Let the $n$ tokens be on the $x$-axis. Then the tokens must collapse to the point whose $x$-value is the arithmetic mean of their $x$-values. An example of where this is impossible is when all but one token is on the origin, and the other is at $(1,0)$. Then they must meet at $\left(\frac1n,0\right)$. Since we take the midpoint of any two tokens, only integral multiples of negative powers of two are achievable. However, this must mean that $\frac1n$ is of the form $\frac a{2^b}$, for $a,b\in\mathbb Z$. WLOG, $a$ is odd, so it must be $1$, and thus $n$ is a power of two, contradiction. $\blacksquare$ The proof is done. $\square$

We claim by induction that powers of two are collapsible. For the base case $n=2^0,$ the result is clear. For the inductive step, assume $n=2^k$ is collapsible. Then, split $n=2^{k+1}$ into two sets of $2^k$ and collapse the sets so that half the tokens are at one point and the other half at another point. Then, through $2^k$ moves, we can move all the tokens to the midpoint of the two points by pairing off coins from the two sets. Next, we claim that for $n$ not power of two, all arrangements such that the $x$ coordinates of the tokens are integers and their sum is not divisible by $n$ fail. Such an arrangement clearly exists. If the tokens are placed at $(x_i,y_i)$ for $1\le i\le n,$ the sum of the $x$ coordinates is an invariant so if $n$ is collapsible, each $x$ coordinate will eventually be $(x_1+\dots+x_n)/n.$ But each token can only move to coordinates of the form $x_1/2^{\alpha_1}+\dots+x_n/2^{\alpha_n}$ so $$\frac{x_1+\dots+x_n}{n}=\frac{x_1}{2^{\alpha_1}}+\dots+\frac{x_n}{2^{\alpha_n}}.$$This is absurd as the p-adic valuation of the left hand side is negative for any $p\mid n,$ $p\neq 2,$ while the p-adic valuation is non-negative for the right hand side. $\square$

The answer is all powers of 2. For a construction, we can just work inductively, where we can combine all $2^{k+1}$ points into $2^k$ midpoints, each of which has two points. From there, we can repeat the construction for $k$ twice using the inductive hypothesis. To show that the other $n$ do not work, consider the configuration where $n-1$ of the points are at $(0, 0)$ and the last one is at $(1, 0)$. As the operation does not change the sum of the coordinates, the final collapsible point must be $\left(\frac 1n, 0\right)$. But it's clear that the only points that tokens can ever reach must be of the form $\left(\frac i{2^k}, 0\right)$, but $n$ is not a power of $2$, so no token can ever reach this final point, contradiction.

All powers of two. Proof. First we will prove that all non-powers of $2$ do not work. We will do this by constructing a configuration of $n$ coins that is not collapsible for some positive integer $n$ that is not a perfect power of $2$. We can do this by placing $n-1$ of the coins at the origin and the remaining coin at the point $(1,0)$. The sum of the $x$-coordinates of all of these points will always remain the same(since we are just taking the average every time we make a move on two coins), but notice that if we express all of these $x$-coordinates as fractions, their denominators must always be powers of $2$. This is a contradiction because we would like to end up with all of the $x$-coordinates being $\frac{1}{n}$, with $n$ not being a power of $2$, and therefore non-powers of $2$ do not work. Now we will prove that all powers of $2$ work by giving a strategy to collapse all the coins. Notice that if you have two groups of coins of the same size on two different points, these coins are collapsible, since we can pair the coins and have them all end up at the midpoint of these two points. With powers of $2$, we start with $n=2^k$ groups of $1$ coin each, which we can collapse to $2^{k-1}$ groups of $2$ coins each, and so on and so forth until we end up with one group of $2^k$ points. Thus we have proved that all powers of $2$ work and we are done.

We claim that the answer is all $n$ in the form of $2^k$. We will use induction to show this. Base Case: $n = 2$ clearly works. Inductive Step: Assume the system is collapsible for $2^k$ and we wish to prove it for $2^{k+1}$. Clearly we can divide the $2^{k+1}$ tokens into two $2^k$ piles which can be collapsed. Hence, $2^{k+1}$ can be collapsed. Now we show that only numbers in the form of $2^k$ are collapsable. Assume that we have $n$ tokens where $n \not= 2^k$. Note that if we put $n-1$ tokens at $(0,0)$ and the last token at $(1,0)$ they must collapse at the point $(\tfrac{1}{n}, 0)$. But by repeatedly taking the midpoint, our denominator must be a power of 2, contradicting our assumption. Hence only numbers of the form $2^k$ are collapsable.

Mogmog8 wrote: But each token can only move to coordinates of the form $x_1/2^{\alpha_1}+\dots+x_n/2^{\alpha_n}$ so $$\frac{x_1+\dots+x_n}{n}=\frac{x_1}{2^{\alpha_1}}+\dots+\frac{x_n}{2^{\alpha_n}}.$$This is absurd as the p-adic valuation of the left hand side is negative for any $p\mid n,$ $p\neq 2,$ while the p-adic valuation is non-negative for the right hand side. $\square$ Wowwwww very clever thinking :O

For $n=1$ case the sequence is is collapsible, by inductive hypothesis we assume is it is true for $n=2^k$ and now we prove for $n=2^{k+1}$, notice that for $2^{k+1}$ we can divide the sequence of tokens into two parts of $2^k$ size which are collapsible and then collapcing the two points into a single point so the arrangements of $2^{k+1}$ tokens is also collapsible. Now to prove that no other form other than arrangements of $2^k$ is collapsible. If we place all the tokens on non-negative integer positions on a real number line we will observe that the sum of the $x$-coordinates of all the tokens on a number line remains the same or is an INVARIANT, each $x$-coordinate will collapse to $\displaystyle \frac{(x_1+x_2+...+x_n)}{n}$, this is a contradiction. because eventually the token can only move to a position with a denominator of a power of $2$, so for an arrangement n should be a power of $2$.

If $n$ is a power of $2$ we can keep on putting the tokens in groups of $2$ from which our construction is simple. If $n$ is not a power of $2$ then put the tokens on the number line in $1$, $2$, $4$, $\dots$, $2^{n-1}$. Note the final spot for which the tokens must end up at is fixed since the sum of each of the tokens on the number line is invariant. So the point on the number line where the tokens must end up is $\frac{2^n-1}{n}$. However the denominator of any token on the number line must be a power of $2$ so the coins can't reach the final position if $n$ is not a power of $2$, done.

We claim only powers of 2 work. We prove the necessity first. We will induct on the exponent $2^k$ , $\forall k \ge 0$. For $k = 0$ we have $2^0=1$ which is obviously true. We assume the truth for $n = 2^k$. Now split $2^{k+1}$ into two piles of $w^k$, which we assumed to be collapsible. We can pair up one pile on one point and the other half on another point , to which they will collapse to their midpoint. We now prove that non powers of two won't work. First assume the contrary. Place $n-1$ points on the origin and 1 point at the point $(1,0).$ As the total sum of the coordinates after any individual move is invariant, the final collapsible point will be )$(\frac 1 n,0 )$ However when we repeatedly take the midpoint , we end up wiht a denominator with a power of 2, contradicting our assumption. \end{proof}

The answer is $n = 2^k$ where $k$ is a nonnegative integer. To show this works, an induction-type argument can be used. For $k=0,$ do nothing. Otherwise, pair up tokens and perform a move on each pair, and repeat the argument on $k-1$ twice. To show necessity, suppose that we have a prime $p > 2$ dividing $n.$ We can put the $i$th token at a lattice point $(x_i, y_i)$ such that the sum of the $x_i$ is not divisible by $p.$ Then because the sum of coordinates is invariant, the coordinates of the final point is $\left(\frac{x_1 + \dots + x_n}{n}, \frac{y_1 + \dots + y_n}{n}\right).$ Since $p \mid n$ and doesn't divide the first sum, we need to somehow divide by $p$ when we can only divide by $2.$ This is impossible, hence $n$ must be a power of $2,$ as desired. Remark: One could just set $y_i = 0$ for all $i$, $x_i = 0$ for $i \ge 2,$ and $x_1 = 1.$ This would also do the trick, but our approach is more general.