Let \(n\ge3\) be a fixed integer, and let \(\alpha\) be a fixed positive real number. There are \(n\) numbers written around a circle such that there is exactly one \(1\) and the rest are \(0\)'s. An operation consists of picking a number \(a\) in the circle, subtracting some positive real \(x\le a\) from it, and adding \(\alpha x\) to each of its neighbors. Find all pairs \((n,\alpha)\) such that all the numbers in the circle can be made equal after a finite number of operations. Proposed by Anthony Wang
Problem
Source: ELMO Shortlist 2023 C8
Tags: Elmo, combinatorics
29.06.2023 20:49
Let the numbers be $a_1$, $a_2$, $\ldots$, $a_n$. Let $\omega$ be an $n$th root of unity other than $1$. Then, $\sum_{i=1}^na_i\omega^i$ is invariant if $\omega+\omega^{-1}=\alpha^{-1}$, or $\alpha=\frac1{2\cos\frac{2\pi k}n}$ for some integer $k$. If $k\neq0$, then the sum is zero when all $a_i$ are equal, so the numbers cannot be made equal. Now, suppose $\alpha\neq\frac1{2\cos\frac{2\pi k}n}$ for all nonmultiples $k$ of $n$. First, ignore the $x\leq a$ restriction. We will first show there exists $x_1$, $x_2$, $\ldots$, $x_n$ such that all $n$ numbers of the form $a_i+\alpha x_{i-1}-x_i+\alpha x_{i+1}$ are equal. When $\alpha=\frac12$, if $y_i=\frac12(x_{i-1}-x_i)$ then the condition is equivalent to $a_i+y_i-y_{i+1}$ being constant and $\sum_{i=1}^ny_i=0$. However, the second condition can be ignored by shifting $y_i$, and if $z_i=y_i-y_{i+1}$, then $a_i+z_i$ is constant and $\sum_{i=1}^nz_i=0$, which is obviously possible. When $\alpha\neq\frac1{2\cos\frac{2\pi k}n}$, then we have $$\begin{vmatrix} -1&\alpha&0&\ldots&0&\alpha\\ \alpha&-1&\alpha&\ldots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ \alpha&0&0&\ldots&\alpha&-1\\ \end{vmatrix}=\prod_{i=1}^n(-\omega^i+\alpha(\omega^{i-1}+\omega^{i+1}))\neq0.$$ Therefore, there exists $x_i$ such that $a_i+\alpha x_{i-1}-x_i+\alpha x_{i+1}$ is constant. Adding a constant to all of the $x_i$ makes them all nonnegative and $\min x_i=0$. Now, we will show that it is possible to pick the number $a_i$ and subtract exactly $x_i$ from it to make all of the numbers equal. If $\alpha>\frac12$, apply the operation to each number a large number of times to increase all of the $a_i$, then apply the operation to number $i$ and subtract $x_i$ from it, which is possible whenever the $a_i$ are large enough. If $\alpha\leq\frac12$, let $C=a_i+\alpha x_{i-1}-x_i+\alpha x_{i+1}>0$. Define $b_i$ to be the current value of the $i$th number, and let $c_i$ be the total amount subtracted from $b_i$ when the $i$th number was picked. Since the sum of all of the numbers is $\sum_{i=1}^na_i+(2\alpha-1)\sum_{i=1}^nc_i$ and $\sum_{i=1}^nc_i\leq\sum_{i=1}^nx_i$, we get that the sum of all numbers is at least $Cn$, so there always exists a number that is at least $C$. If they are not all equal, then suppose $b_i>C$. We have $C=b_i+\alpha(x_{i-1}-c_{i-1})-(x_i-c_i)+\alpha(x_{i+1}-c_{i+1})$. Then, we must have $x_i-c_i>0$, so we can apply the operation to $b_i$ and subtract $\min(x_i-c_i,b_i)\geq\min(x_i-c_i,C)$ from it. After each operation, either $x_i=c_i$ for some $i$ or $\sum_{i=1}^nc_i$ increases by at least $C$, so this process must end. When this process ends, we must have $x_i=c_i$ for all $i$, so all of the numbers are equal to $C$. Therefore, it is possible to make all of the numbers equal if and only if $\alpha\neq\frac1{2\cos\frac{2\pi k}n}$ for all integers $k$ satisfying $n\nmid k$.
30.06.2023 14:30
Here is a much bashier solution. The answer is all $(n, \alpha)$ such that $\alpha \ne \frac{1}{2\cos(2\pi k/n)}$ for some $k$ that is not a multiple of $n$. Let $P(x) = x^n-1$ and $Q(x) = \alpha - x + \alpha x^2$. Let $a_0, \cdots, a_{n-1}$ be the reals on the circle. Consider $A(x) = \sum_{j=0}^{n-1} a_jx^j \in \mathbb{R}[x] / P(x)$. Initially, $A(x) = 1$. In the end, $A(x) = c(1+\cdots+x^{n-1})$. Let $\omega$ be a root of $1+\cdots+x^{n-1} = \frac{x^n-1}{x-1}$, so it makes sense to evaluate $A(\omega)$ (recall $A \in \mathbb{R}[x]/P(x)$). Then initially $A(\omega)=1$ and in the end $A(\omega) = 0$. If $Q(\omega)=0$, this is absurd. When $Q(\omega) = 0$ we can see that $\alpha = \frac{\omega}{1+\omega^2} = \frac{1}{\omega+\omega^{-1}} = \frac{1}{2\cos(\frac{2\pi k}{n})}$ for some $k$ that is not a multiple of $n$. We now show that all other $\alpha$ work. Let $F(x)$ be a polynomial of degree at most $n-1$ such that $1+Q(x)F(x) = (1+\cdots+x^{n-1}) G(x)$. Since $Q(x), 1+\cdots+x^{n-1}$ are coprime, it follows that $F(x) = F_0(x) + c(1+\cdots+x^{n-1})$ where $1+Q(x)F_0(x)$ is divisible by $1+\cdots+x^{n-1}$. We can for example, set LHS to be divisible by $x^n-1$, then by Lagrange Interpolation / Inverse of Discrete Fourier Transform to obtain that having $$t_{k+1} = [x^k] F_0(x) = \frac 1n \sum_{j=0}^{n-1} \frac{1}{1-\alpha(\omega^j + \omega^{-j})} \omega^{-jk}$$Of course, $\sum t_k = F_0(1)$ and $1+Q(1)F_0(1) = 0$, so $F_0(1) = \frac{-1}{Q(1)} = \frac{1}{1-2\alpha}$ Notice that $F(x) = f_0 + f_1x+ \cdots + f_{n-1}x^{n-1}$ corresponds to $a_j$ removing a total of $f_{j+1}$ and $a_{j-1}, a_{j+1}$ each gaining a total of $\alpha f_{j+1}$ as a result (note that $a_j$ don’t need to give out $f_{j+1}$ immediately; it can lose $f_{j+1}$ over several steps to ensure that all $a_j$ are nonnegative during our entire process). When $a_j$ gives out $f_j$, the polynomial changes by $Q(x) x^{j-1}$. This way, all numbers on the circle ends up being the same. We will first construct $c$ such that all $t_j+c$ are positive and $-1\le (2\alpha-1)(\sum\limits_{j=0}^{n-1} (t_j+c))$. (the second condition implies that the sum of $a_j$ are nonnegative after operations). When $2\alpha - 1 \ge 0$ this is clear by taking $c\to \infty$, so we focus on the case where $2\alpha - 1 < 0$ We know that $$\frac{1}{1-2\alpha} \ge \sum_{j=0}^{n-1} (t_j+c) = nc+\frac{1}{1-2\alpha}$$, so this is equivalent to $2\ge (2\alpha-1) nc$. If $\alpha \le \frac 12$ we have completed this step. Otherwise, $2\alpha-1 \ge 0$, so $c\le \frac{2}{(2\alpha-1)n}$ So this is equivalent to $c\le 0$. It suffices to show that each $t_j$ is positive, and then we can use DottedCalculator's finish. WTS: $$\sum_{j=0}^{n-1} \frac{\omega^{jk} + \omega^{-jk}}{1-\alpha (\omega^j + \omega^{-j})} \ge 0$$ We can rewrite this as $$\sum_{j=0}^{n-1} (\omega^{jk} + \omega^{-jk}) \sum_{l\ge 0} (\alpha^l (\omega^j + \omega^{-j})^l$$ $$ = \sum_{l\ge 0} \alpha^l \sum_{j=0}^{n-1} (\omega^{jk}+\omega^{-jk})(\omega^j+\omega^{-j})^l$$ Let $f_l(x) = (x^k+x^{-k})(x+x^{-1})^l$. By roots of unity filter, $$\sum_{j=0}^{n-1} (\omega^{jk}+\omega^{-jk})(\omega^j+\omega^{-j})^l = \sum_{j=0}^{n-1} f(\omega^j) = n \sum_{d\mid k, k\in \mathbb{Z}} [x^d]f(\omega^j) > 0$$ The conclusion follows.
11.08.2023 07:05
I guess I should give some sort of Proposer's Remarks for this problem, so let me tell some sort of a story: In 2020, while jj_ca888 and I were working on SMC (:sob:), I wrote down this problem, inspired by a USACO (?) problem dealing with adding vectors in $\mathbb F^n$ phrased as using a big fork to toggle lamps or something: Fork Problem Alpha wrote: Let $n$ be a positive integer. Andrew has two lists $A = (a_1, a_2, \dots, a_n)$ and $B=(b_1, b_2, \dots, b_n)$ in $\mathbb F _2^n$. In each move, Andrew picks some positive integer $1 \leq \ell \leq n$ and adds $b_i$ to $a_{\ell + i}$ where $i$ ranges from $1$ to $n$ and the indices for $a$ are taken modulo $n$. Show that Andrew can reduce $A$ to all zeroes iff he can do the same when $B$ is reversed. But I quickly realized that this is just wrong (I think there is a counterexample for $n \approx 7$, although don't quote me on that). As an algebraic combinatorialist (really don't quote me on that), I wanted some nice algebraic structure, so I decided, ok what if we correspond $\mathbb F_2^n$ with $\mathbb Z/(2^n - 1)\mathbb Z$ (non injectively but that's ok) by using bits, so that shifting $B$ corresponds to just multiplying by $2$. The additive structure is all broken, but that's okay. So we have a new problem: Fork Problem Beta wrote: Let $n$ be a positive integer. Andrew plays a game with $n$ baskets arranged around a circle, each containing some number of rocks. He also has a list $a_1, a_2, \dots , a_n$ of nonnegative integers. On each move, Andrew chooses a basket to start at and moves one time clockwise around the circle, placing $a_i$ rocks into the $i$th basket he encounters. removes two rocks from a basket and adds one to the basket directly clockwise. Show that no matter the starting conditions, Andrew can make every basket contain exactly one rock if and only if he can do so when he moves counterclockwise instead. (Oh, I should mention, I intended the conclusion as just some sort of answer extraction that I put $\varepsilon$ thought into. The real work is uncovering the algebraic structure). For this problem, the map $\mathbb F_2^n \to \mathbb Z/(2^n - 1)\mathbb Z$ is now the map $\mathbb N_0^n \to \mathbb Z/(2^n - 1)\mathbb Z$. Unfortunately the conclusion was still so arbitrary that this problem was either still wrong (with a similarly sized counterexample), or I just did not feel like solving it. To try to fix this, I tried to force $B$ to be a palindrome and ask for an answer instead: (this is 2021, now) Fork Problem Gamma wrote: Let $n, k$ be positive integers where $k \le n$. Andrew has $n$ empty baskets in a circle. In each move, either he places $1$ rock in $k$ consecutive baskets, or he picks a basket with at least $2$ rocks, removes one of those rocks, and moves the other rock clockwise. Find the minimum number of moves of type $1$ needed for Andrew to make each basket have exactly $1$ rock. In other words, $B=2^k-1$ and $A=2^n-1$. It works out nicely that since the "binary carry" operations (type $2$ moves) can never remove all rocks, i.e. make the $\mathbb N_0^n$ "vector" identically zero, the kernel of the $\mathbb N_0^n \to \mathbb Z/(2^n - 1)\mathbb Z$ map perfectly detects when it is possible to use only such operations to make every basket have exactly $1$ rock, i.e. the conclusion for this problem, so this is an actually true problem now! Unfortunately, the finish requires essentially APMO 2016/2, which is a bit undesirable. The remainder of this story occurs $\approx 3$ days before the ELMO 2023 submission deadline. To get rid of "number theoretic" effects, the idea was to replace $\mathbb N$ with $\mathbb R_{\ge 0}$ and $2$ with some real constant $a$, and ask for when it is possible to get everything equal from some arbitrary starting configuration. Unfortunately, this is too strong for obvious reasons (if you can remove $x$ in one and put $a x$ in another, then you can make anything up to scaling with just this; maybe this is interesting, but I don't know how to deal with positivity here). But if $a$ is instead replaced with an indeterminant $X$, then we get some nice ring-theoretic interpretations. In particular, looking at the canonical map $\mathbb R[X] \to \mathbb R[X] / (X^n - 1)$, we ask for when there exists a nontrivial multiple of $X^{k - 1} + \dots + X + 1$ mapping to something of the form $c(X^{n - 1} + \dots + X + 1) - Q(X)$, where $c$ is some real and $Q(X)$ represents the starting configuration. In other words, we ask for when some $c(X^{n - 1} + \dots + X + 1) - Q(X)$ lies in the ideal generated by $X^{k - 1} + \dots + X + 1$ and $X^n - 1$ in $\mathbb R[X]$. But we can replace $X^{k - 1} + \dots + X + 1$ with an arbitrary polynomial $P(X)$; I picked $X^2 - \beta X + 1$ (which eventually got inverted with $\alpha = \beta^{-1}$), which has the following nice properties: If $\beta = 2 \cos \left(\tfrac {k\tau}{n}\right)$ for $n \nmid k$, then $\gcd(X^2 - \beta X + 1, X^n - 1) = X^2 - \beta X + 1 \mid X^{n - 1} + \dots + X + 1$, so for almost all $Q(X)$. we cannot do it (which can also be phrased as an invariant), If $\beta \ne 2 \cos \left(\tfrac {k\tau}{n}\right)$ for any $k$, then $\gcd(X^2 - \beta X + 1, X^n - 1) = 1$ (because they share no roots), so the ideal $(X^2 - \beta X + 1, X^n - 1)$ is all of $\mathbb R[X]$ so everything is reachable (ignoring positivity), if $\beta = 2$, then $\gcd(X^2 - \beta X + 1, X^n - 1) = X - 1$, which does not divide $X^{n - 1} + \dots + X + 1$, so we can just pick the appropriate $c$ to get it to work (ignoring positivity). Finally, we can remove positivity as follows: spam the operation on every single number in the circle, by the Fundamental Limit Theorem for Markov Chains, if $n$ is odd, the numbers approach a uniform distribution, and if $n$ is even (it is periodic), the numbers approach an "oscillating" distribution with period $2$ where every other number approaches the same value. The latter case can be dealt with to make everything almost uniform, so then positivity no longer matters. Thus, everything falls into place, and we have the problem written in #1 (where I have chosen $Q(X) = 1$). As a final remark, although I wasn't at MOP this year, it's amazing (or rather sad) that this problem appeared cotemporally as ISL 2022/C4.