Click to reveal hidden text

I was confused with the example… fixed now

Bump bump

Since a full solution hasn't been posted, here is mine from the contest: Consider the directed graph with nodes the binary strings of length $n$ and directed edges from each node to its twist. We get a directed graph, where there is exactly one edge going out of every node. Consider the connected components in this graph. It is well-known in every such connected component there can be exactly one simple cycle (because from every node there is exactly one edge going out). This means that in a divided subset there can be at most one node from every connected component. We would like to now count the number of connected components. Crucial claim: This cycle is of length 2 in every connected component. Proof: Consider first how the number of blocks changes as a twist is performed. It is easy to see that if the binary string on which it is performed has more than 1 but less than $n$ connected components, the number of blocks may change by $\pm2$ or remain the same after a twist. Now we first prove the claim for the connected components containing one of the nodes $00\dots 0$, $11\dots1$, $1010\dots$, $0101\dots$. The first two cases are symmetric and we have $00\dots0\rightarrow10\dots0\rightarrow110\dots0\rightarrow10\dots0$, hence a cycle of length 2 is formed. The second 2 cases are also symmetric and we have $\dots101\rightarrow\dots100\rightarrow\dots110\rightarrow\dots100$ and again a cycle of length 2 is formed. Now we consider all other connected components. Assume one of them has a simple cycle of length more than 2. If there are two adjacent nodes which have the same number of blocks, this would be a cycle of length 2 - contradiction. So now every two adjacent nodes have a different number of blocks and each time this number is $\pm2$ the previous one. From this it easily follows that the number of nodes in every such cycle is an even number. Now assume $t$ is the largest number of blocks of a string in the considered cycle. Since at the end the string is the same as in the beginning, each element of the string should have been changes an even number of times. This means that the element at position $t$ has been changed an even number of times too. Consider the "first" time it was changed (or really an arbitrary operation at which it was changed). Then just before it was a string with $t-2$ blocks and just after it is, again, a string with $t-2$ blocks. For this to happen, before the altering we have $s_{t-1} \neq s_t \neq s_{t+1}$ (and $t$ blocks) and after that we have $s_{t-1} = s_t = s_{t+1}$ (and $t-2$ blocks). Then the next time the element on position $t$ is changed, we would go from $s_{t-1} = s_t = s_{t+1}$ to $s_{t-1} \neq s_t \neq s_{t+1}$, hence the number of blocks would increase from $t$ to $t+2$ - contradiction with the maximality of $t$. Hence in every connected component the length of the cycle is 2. Now there is a bijection between the connected components and the cycles of length 2, so we will count them. To do that, we count the number of strings of length $n$ with $i$ blocks, which have a twist with exactly $i$ blocks again. This means that either $s_{i-1}=s_i\neq s_{i+1}$ or $s_{i-1}\neq s_i = s_{i+1}$. Counting this gives us a total of $2^{n-2}$ connected components. Hence, this is the answer. $\square$

Maths_Girl wrote: Now there is a bijection between the connected components and the cycles of length 2, so we will count them. To do that, we count the number of strings of length $n$ with $i$ blocks, which have a twist with exactly $i$ blocks again. This means that either $s_{i-1}=s_i\neq s_{i+1}$ or $s_{i-1}\neq s_i = s_{i+1}$. Counting this gives us a total of $2^{n-2}$ connected components. Hence, this is the answer. $\square$ I think, it's not so trivial to count the strings that produce a cycle of length 2, call them good strings. Their number should be $2^{n-1}$. This is the more difficult part of the problem. Maybe there is a more straightforward approach, but here is what I would propose. . Let $N(n,k), k\ge 1$ denotes the good strings of length $n$ with exactly $k$ equal first bits. Clearly $$N(n)= \sum_{k=1}^m N(n,k).$$where $m:=\lceil n/2\rceil$ and $N(n)$ denotes the number of good strings. So, $N(n,k)=0$ for $k>m$. Further, it can be checked that for $2\le k\le m$ it holds $N(n,k)=N(n-1,k)+N(n-2,k-1)$ and $N(n,1)=N(n-1,1)+ N(n-2)+2$ (if I'm not mistaken for the latter one). So, some calculation can do the job. Another approach is some bijection between the good strings and the bad strings, though I couldn't see how.

So, lets finish the problem. It boils down to count the strings that produce cycles, call them good strings, and denote their number by $N(n)$. Consider a similar operation, but after counting the contiguous blocks we increase this number by $1$ and change the bit of that position. By $N_{+1}(n)$ we denote the number of good strings under the just defined operation. If the number of of blocks is $n$ (all bits alternate) and so, $n+1$ is a position outside the string, we assume it's not a good string. We prove by induction simultaneously that $N(n)=2^{n-1}$ and $N_{+1}(n)=2^{n-1}-2$ for $n\ge 3$. The base of induction is trivial, so lets see how to make the step. Fix some $n\ge 5$ and let the hypothesis is proven for the numbers less than $n$. There are two possible cases for the last two bits. Either they are equal or they differ. Let us consider these cases separately. 1) The last two bits are equal. Then if we delete the last bit the number of blocks wouldn't change. So, it is as if we deal with a string with size $n-1$, except when the number of blocks is $n-1$ and we should change the second to last bit. In this situation with deleted last bit it will be a bad string but if it's not deleted it will be a good string. Hence, we obtain that the number of good strings with last two bits equal is $N(n-1)+2=2^{n-2}+2$. 2) Suppose the last two bits differ. If the first two bits are equal, we delete the first bit and the last bit of the string and in this case we get $N(n-2)=2^{n-3}$ good strings. If the first two bits also differ, we again delete the first and the last bits and obtain $N_{+1}(n-2)=2^{n-3}-2$ good strings like that. Putting these two cases together, we get $N(n)=2^{n-2}+2 + 2^{n-3}+2^{n-3}-2=2^{n-1}$. It remains to calculate $N_{+1}(n)$. Consider the first two bits of a good string under the modified operation. If they are equal we can delete the first bit and similarly as above we get $N(n-1)$ "good +1" strings like that. If the first two bits differ, we again delete the first bit and get $N_{+1}(n-1)$ "good +1" strings like that. Therefore all "good +1" strings are $N(n-1)+N_{+1}(n-1)=2^{n-2}+2^{n-2}-2=2^{n-1}-2$ and the inductive step is complete.

dgrozev wrote: I think, it's not so trivial to count the strings that produce a cycle of length 2, call them good strings. Their number should be $2^{n-1}$. This is the more difficult part of the problem. Maybe there is a more straightforward approach, but here is what I would propose. Indeed, I should have written this in more detail, but I actually believe this to be the easier part of the problem, here is how I finished it: We will count the number of cycles with length 2 that have exactly $i$ blocks for $1\leq i\leq n$. If this is $f(i)$ then the number of connected components would be $\sum_{i=1}^{n}f(i)$. Firstly, $f(1)=0$ and $f(n)=0$. Now let $2\leq i\leq n-1$. Now if we have a string of $i$ blocks and we want its twist to have exactly $i$ blocks too, then $s_{i-1}\neq s_{i+1}$. WLOG let $s_i=0$ (in the second element of the cycle it would be $s_i=1$) and let $s_{i-1}=0, s_{i+1}=1$ (and remember to multiply the answer by 2 at the end). Now consider where the "division lines" between the blocks are, i.e. if we draw a line between two consecutive elements of the string which are different, since we have exactly $i$ blocks, we must have $i-1$ division lines. We know there is one between elements $s_{i}$ and $s_{i+1}$ and there is no division line between $s_{i-1}$ and $s_i$. Note that because the value of $s_i$ is fixed, the placement of the division lines uniquely determines the rest of the string. Hence we are left with $n-3$ places to put $i-2$ division lines. This can be done in $\sum_{i=2}^{n-1}\binom{n-3}{i-2} = \sum_{i=0}^{n-3}\binom{n-3}{i} = 2^{n-3}$. Now remember to multiply by 2 from before and we have $2^{n-2}$ cycles of length 2.