Robot "Mag-o-matic" manipulates $101$ glasses, displaced in a row whose positions are numbered from $1$ to $101$. In each glass you can find a ball or not. Mag-o-matic only accepts elementary instructions of the form $(a;b,c)$, which it interprets as "consider the glass in position $a$: if it contains a ball, then switch the glasses in positions $b$ and $c$ (together with their own content), otherwise move on to the following instruction" (it means that $a,\,b,\,c$ are integers between $1$ and $101$, with $b$ and $c$ different from each other but not necessarily different from $a$). A $\emph{programme}$ is a finite sequence of elementary instructions, assigned at the beginning, that Mag-o-matic does one by one. A subset $S\subseteq \{0,\,1,\,2,\dots,\,101\}$ is said to be $\emph{identifiable}$ if there exists a programme which, starting from any initial configuration, produces a final configuration in which the glass in position $1$ contains a ball if and only if the number of glasses containing a ball is an element of $S$. (a) Prove that the subset $S$ of the odd numbers is identifiable. (b) Determine all subsets $S$ that are identifiable.
Problem
Source:
Tags: combinatorics, Italy
08.05.2022 17:33
(b) Suppose $S$ is identifiable set. Then 1. $101\in S$ 2. $0\notin S$ We prove that any set satisfying these two conditions is identifiable. Suppose there are some balls (not zero) in the glasses. We'll show a sequence of instructions that orders all the balls in a contiguous sequence right to left, that is, at the positions $101,100,\dots.$ To be sure that there is a ball in the $101$th place we use the instructions: $(1;1,n),(2;2,n),\dots,(100;100,n)$, where $n=101$. After that, we put the same block of instructions for $n=100$ and so on, and finally, for $n=2$. At this moment, we are sure the balls are in contiguous sequence, right to left. Let us show that there exists a programme chunk that identifies $S:=\{n\}$ where $1\le n<101$. As shown, we arrange the balls right to left. To ascertain there are exactly $n$ balls we should check that there is a ball at the $m:=(101-n+1)$th position and there isn't at the $m-1=(101-n)$th one. The block of instruction that does it is: $(m;m,1),(m-1;m,1)$. Before these two instructions, there is no ball at the 1st position. After the execution, there is a ball at the 1st position if and only if there were exactly $n$ initial balls. We refer to this programme code as a code identifying $n$. Now, let $S$ consists of the elements $1\le n_0<n_1<\dots<n_{k}=101$. First, we put a chunk of code that identifies $n_0$. After that, we work only on the positions $2,3,\dots,101$ and put a chunk of code that identifies $n_1$ on those positions. Next, we put the instruction $(2;2,1)$. So, what have we done till now? We have a ball at the first position if and only if $(n_0\in S)\, \mathrm{or}\, (n_1\in S)$. Then we repeat this action for $n_2,\dots,n_{k-1}$. As a result, the obtained program identifies $S$. Indeed, take $n\in S, n\neq 101$, put $n$ balls somehow in the glasses, and execute the programme. We obtain a configuration with a ball in the first glass if and only if $n\in S$. If we put $101$ balls in the glasses, then we will again have a ball in the 1st place.