Collapsible arrangements [CMO 2018

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Amir Hossein

5452 posts

Amir Hossein

#1 h Mar 31, 2018, 2:09 AM • 8 Y

Y by Smita, phymaths, Math-Ninja, Davi-8191, Nymoldin, Danielzh, Adventure10, Mango247

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$ .

This post has been edited 1 time. Last edited by Amir Hossein, Mar 31, 2018, 2:14 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

adamov1

355 posts

adamov1

#2 h Mar 31, 2018, 2:18 AM • 5 Y

Y by Amir Hossein, hansu, ESCmath, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mathdragon245

133 posts

Mathdragon245

#3 h Apr 1, 2018, 9:05 AM • 3 Y

Y by Amir Hossein, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

phymaths

264 posts

phymaths

#4 h Apr 4, 2018, 12:32 PM • 2 Y

Y by Adventure10, Mango247

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!

Motivation

This post has been edited 3 times. Last edited by phymaths, Apr 4, 2018, 12:49 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rkm0959

1721 posts

rkm0959

#5 h Apr 12, 2018, 1:18 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Durjoy1729

221 posts

Durjoy1729

#6 h Jan 4, 2019, 5:49 AM • 5 Y

Y by Digonta1729, potentialenergy, DonaldJ.Trump, Adventure10, Mango247

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 post has been edited 3 times. Last edited by Durjoy1729, Jan 4, 2019, 5:52 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Taha1381

816 posts

Taha1381

#7 h Mar 11, 2019, 3:47 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SixForty

1 post

SixForty

#8 h May 21, 2020, 3:20 AM

Y by

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

babygrogu

46 posts

babygrogu

#9 h Nov 14, 2020, 1:37 PM

Y by

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.

This post has been edited 2 times. Last edited by babygrogu, Nov 21, 2020, 7:45 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

heheXD1

429 posts

heheXD1

#10 h Mar 11, 2021, 2:04 AM

Y by

adamov1 wrote:

Click to reveal hidden text

"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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

heheXD1

429 posts

heheXD1

#11 h Mar 11, 2021, 6:22 AM • 3 Y

Y by Mango247, Mango247, Mango247

Anyone??

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

508669

1040 posts

508669

#12 h Mar 11, 2021, 5:37 PM • 1 Y

Y by Mango247

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$ .

This post has been edited 1 time. Last edited by 508669, Mar 12, 2021, 5:12 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

heheXD1

429 posts

heheXD1

#13 h Mar 11, 2021, 10:45 PM

Y by

@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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

khina

993 posts

khina

#14 h Mar 12, 2021, 12:39 AM • 1 Y

Y by heheXD1

@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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Returner

11 posts

Returner

#15 h Mar 12, 2021, 4:42 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

heheXD1

429 posts

heheXD1

#16 h Mar 13, 2021, 2:12 AM • 1 Y

Y by Mango247

@2above OHHHHH, ty for explaining!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JustKeepRunning

2958 posts

JustKeepRunning

#17 h Apr 18, 2021, 1:55 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jasperE3

11133 posts

jasperE3

#18 h Apr 22, 2021, 3:39 AM

Y by

$\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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mogmog8

1080 posts

Mogmog8

#19 h Nov 19, 2022, 5:21 PM • 2 Y

Y by centslordm, Danielzh

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8857 posts

HamstPan38825

#20 h Dec 17, 2022, 3:14 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

peppapig_

279 posts

peppapig_

#21 h Feb 10, 2023, 5:21 PM • 1 Y

Y by mulberrykid

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

coolmath_2018

2807 posts

coolmath_2018

#22 h Feb 23, 2023, 7:51 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RedFireTruck

4221 posts

RedFireTruck

#23 h Apr 12, 2023, 10:17 PM

Y by

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Danielzh

481 posts

Danielzh

#24 h May 14, 2023, 12:45 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

L13832

252 posts

L13832

#25 h Jul 12, 2024, 11:20 PM

Y by

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$ .

This post has been edited 1 time. Last edited by L13832, Jul 27, 2024, 5:34 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dolphinday

1318 posts

dolphinday

#26 h Jul 19, 2024, 12:51 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Topiary

22 posts

Topiary

#27 h Jul 22, 2024, 2:05 PM

Y by

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}

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EpicBird08

1740 posts

EpicBird08

#28 h Jul 31, 2024, 6:58 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Saucepan_man02

1300 posts

Saucepan_man02

#29 h Jan 29, 2025, 7:12 AM

Y by

Plot the problem in argand plane:

Let each vertex be denoted by $z_k$ . Note that: $\sum z_k$ is constant, thus the final point for any collapsible arrangement must be the centroid.
If $n$ is a power of $2$ , we clearly see by induction that its collapsible.
If not, then consider $z_1=1, z_2=z_3=\cdots=z_n=0$ which has a centroid of $(\tfrac{1}{n}, 0)$ . But, notice that, after every move, we must have every point's real part to be of the form $\tfrac{1}{2^k}$ (or $0$ itself), which leads to contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ilikeminecraft

328 posts

Ilikeminecraft

#30 h Mar 26, 2025, 4:35 PM

Y by

The answer is all powers of 2. To do 2, it is trivial by induction.
For non powers of 2, line them up on the number line. Then, put $n - 1$ at 0 and one is at $1.$ It is obvious that the sum of all numbers will always be 1. However, all of them must also have finitely many number of 1/0s in the binary expansion. This finishes.

Z K Y