Question 41
The robot "Mag-o-matic" handles 101 glasses, arranged in a row whose positions are numbered from 1 to 101. Each glass may or may not contain a ball. The robot Mag-o-matic only accepts elementary instructions of the form $(a ; b, c)$, which it interprets as
"look at the glass in position $a$: if it contains a ball, then swap the glasses in positions $b$ and $c$ (together with their possible contents), otherwise go on to the next instruction"
(it is understood 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 program is a finite sequence of elementary instructions, fixed in advance, which Mag-o-matic executes one after the other.
A subset $S \subseteq\{0,1,2, \ldots, 101\}$ is called identifiable if there exists a program 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 of $\{0,1, \ldots, 101\}$ consisting of the odd numbers is identifiable.
b. Determine all identifiable subsets of $\{0,1, \ldots, 101\}$.
"look at the glass in position $a$: if it contains a ball, then swap the glasses in positions $b$ and $c$ (together with their possible contents), otherwise go on to the next instruction"
(it is understood 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 program is a finite sequence of elementary instructions, fixed in advance, which Mag-o-matic executes one after the other.
A subset $S \subseteq\{0,1,2, \ldots, 101\}$ is called identifiable if there exists a program 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 of $\{0,1, \ldots, 101\}$ consisting of the odd numbers is identifiable.
b. Determine all identifiable subsets of $\{0,1, \ldots, 101\}$.