Given the set $S_n = \{0, 1 \dots n-1\}$. Prove that you can get every subset of $S_n$ starting from $S_n$ and using only two given operations.

Question

So it's given this set. $$S_n = \{0, 1 \dots n-1 \}$$ We have two operations $Add : P(2^{S_n}) \rightarrow P(2^{S_n})$ and $RemoveZero: P(2^{S_n}) \rightarrow P(2^{S_n})$: $$Add(\{x_1 \dots x_k\}) = \{ x_1 + 1 \mod n , \space \space x_2 +1 \mod n, \space \space \space \dots \space \space x_k+1 \mod n\}$$ $$RemoveZero(S) = S \setminus{\{0\}}$$

I need to show that it's possible to get every subset of $S_n$ starting from $S_n$ and using only there two operations.

I was trying to show it by induction. It's easy to see that $(Add\circ RemoveZero )^k(S_n))$ gives an set with n-k elements. So I can get a set of every size. But I can't continue. Any tips?

Answer 1

Let $S_n$ be as given and let $S$ be a subset of $S_n$.

We will show that the following algorithm gives us $S$.

for $i$ going from $n-1$ to $0$
$\\\\\ \ \ \ \text{Add}(S_n)$
$\\\\\ \ \ \ \text{if }i\not\in (S)\ \text{RemoveZero}(S_n)$

We go through the loop $n$ times. If an element $k$ doesn't get removed then its final value is $k+n\ \text{mod}\ n=k$ because we add $1$ to every element before evaluating whether or not to remove the zero.

Answer 2

Imagine you are sitting at a circular table with $n$ place settings, each of which has a cupcake (numbered $0$ to $n-1$). You can perform one of these two actions as many times as you like:

• Eat the cupcake in front of you.

• Rotate the table one spot clockwise.

Do you see how, for any subset $S$ of cupcakes, it is possible to eat all of the cupcakes outside of $S$ and none of the cupcakes in $S$, using those operations alone? And can you see how this is the same as the problem you asked?

---