Given an endless supply of white, blue and red cubes. In a circle arrange any $N$ of them. The robot, standing in any place of the circle, goes clockwise and, until one cube remains, constantly repeats this operation: destroys the two closest cubes in front of him and puts a new one behind him a cube of the same color if the destroyed ones are the same, and the third color if the destroyed two are different colors. We will call the arrangement of the cubes good if the color of the cube remaining at the very end does not depends on where the robot started. We call $N$ successful if for any choice of $N$ cubes all their arrangements are good. Find all successful $N$. I. Bogdanov
Problem
Source: Tournament of Towns 2020 oral p6 (15 March 2020)
Tags: combinatorics, winning strategy, game strategy, game
Ankoganit
01.06.2020 17:42
We abbreviate the colors as $R, W$ and $B$ in the obvious manner: $W$ for Wine red, $R$ for Royal blue, and $B$ for Bleached white. We claim the answer is all powers of two. First, let us prove other numbers are not successful. Let $A(n)$ and $B(n)$ denote the following configurations: [asy][asy]size(9cm); draw(arc(0,1,45,135)^^arc(2.5,1,45,135),dotted); draw(arc(0,1,135,405)^^arc(2.5,1,135,405)); void box(pair p,string s){ filldraw(shift(p)*scale(0.3)*shift((-.5,-.5))*unitsquare,white); label(s,p);} box(dir(270),"B");box(dir(270)+2.5,"B"); for(int i=0;i<3;++i){ box(dir(225-45*i),"R");box(dir(315+45*i),"R"); box(dir(225-45*i)+2.5,"R");box(dir(315+45*i)+2.5,"R"); } dot(dir(292.5)^^dir(247.5)+2.5); label("$n-1$ R cubes",0); label("$n-1$ R cubes",2.5); label("$A(n)$",1.4*dir(270)); label("$B(n)$",1.4*dir(270)+2.5); [/asy][/asy] The dot indicates where the robot starts. We claim that $A(n)$ ends in $W$ if $n-1$ has an odd number of digits in binary and $B$ otherwise; and $B(n)$ ends in $B$ if $n$ has an odd number of digits in binary, and $W$ otherwise. The small cases can be verified manually. For the induction step, note that one step in the $A(n)$ configuration results in a $B(n-1)$ configuration with $B$ and $W$ switched. This means this ends with the opposite colour of $B(n-1)$ ($B$ and $W$ being opposites), which checks out the induction step. For $B(n)$, note that if $n=2k+1$, note that once the robot makes one full trip through the $2k$ $R$ cubes, it turns them into $k$ $R$ cubes, reducing it into $A(k+1)$, and the induction step works out again. If $n=2k$, a full circle trip reduces the situation into $B(k)$ with $B$ and $W$ swapped, and again we are good. Now it's immediate that $A(n)$ and $B(n)$ are always different as long as $n$ isn't a power of two, proving these aren't successful. Now to show $2^k$ is always successful. Define the $+$ operator on the symbols $R,W,B$ as $x+y=$the color obtained when $x$ and $y$ are deleted (so $R+R=R,B+W=R$ etc.). This is commutative, but sadly not associative; but something weaker is true: Claim. For any $a,b,c,d\in \{R,W,B\}$, we have $(a+b)+(c+d)=(a+c)+(b+d)$. Proof. Casework. For a sequence $a_1,\cdots, a_n$ with $a_i\in\{R,W,B\}$, we define $f(a_1,\cdots, a_n)$ to be the color at the end if the initial configuration consists of cubes of color $a_1,\cdots, a_n$ clockwise around a circle and the robot starts at right before $a_1$. It's easy to see $$f(a_1,\cdots, a_{2^k})=f(a_1,\cdots,a_{2^{k-1}})+f(a_{2^{k-1}+1},a_{2^k}).$$So for example $f(a_1,\cdots, a_8)$ would be $$((a_1+a_2)+(a_3+a_4))+((a_5+a_6)+(a_7+a_8)).$$ Now we claim something much stronger than needed: for $2^k$ cubes, not only does the initial placement of the robot not matter, the order of the cubes around the circle doesn't either. In other words, for $a_i\in\{R,G,B\}$, we have $$f\left(a_1,\cdots,a_{2^k}\right)=f\left(a_{\sigma(1)},\cdots, a_{\sigma({2^k})}\right)$$for any permutation $\sigma$ on $\{1,\cdots,2^k\}$. The small cases are easy enough, so let's do the induction step. Let $f(a_1,\cdots,a_{2^k})=(\alpha+\beta)+(\gamma+\delta)$, where $\alpha=f(a_1,\cdots, a_{2^{k-2}})$ and so on. Suppose to perform the permutation $\sigma$ on the indices, $x$ indices $> 2^{k-1}$ need to come to left half (become $\le 2^{k-1}$). We can assume $x\le 2^{k-2}$ (if not, $(\alpha+\beta)+(\gamma+\delta)=(\gamma+\delta)+(\alpha+\beta)$, and permute this new expression instead). By induction, the terms within $\alpha+\beta$ and $\gamma+\delta$ can be permuted freely; order them so $\beta$ contains all the $a_i$'s with indices that need to jump from the left half to the right half, and $\gamma$ contains all those that need to jump from right to left half. Now $$(\alpha+\beta)+(\gamma+\delta)=(\alpha+\beta)+(\delta+\gamma)=(\alpha+\delta)+(\beta+\gamma).$$By induction, we can reorder the terms in $(\beta+\gamma)$ to form $(\beta'+\gamma')$ so that the indices that need to be on the right half are all in $\gamma'$ and those to be on the left half are in $\beta'$. Then $$(\alpha+\delta)+(\beta'+\gamma')=(\alpha+\beta')+(\delta+\gamma')$$and thus all the indices are now in the correct half of the expression. Now we can rearrange the individual halves internally to get the correct permutation.
SnowPanda
16.12.2020 21:51
The answer is powers of $2$.
First, note that since $3x \equiv 0 + 1 + 2 \equiv 0 \pmod{3}$, we can let red, white, and blue be $0$, $1$, and $2$ mod $3$. Then the robot takes a sequence $a_1,\, a_2, \, a_3, \, \ldots, \, a_N$, and repeatedly deletes the first two terms $x$ and $y$ and places $-x - y$ at the end. The color remaining at the end is the value of the final expression mod $3$.
If $N = 2^k$, then it's clear (for example, by induction) that the final expression is $$(-1)^k\cdot (a_1 + a_2 + \cdots + a_N),$$which is symmetric in all the $a_i$, so the final value is the same for any permutation of the sequence (we only need it to be true for all cyclic shifts).
Meanwhile, it's clear that in the sequence, there's always exactly one term containing each $a_i$. If $N > 1$ is odd, then we eventually end up with a sequence $$a_N, -a_1 - a_2, -a_3 - a_4, \ldots, -a_{N - 2} - a_{N - 1},$$which results in the term $-a_N + a_1 + a_2$. So then $a_N$ and $a_1$ will end up with different signs in the final expression. This means the sequence $(1, 0, 0, \ldots)$ will have a different final color if the $1$ is $a_1$ as if the $1$ is $a_N$.
Now if $N = 2^k\cdot n$, where $n > 1$ is odd, then the sequence eventually becomes a length $n$ sequence \[(-1)^k\cdot (a_1 + \cdots + a_{2^k}, \, a_{2^k + 1} + \cdots + a_{2\cdot 2^k}, \, \ldots),\]and then the same reasoning as before shows that if we have the sequence $(1, 0, 0, \ldots)$, then the outcomes when the $1$ is in the first block of consecutive $2^k$ and when the $1$ is in the last block are different.
EthanWYX2009
06.07.2024 10:47
The answer is $N=2^k,$ where $k$ is a positive integer. First prove $2^k$ indeed work. My observation is consider the operation in $\mathbb Z_3.$ Call white $0,$ blue $1,$ and red $-1.$ I hope to find something not changing, so turns out that $a,b$ geberates $-(a+b)$ (the sum of these three balls are $0.$) Now As the robot turn exactly $k$ turns (each turn a whole circle), every ball is operated $k$ times, so the final number is always $(-1)^k\sum\text{label}.$ Now we need $2^k<N<2^{k+1}$ doesn't work. A straight idea is to operate $N-2^k$ times first. Since the rest never change by above, we get contradiction. So here consider $\text{0 1 1 1 1}\cdots\text{ 1}\to\text{1 1 1 1}\cdots\text{1 -1}$ and $\text{1 1 1 1}\cdots\text{ 1 0}\to\text{1 1 1 1}\cdots\text{1 -1}.$ (ends with $2^k$ balls). Now by above calculation we know this two are not equal, contradiction.$\Box$