MarkBcc168 wrote:

What is $\text{rad}$?

$\mathrm{rad}(n)$ is the largest squarefree divisor of $n$.

Another construction for $(2p, p),$ where $p$ is an odd prime. Dismiss the trivial case when $p-1$ is a power of $2$ and write $p=2^a+2^b+C$ with $a>b$ being the biggest exponents of $2$ in the binary expansion of $p.$ Not hard to see that we can mark the centroid of any $2^k$ numbers for $k\ge 0.$ Mark the following centroids: $$g=\frac{x_1+\cdots+x_{2^a}}{2^a}, g_1=\frac{x_{2^a+1}+x_{2^a+2}}{2}, \cdots, g_C=\frac{x_{2^a+2C-1}, x_{2^a+2C}}{2}, t_1=\frac{x_{2^a+2C+1}}{1}, \cdots, t_{2^b-C}=\frac{x_p}{1}$$Now mark the following $2^b$ points: $$\frac{(p-2^b)g+2^bt_1}{p}, \frac{(p-2^b)g+2^bt_2}{p}, \cdots, \frac{(p-2^b)g+2^bt_{2^b-C}}{p} \ \ \ \text{and} \ \ \ \frac{(p-2^{b+1})g+2^{b+1}g_1}{p}, \frac{(p-2^{b+1})g+2^{b+1}g_2}{p}, \cdots, \frac{(p-2^{b+1})g+2^{b+1}g_C}{p}$$And finally mark the centroid of all these $2^b$ numbers, which happens to be exactly what we need.

Quote: Let $m, n \ge 2$ be integers. Carl is given $n$ marked points in the plane and wishes to mark their centroid.* He has no standard compass or straightedge. Instead, he has a device which, given marked points $A$ and $B$, marks the $m-1$ points that divide segment $\overline{AB}$ into $m$ congruent parts (but does not draw the segment). For which pairs $(m,n)$ can Carl necessarily accomplish his task, regardless of which $n$ points he is given?

Wizard_32 wrote: Cool problem no no no , seriously no, not cool at all, bad problem Carl

Here's my solution which I found after submitting the solutions for Day 1, in which I will just show the construction of $2p$ in $p$ vertices and the rest is same as the others: Well first of all let the complex coordinates of the points be $a_1,a_2,...a_p$. First of all the scale allows us to create $\frac{a_ik+a_jl}{k+l}$ where $(k,l)$ is any pair of nonnegative integers adding up to $p$. The main idea is to take the average of appropriate tuples to eventually reach $\frac{a_ib_1+a_jb_2+...a_xb_p}{p}$ where $(b_1,b_2,b_3,...b_p)$ is any $p-tuple$ of nonnegative integers adding to $p$ so that we can put all $b_i$ as $1$ to reach the centroid. First we will take appropriate pairs whose average will give any desired triple with sum of elements $p$. One can see this is easily doable. If we want, say, $k,l,m$ as the triple(of course $k+l+m=p$)on $a_1,a_2,a_3$ respectively and WLOG $k \leq l \leq m$(otherwise we can just take whatever the order is in ascending order with corresponding points) Then we can take the 2 points, first one formed by the pairs $2k,p-2k$ and by the points $a_1,a_3$ respectively, and the other point being formed by $2l,p-2l$ with the points $a_2,a_3$ respectively, take their average(as $2|2p$) to get the desired triple. So we can always get $\frac{a_pk+a_ql+a_rm}{p}$ with $k+l+m=p$. We extend this idea similarly, taking appropriate triples, averaging out to get any quadruple, and then so on and so forth until we reach a $p-tuple$ as desired. Thus, we can form $\frac{a_ib_1+a_jb_2+...a_xb_p}{p}$ as said earlier, and putting $b_i$ all equal to $1$ gives centroid. Done!

Probably the worst-written solution ever.

@below he passed bad comments about that question so give him a zero! $\phantom{Just kidding :P}$

rmtf1111 wrote: Wizard_32 wrote: Cool problem no no no , seriously no, not cool at all, bad problem Carl Hey Also, I'll provide my own construction to add to the list:

I don’t think my “construction” is here yet.

CantonMathGuy wrote: I don’t think my “construction” is here yet.

Wow, this one was ingenious! No need of providing a systematic way of construction.

This problem reminded me of this year's USAMO P5 with Evan's blackboard, so in my solution I restated the problem to be almost just like it .

CantonMathGuy wrote: I don’t think my “construction” is here yet. @CantonMathGuy would you like to share your thought process behind this ingenious solution?

We claim any $m$ works iff $m$ is even and $m$ is a multiple of the largest squarefree divisor of $n$. Represent the points in the plane as vectors $x_1,x_2,\ldots,x_n$. We want to generate $\tfrac{1}{n}x_1+\cdots+\tfrac{1}{n}x_n$. Claim: If $(m_1,n_1)$ and $(m_2,n_2)$ work, then $(\text{lcm}(m_1,m_2), n_1n_2)$ works. Proof: Split the group of $n_1n_2$ points into $n_2$ groups of $n_1$ points. We can then take the centroid of each of the groups with a $m_1$-cutter, and we can take the centroid of the resulting points with an $m_2$-cutter. So if we have a $\text{lcm}(m_1,m_2)$-cutter, we win. $\square$ Claim: $p\mid n\implies p\mid m$ for any prime $p$. Proof: At any point in the process, the vector we have is of the form $\tfrac{a_1x_1+\cdots+a_nx_n}{m^k}$ for some $k$. At the end, this must be $\tfrac{1}{n}x_1+\cdots+\tfrac{1}{n}x_n$. Hence, $\tfrac{a_i}{m^k} = \tfrac{1}{n}$, and since the RHS is fully reduced, we know $n\mid m^k$. That is, every prime $p\mid n$ also divides $m$. $\square$ Claim: $m$ is even. Proof: Suppose $m$ is odd. Then, by the above claim, $n$ must also be odd. We claim at least one coefficient in any possible linear combination we get is 0 mod 2. This will give the desired contradiction, since all the final coefficients are $\tfrac{1}{n}$, but $\tfrac{1}{n}\equiv 1\pmod2$. We induct on the length of the linear combination (the number of nonzero coefficients). The base case is when the linear combination is just $x_i$; then, all the other coefficients are 0, proving the base case. Now, any new linear combination is of the form \[ \frac{k_1}{m} \cdot \frac{a_1x_1+\cdots+a_kx_k}{m^\ell} + \frac{k_2}{m} \cdot \frac{b_1x_1+\cdots+b_rx_r}{m^s}. \]for some $k_1+k_2=m$. Since $m$ is odd, WLOG $k_1$ even, $k_2$ odd. The above becomes \[ \frac{(k_1a_1)x_1+\cdots+(k_1a_k)x_k}{m^{\ell+1}} + \frac{(k_2b_1)x_1+\cdots+(k_2b_r)x_r}{m^{s+1}}.\]All the coefficients in the first term are even since $k_1$ even. But by induction, at least one of $b_i$ is even. Hence $k_2b_i$ is also even for that $i$. Now, when we put the entire fraction with a common denominator, that $x_i$ will still have an even coefficient, completing the induction. $\square$ Claim: $(m,n)=(2p,p)$ works.

. Choose some $k$ such that $2^k>2p$. Then take the following linear combinations: First for $t=1,\ldots,p-1$, write \[ \left(\frac{(2^k \cdot t)\mod p}{p}\right) x_t+ \left(1-\frac{(2^k \cdot t)\mod p}{p}\right)x_{t+1}.\]Currently, if we sum up the above $p-1$ linear combinations, $p$ times the coefficient of $x_i$ will be \[ p\left(\frac{2^k\cdot i \mod p}{p} + 1-\frac{2^k\cdot (i-1) \mod p}{p}\right) = p+(2^k\mod p) \equiv 2^k\pmod{p}.\]So if we add in enough $x_i$'s into the sum, we can get $p$ times the coefficient of $x_i$ to be exactly $2^k$. Since for each linear combination we add to the sum, we add exactly 1 to the total sum of the coefficients, and at the end the sum is $p\cdot \tfrac{2^k}{p}=2^k$, we know that at the end we must have a total of $2^k$ linear combinations that we added to get the sum. Hence, we have $2^k$ linear combinations, and we want to take their centroid. However, we can do this just with the midpoint tool. $\square$ Now, by the above claims, for $n=p_1^{e_1}\cdots p_k^{e_k}$, we just need $m=2p_1\cdots p_k$ (or $m=p_1\cdots p_k$ if $p_1=2$), finishing the problem.

The answer is $\operatorname{rad}(2n)\mid m$. Since Carl must accomplish his task for all sets of $n$ points, it is clear that the task is equivalent to this: Carl writes the $n$ vectors $\langle1,0,0,\ldots\rangle$, $\langle0,1,0,\ldots\rangle$, $\ldots$, $\langle0,0,0,\ldots,1\rangle$ on a board. For any two vectors $\mathbf a$, $\mathbf b$ on the board and nonnegative integers $k$, $\ell$ with $k+\ell=m$, Carl can also write the vector $\tfrac km\mathbf a+\tfrac\ell m\mathbf b$. For which $m$ can Carl write $\langle\tfrac1n,\tfrac1n,\tfrac1n,\ldots,\tfrac1n\rangle$? Proof of necessity: First assume for contradiction $p\mid n$ but $p\nmid m$. It is easy to check that for any vector on the board $\mathbf v=\langle v_1,v_2,\ldots,v_n\rangle$, we have $\nu_p(v_i)\ge0$ for all $i$. Hence $\langle\tfrac1n,\tfrac1n,\ldots,\tfrac1n\rangle$ can never be written. Now suppose $n$, $m$ are both odd, and take all vectors modulo $2$. It is always true that all vectors have exactly one component $1\pmod2$, i.e.\ no new vectors modulo $2$ may be added to the board. Hence no vector congruent to $\langle1,1,\ldots,1\rangle$ may be written. Proof of sufficiency: Note that we may construct the centroid of any $T=2^t$ points so long as $m$ is even: to prove this, induct on $t$, with the base case $t=0$ given. Then for points $P_1$, $\ldots$, $P_T$, the centroid of $P_1\cdots P_T$ is the midpoint of the segment connecting the centroids of $P_1\cdots P_{T/2}$ and $P_{T/2+1}\cdots P_T$. Let $\operatorname{rad}(2n)\mid m$. Then we may divide any segment into $m^k$ congruent parts for each $k$, so we may divide any segment into $n$ congruent parts. Let $T=2^t$ be the smallest power of $2$ greater than $m$ (so that $T<2m$). Consider the $T$ row vectors $\mathbf v_1$, $\mathbf v_2$, $\ldots$, $\mathbf v_T$ of the matrix \[ \frac1n\begin{bmatrix} a_{11}&a_{12}&\cdots&a_{1n}\\ a_{21}&a_{22}&\cdots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{T1}&a_{T2}&\cdots&a_{Tn} \end{bmatrix}, \]where: $a_{11}:=n$ and $a_{1j}:=0$ for $j>1$. For each $i$, let $j$ be the greatest index such that $a_{ij}\ne0$. Then define \[a_{i+1,j}:=\min(n,T-a_{1j}-a_{2j}-\cdots-a_{ij})\quad\text{and}\quad a_{i+1,j+1}:=n-a_{i+1,j}.\] For instance, for $n=5$ we have \[ \begin{bmatrix} \textrm{---}&\mathbf v_1&\textrm{---}\\ \textrm{---}&\mathbf v_2&\textrm{---}\\ \textrm{---}&\vdots&\textrm{---}\\ \textrm{---}&\mathbf v_T&\textrm{---} \end{bmatrix} =\frac15\begin{bmatrix} 5&0&0&0&0\\ 3&2&0&0&0\\ 0&5&0&0&0\\ 0&1&4&0&0\\ 0&0&4&1&0\\ 0&0&0&5&0\\ 0&0&0&2&3\\ 0&0&0&0&5 \end{bmatrix} \]Then all $T$ vectors have at most $2$ nonzero components, all with denominators that divide $n$, so we may construct them. Furthermore the centroid of $\mathbf v_1$, $\mathbf v_2$, $\ldots$, $\mathbf v_T$ is $(\tfrac1n,\tfrac1n,\ldots,\tfrac1n)$, so we are done.

Put the points on the complex plane; say they mark the numbers $\omega_1, \omega_2, \ldots , \omega_n$. Given any two marked numbers $w$ and $z$, we may mark any number of the form $\tfrac{iw + jz}{m}$ where $i, j > 0$ satisfy $i + j = m$. I claim that our answer is for all pairs $(m, n)$ where all primes dividing $2n$ also divide $m$. For each number $N$, define $\text{rad}(N)$ as the set of primes dividing $N$. Suppose that some prime $p$ satisfies $p \mid n$, but $p \nmid m$. Every marked number at any point can be written as\[a_1\omega_1 + a_2\omega_2 + \ldots + a_n\omega_n\]for some rationals $a_1 + \ldots + a_n = 1$. This can easily be seen from induction; all original $n$ points can be written in this form, and any new point marked on the line connecting two points of this form can be written in this form as well. Furthermore, we can see that all $a_i$ can be written in not necessarily simplified form with a power of $m$ on the denominator. This again follows from induction; the original $n$ points satisfy this, and legally markable point between any two points satisfying this also satisfies this. Thus, for every marked point $c_1\omega_1 + \ldots c_n\omega_n$, every $c_i$ can be written as $\tfrac{x}{m^y}$ for nonnegative integers $x, y$ hence\[v_p(c_i) = v_p(x) - v_p(m^y) = v_p(x) \geq 0\]for all $i$. This does not hold for the centroid since $v_p(\tfrac{1}{n}) = -v_p(n) < 0$, so when $p \nmid m$ the centroid is not markable. Furthermore, we show $m$ must be even. If not, then $m$ is odd, and by our above result $n$ is odd. We claim by induction that for any point $a_1\omega_1 + \ldots + a_n\omega_n$ markable on the plane, exactly one of the $a_i$ satisfies $v_2(a_i) = 0$. This is clearly true for our original $n$ points. Since $m$ is odd, the $v_2$ of any $a_i$ for any point must be $\geq 0$. For the inductive step, suppose we have the two marked points\[e_1\omega_1 + \ldots + e_n\omega_n \text{ and } f_1\omega_1 + \ldots + f_n\omega_n.\]Given these two points, suppose we mark\[\sum_{k=1}^n \left(\frac{ie_k + jf_k}{m}\right)\omega_k\]and we consider $v_2\left(\tfrac{ie_k + jf_k}{m}\right) = v_2(ie_k + jf_k)$ for all $k$. WLOG $i$ is even and $j$ is odd. For the $n-1$ values of $k$ where $v_2(f_k) \geq 1$, the coefficient $\tfrac{ie_k + jf_k}{m}$ has a $v_2$ value of $\geq 1$. For the single value of $k$ where $v_2(f_k) = 0$, since $j$ is odd, the coefficient $\tfrac{ie_k + jf_k}{m}$ corresponding to $k$ has a $v_2$ value of $0$. So for this newly marked point, indeed $n-1$ of the coefficients have $v_2$ value $\geq 1$, and exactly one has $v_2$ value $0$, completing our induction. Thus, if the centroid is markable, then $v_2(\tfrac{1}{n})$ must simultaneously have a $v_2$ value of $0$ and $\geq 1$, impossible. We have restricted all possible pairs $(m, n)$ to satisfying $\text{rad}(2n) \subseteq \text{rad}(m)$. Now, we show for all such pairs, an explicit way of marking the centroid. It suffices to find a construction for all pairs of the form $(2p, p)$ where $p$ is prime; then, we will be able to construct the centroid for all $(2p^k, p)$, and by splitting into groups of $p$, we can construct the centroid for all $(2p^k, p^{\ell})$. Furthermore, given that we can construct the centroid for $(m_1, n_1)$ and $(m_2, n_2)$, we can clearly construct the centroid for $(\text{lcm}(m_1, m_2), n_1n_2)$ since we can first construct the centroid of $n_1$ groups of $n_2$ points then construct the centroid of the constructed $n_1$ centroids. So, we have the points $\omega_1, \ldots , \omega_p$. Each point can be represented as $(c_1, \ldots , c_p) \iff c_1\omega_1 + \ldots + c_p\omega_p$. Choose a large exponent $e$ for which $2^e >> 2p$ and construct the points\begin{align*} z_1 &= \left(\tfrac{2^e \pmod p}{p}, \tfrac{-2^e \pmod p}{p}, 0, 0, \ldots 0\right)\\ z_2 &= \left(0, \tfrac{2 \cdot 2^e \pmod p}{p}, \tfrac{2 \cdot -2^e \pmod p}{p}, \ldots , 0\right)\\ &\vdots \\ z_i &= \left(0, \ldots , \tfrac{i \cdot 2^e \pmod p}{p}, \tfrac{i \cdot -2^e \pmod p}{p}\ldots , 0\right)\\ &\vdots\\ z_{p-1} &= \left(0, \ldots , 0, \tfrac{(p-1) \cdot 2^e \pmod p}{p}, \tfrac{(p-1) \cdot -2^e \pmod p}{p}\right) \end{align*}Next, we consider the multiset $\mathcal{S}$ of points containing $z_1, \ldots , z_{p-1}$, and sufficiently many (enough to make $|\mathcal{S}| = 2^e$) copies of each $\omega_i$ so that the sum of all of the points in the multiset is\[\sum_{\text{point} \in S} \text{point} = \left(\tfrac{2^e}{p}, \tfrac{2^e}{p}, \ldots , \tfrac{2^e}{p}\right).\]This is clearly possible, because notice that if\[z_1 + \ldots + z_{p-1} = (\tfrac{a_1}{p}, \tfrac{a_2}{p}, \ldots , \tfrac{a_p}{p})\]then each\[a_i \equiv i \cdot 2^e - (i-1)2^e \equiv 2^e \pmod p.\]Clearly, we can construct the centroid of the $2^e$ points in $\mathcal{S}$, which also happens to be the centroid of the original $p$ points, thus we are done. $\blacksquare$

A very easy construction for $(m,n) = (2p,p)$ We more strongly claim that for any $n$ points $x_1,x_2,\ldots,x_n$ and any non-negative integers $a_1,a_2,\ldots,a_n$ with $\sum a_i = p$, we can create the point $$\sum_{i=1}^n \frac{a_i x_i}{p}$$We use induction on $n$ to prove this. Base case $n=1$ is trivial and $n=2$ directly follows from the given hypothesis. Now assume the assertion holds for $n=k$ ($k \ge 2$) and consider any $x_1,x_2,\ldots,x_{k+1}$ and $a_1,a_2,\ldots,a_{k+1}$. WLOG, $a_{k+1} = \max\{a_i\}$. By our induction hypothesis, we can create the points $$\frac{2 a_1 }{p} \cdot x_1 + \frac{a_{k+1} + a_2 - a_1}{p} \cdot x_{k+1} + \sum_{i=3}^{k} \frac{a_i}{p} \cdot x_i \qquad \text{and} \qquad \frac{2 a_2}{p} \cdot x_2 + \frac{a_{k+1} + a_1 - a_2}{p} \cdot x_{k+1} + \sum_{i=3}^{k} \frac{a_i}{p} \cdot x_i $$Now the average of these is our desired point, so we are done (one thing to note is that coefficient of $x_{k+1}$ is always $\ge 0$ because of the maximiality of $x_{k+1}$). $\blacksquare$

This is by far my ugliest construction but it is the only way I could get it to work. The claim is that $\text{rad}(2n) \mid m$ where $\text{rad}(x)$ is the product of all the prime divisors of $x$. Firstly any prime divisor of $n$ is very clearly necessary (take $n-1$ points to be $(0,0)$, and the last point to be $(0,1)$). Now we prove that $2$ is necessary; clearly for $n$ even this is true, so henceforth assume $n$ odd. Place $n-2$ points at $(0,0)$ and call their location $A$. Call the remaining points $B$ and $C$. We employ barycentric coordinates on triangle $ABC$. Indeed, notice that the transformations maps points $X(a,b,c)$ and $Y(x,y,z)$ to \[ (ka + (1-k)x, kb + (1-k)y, kc + (1-k)z) \]for $k=\frac{A}{n}$ where $1 \le A \le n-1$. Observe that the target point is now $\left( \frac{n-2}{n}, \frac{1}{n}, \frac{1}{n} \right).$ Now take the numerators mod $2$. If two points with the same numerator representation mod $2$ are averaged together in any manner then it remains the same. Now consider the parities $(1, 0, 0)$ and $(0, 1, 0)$. This forces \[ k, 1-k, 0. \]Since $n$ is odd, no matter what there is exactly one odd numerator. Therefore there is always exactly one odd numerator, assuming that $n$ here is odd. Thus the desired point cannot be obtained. Now for the construction (oh god) Let $n = 2^k + 2^r + l - 1$ where $0 \le l < 2^r < 2^k$, and $r$ and $k$ are as large as possible. Label the points $A_1, A_2, \cdots A_n$. Now since we have $2$ in our arsenal it is simple to mark the centroid of any $2^k$ points, so mark the centroid of $A_1$, $A_2$, $\cdots$, $A_{2^k}$, say $B$. Delete $A_1, \cdots A_{2^k}$ from the picture. Now take exactly $l$ pairs of disjoint points from the remaining $A_i$, and mark their midpoints, and label them $C_i$ for some index $i$. We now wish to construct \[ \frac{2^kB + \underset{\text{centroids of $l$ pairs}}{2\sum C_i} + \underset{\text{the remaining}}{\sum A_i}}{n}. \]Thus after some averaging (using $n$ and $2$) of the remaining points we need to end up with these weights. Note that there are precisely $2^r$ points left. Now if $l > 0$, for any point labeled $C_i$, construct the point \[ \frac{2^{r+1}C_i + (n - 2^{r+1})B}{n}. \]Indeed this is within the bounds due to $l > 0$. If $l = 0$ then none of these points exist which is good. For any point labeled $A_i$ construct the point \[ \frac{2^rA_i + (n - 2^r)B}{n}.\] Now take the centroid of the new $2^r-1$ points and $B$. Indeed, the weights of the $C_i$ and $A_i$ are trivially calculated; then observe that we have this expression for the weight of $B$: \[ \frac{l(n - 2^{r+1}) + (2^r - l - 1)(n - 2^r) + n}{n \cdot 2^r} = \frac{2^r n - 2^r l + 2^r - 2^{2r}}{2^r n } = \frac{n - l + 1 - 2^r}{n} = \frac{2^k}{n}. \] This is as desired. $\textbf{Remark.}$ Y'know the construction is probably the silliest part of this solution. I got $n=1$ through $n=7$, $n=11$, $n=23$, any $n$ with three ones in binary, any $n$ with four ones in binary where the lead digit isn't adjacent to any other $1$, and none of the methods generalized. Then I just sat down and went "oh yeah that's easy" for $2^n$ points and it was horrible, but it worked.

The answer is all $(m,n)$ with $\mathrm{rad}(2n) \mid m$. Note that if $n$ is fixed and some $m$ works, then all of its multiples do as well. Necessity: We first show that if a prime $p$ divides $n$, then it must divide $m$ as well. Otherwise, consider $n-1$ points with $x$-coordinate $0$ and $1$ point with $x$-coordinate $1$. Then by induction, any point marked has an $x$-coordinate with $\nu_p$ at least $0$, but the centroid has $x$-coordinate $\tfrac{1}{p}$: contradiction. Now we show that we must have $2 \mid m$ for $n$ odd; suppose otherwise. Let the $y$-coordinates be linearly independent over $\mathbb{Q}$, and interpret each marked point as a length-$n$ vector with nonnegative rational components summing to $1$: we start with $n$ vectors, each of which is $0$ in all but one component, and an operation of the device on points $A$ and $B$ corresponds to writing down the vectors $\lambda \vec{A}+(1-\lambda)\vec{B}$ for $\lambda=\tfrac{1}{m},\ldots,\tfrac{m-1}{m}$. Thus to mark the centroid, we must write down the vector $(\tfrac{1}{m},\ldots,\tfrac{1}{m})$ due to the linear independency. On the other hand, it is clear by induction that any vector we write down must have both components with $\nu_2$ equal to $0$ and $\nu_2$ greater than $0$, which is a contradiction. Construction: We show that $m=\mathrm{rad}(2n)$ works. If $n$ is composite, pick some $p \mid n$. Split the $n$ points into $n/p$ groups of $p$ points each. By hypothesis, we can mark the centroid of each of the $p$ points. Then hide all the other points except for the $n/p$ centroids, and mark their centroid, which is again possible by hypothesis. Therefore, it suffices to prove that we can do this when $n$ is a prime. Since $n=2$ is trivial, we just have to prove that $(m,n)=(2p,p)$ works when $p$ is an odd prime. Again interpret the operations as averaging vectors. We begin with the following claim: Claim: We can mark any vector whose components are all dyadic rationals (denominators are powers of two) at most $1$. Proof: We induct on the highest power of $2$ in the denominator, i.e. lowest $\nu_2$ term, with the base case where the minimal $\nu_2$ is $1$ being done already. For the inductive step, any vector must have an even number of components with minimal $\nu_2$—call this number $k$, so color half of them red and the other half blue. Then form two vectors, one by incrementing all the red components by $2^k$ and decrementing all the blue components by $2^k$, and the other by incrementing all the blue and decrementing all the red in the same way. Both of these vectors can be formed by hypothesis; now take their (unweighted) average. Now write $n=2^a+b$ where $a$ is maximal. Note that $$\frac{2^a}{2^a+b}\left(\underbrace{\frac{1}{2^a},\ldots,\frac{1}{2^a}}_{b\text{ terms}},\underbrace{\frac{2^a-b}{2^{2a}},\ldots,\frac{2^a-b}{2^{2a}}}_{2^a\text{ terms}}\right)+\frac{b}{2^a+b}\left(\underbrace{0,\ldots,0}_{b\text{ terms}},\underbrace{\frac{1}{2^a},\ldots,\frac{1}{2^a}}_{2^a\text{ terms}}\right)=\left(\frac{1}{2^a+b},\ldots,\frac{1}{2^a+b}\right),$$and since $2^a>b$ by maximality, we can apply our above claim and get that $(\tfrac{1}{n},\ldots,\tfrac{1}{n})$ can be formed, finishing the problem. $\blacksquare$ Remark: The construction (hardest part of the problem) was found by noting that $3$ and $5$ were easy since they were $1$ more than a power of $2$. For $7$, I found a construction that broke it up into $4$ and $3$, and kind of used the fact that $3$ was $1$ less than a power of $2$, but after some effort I realized that this could be adapted to the general case above.

The problem rephrases as: what is the least $m$ such that, with the operation of adding in linear combinations of the form $\frac{ca+(m-c)b}{m}$, we can reach $\frac{z_1+\dots+z_n}{n}$ starting with $z_1,\dots,z_n$? (to rigorously see why this is true, set the $n$ points to linearly dependent irrational numbers on the $x-$ axis). The answer is $\text{rad}(2n) | m$. Necessity: we clearly must have $p | m$ for each $p | n$ or the denominators of our expressions in the $z_i$ will never be multiples of $p$. If $n$ is odd and only linear combinations for odd $m$ are allowed, any reachable expression will have exactly $1$ odd coefficient, but we need all $n$ to be odd. Sufficiency: It suffices to construct prime $n$, as if $p | n$ and $n$ is composite we can break into $\frac{n}{p}$ groups of $p$, average each group, and continue inductively. $n=2$ is obvious, so it remains to construct for odd primes $n$. Let $n = \sum 2^{a_i}$ for $a_1 < \cdots < a_k$. Break the $z_i$ into $k$ averages such that $w_i$ is the average of $2^{a\_i}$ of the $z_i$ for each $1\le i\le k$. Now simply take $$\frac{2^{a_k}}{n}\left(\sum_{i=1}^{k-1} \frac{1}{2^{a_k-a_i}}w_i + \left(1-\sum_{i=1}^{k-1} \frac{1}{2^{a_k-a_i}}\right)w_k\right) + \left(1-\frac{2^{a_k}}{n}\right)w_k$$ where the first expression used in the weighted average can be obtained by repeatedly taking midpoints.

We claim Carl can achieve his goal iff $\operatorname{rad}(2n) \mid m$. Note that (by taking a rationally independent subset of ${\mathbb R}^2$) we are allowed to replace ${\mathbb R}^2$ by an arbitrary vector space $V$. Necessity. First take $V = {\mathbb Q}$, and from the starting points $(0, 0, \ldots, 0, 1)$ we require $\operatorname{rad}(n) \mid m$ to construct the point $\tfrac1n$ (for example, by analyzing $\nu_p(x)$ of a constructed point $x$ for $p \mid n$). Now we claim $2 \mid m$ is also necessary. Take $V = {\mathbb Q}^n$ and points \[ \mathcal X = \{ (1, 0, 0, \ldots, 0), \quad (0, 1, 0, \ldots, 0), \quad \ldots \quad (0, 0, 0, \ldots, 1)\}. \]Now it is easy to show (e.g.\ by induction) that if we take any constructed point $\mathbf x = (x_1, x_2, \ldots, x_n)$, then \[ \nu_2(\mathbf x) \coloneqq \bigl(\nu_2(x_1), \nu_2(x_2), \ldots, \nu_2(x_n)\bigr) \in \mathcal X. \]We are supposed to end with $\nu_2(\mathbf x) = (1, 1, \ldots, 1)$, which is impossible. $\square$ Construction. It suffices to show a construction for $n = p$ and $m = 2p$ for any odd prime $p$, since for $n = ab$ we can find centroids of groups of $a$ points and then find the centroid of those $b$ centroids. Furthermore, it suffices to show a construction of the centroid of the $p$ basis vectors $e_1, \ldots, e_p$ of ${\mathbb Q}^p$. Take $k = \lceil \log_2 p \rceil$; the goal is to construct $2^k$ points which have a centroid of $\tfrac1p (e_1 + e_2 + \cdots + e_p)$. This is equivalent to finding a set of $2^k$ $p$-tuples each having a coordinate sum of $p$ and at least $p-2$ zeros. For example, with $p = 5$ and $k = 3$ we can take \begin{align*} &\langle \mathbf{\color{blue}5}, 0, 0, 0, 0 \rangle \\ + &\langle \mathbf{\color{blue}3}, \mathbf{\color{blue}2}, 0, 0, 0 \rangle \\ + &\langle 0, \mathbf{\color{blue}5}, 0, 0, 0 \rangle \\ + &\langle 0, \mathbf{\color{blue}1}, \mathbf{\color{blue}4}, 0, 0 \rangle \\ + &\langle 0, 0, \mathbf{\color{blue}4}, \mathbf{\color{blue}1}, 0 \rangle \\ + &\langle 0, 0, 0, \mathbf{\color{blue}5}, 0 \rangle \\ + &\langle 0, 0, 0, \mathbf{\color{blue}2}, \mathbf{\color{blue}3} \rangle \\ + &\langle 0, 0, 0, 0, \mathbf{\color{blue}5} \rangle \end{align*}In general we can do this for any $p < 2^k$ by a simple greedy algorithm. Then divide each vector by $p$, and notice that each of those points is constructible as a weighted average of two of the $e_j$. Then, by repeatedly taking midpoints we can find the centroid of these $2^k$ points, which by construction is the desired centroid. $\square$

I think my idea is a little simpler then the rest however I cannot explain too well so my solution is actually longer than everyone else's. The answer is when $m$ is divisible by all prime factors of $n$ and $2.$ View the problem in terms of complex, each vertice is $x_1, x_2, \dots, x_n.$ Every time we use the device we end up with some fraction of the form $$\frac{\sum a_ix_i}{m^k},$$where $\sum a=m^k.$ For this to be the centroid we need every $a_i$ to be equal. Therefore $m$ must have every prime factor of $n.$ Now we show that $m$ is even. Consider the last use of the device when $m$ is odd. Note that at least one $a$ would be even, contradiction. Now we show that this is sufficient. First, list out all the primes. For each of these primes note that we can find the centroid of a polygon with that number of vertices. To do this just calculate the midpoints of edges that do not share vertices, with one vertice being left out. Then we have a new polygon with $\frac{p-1}{2}$ sides derived from the midopints and one vertice. If $\frac{p-1}{2}$ is a power of $2,$ then we can continue the previous process on this polygon until we get the centroid, and then we can just use the $p$ in the device to get centroid of the whole $p$ sided figure. If not, continue the process on the $\frac{p-1}{2}$ gon until it reaches some polygon with a power of $2$ edges. Therefore we can just choose some prime $a$ from the list, and then color every $a$ vertices on the $n$ gon some color, find the centroid of all polygons where the vertices are the same color. Now we continue this on the new $\frac{n}{a}$ gon until we run out of primes, where we have the centroid of the $n$ gon$.\blacksquare$

$ $