Problem 3. Let $n$ be a positive integer. Let $B_{n}$ be the set of all binary strings of length $n$. For a binary string $s_{1} s_{2} \ldots s_{n}$, we define its twist in the following way. First, we count how many blocks of consecutive digits it has. Denote this number by $b$. Then, we replace $s_{b}$ with $1-s_{b}$. A string $a$ is said to be a descendant of $b$ if $a$ can be obtained from $b$ through a finite number of twists. A subset of $B_{n}$ is called divided if no two of its members have a common descendant. Find the largest possible cardinality of a divided subset of $B_{n}$.

(Viktor Simjanoski)
Solution. For a string $s$, denote its twist by $f(s)$, and the number of blocks of consecutive digits it has by $b(s)$. Construct an undirected graph $G$ on $B_{n}$ with edges $(s, f(s))$ for all $s \in B_{n}$, and note that the largest possible cardinality of a divided subset of $B_{n}$ is the number of connected components of the graph.

Each connected component of $G$ contains exactly one cycle, and we aim to show that each cycle in the graph has a length of exactly 2 .

1 point.

Assume that there exists a cycle $A \subseteq B_{n}$ which is not of length 2. First, fix some $s \in A$.

We wish to show that $10$ such that $b\left(f^{t}(s)\right)=b(s)$. By minimality of $t$, it follows that $f^{t}(s)_{b(s)}=1-s_{b(s)}$ but as we have $s_{b(s)+1}=1-s_{b(s)}=s_{b(s)-1}$ we obtain that $b\left(f\left(f^{t}(s)\right)\right)=b(s)+2$ which contradicts the maximality of $b(s)$ in $A$, so no such component $A$ can exist.

4 points.

Now, let us count the possible cycles of length 2. Each cycle of length 2 occurs when we have $f(f(s))=s$ and $b(s)=$ $b(f(s))$, which gives $2 \leqslant b(s) \leqslant n-1$.

We count by fixing either the left or right of the position $b(s)=k$ in a string $s$ as one of $k-1$ "break" points between $0 / 1$ blocks in the string $s$ and then counting that the other $k-2$ block "breakpoints" can be assigned in $\binom{n-3}{k-2}$ ways to the remaining $n-3$ spots between two symbols of $s$, with each assignment of blocks giving two distinct outcomes due to the choice of $0 / 1$ in the starting block. This gives a total of

$$
\sum_{k=2}^{n-1} 2\binom{n-3}{k-2}=2^{n-2}
$$

different cycles of length 2 and we are done.