01串的增减操作问题

aimisiyou

对于一个由0、1组成的序列，定义操作：在此序列开头或者结尾或者中间任意位置，填上或删去00,111,0101，问：序列01是否能通过若干次操作变成序列10？
注：中间位置删去后自动合拢

王守恩

如果答案是肯定的，即0和1是可以交换位置的，那么串的次序就无关紧要了，串就等价于集合了。
0，2个2个地删，最后只剩一个或被删光。
1，3个3个地删，配合2个2个地删，可以全部删光。
结果所有的串，要么变成0，要么变成空。这不太可能。

hujunhua

操作都是可逆的，如果串 A 和串 B 可以通过一系列有限的操作相互转化，就记作 A↔B。
显然，A↔B ∧ B↔C → A↔C。
所以“↔”是一个等价关系. 所有的串按此关系被划归于若干个等价类。
让我们先看看各个类的最短代表能有多短，从而计算最多能有多少个等价类。

我们先总结几条操作法则：
法则1：等价片段是可以相互替换的。
法则2：若A+C↔B+C，或者C+A↔C+B，则A↔B。这里“+”表示接龙。

由00↔111↔0101↔空  及法则2立得：11↔010，0↔101
推论：1010↔111↔空，由此推论立得下述法则3

法则3：若A↔B，则 A的逆序↔B的逆序

以下就容易计算其它3位串的缩减结果了：
000↔0，001↔1，010↔11，011↔0010↔10，100↔1，101↔0，110↔01，111↔空
结果3位串都可以缩减为2位串或者0，1，空。
那么3位以上的串就可以逐步缩减到2位串或者0，1，空.
所以初步得出总共至多只有6个等价类，最短代表分别为: 空，0，1，01，10，11

至于其中有没有两个类是等价的，有待于进一步讨论。
显然, 0是不能变成空的，因为任意操作不改变0的数量的奇偶性。所以至少有两个等价类。

假设01↔10，那么
11↔0011↔0101↔空，
1↔1111↔空
那就只有“0”和“空”两个等价类了.

这不太可能。

aimisiyou

0011->0101没看懂？

mathe

看起来6个等价类好像互不等价，不能进一步归并。

aimisiyou

能互转的肯定可以列出转换过程，但不能转换的怎么来证明呢？

mathe

找到解决方案了，序列中的所有0把序列分成若干段，每段含有若干个1，可以0个，第一个0前面如果没有1，认为有0个1，同样最后一个0后面没有1也认为有0个1。如0011110110010，可以看成序列0，0，4，2，0，1，0。
然后将转化出来的序列错位加减，结果在模3取余数，比如这个序列就是0-0+4-2+0-1+0=1,除以3的余数还是1。
容易看出三种变换下，这个表达式计算结果都不变，所以计算结果不同的序列都无法相互转化。再加上0的数目奇偶性不同不可以相互转化，最终结果的确有6类，互相不能转化

aimisiyou

联想到之前的01虫子问题。http://www.cs.cmu.edu/puzzle/puzzle37.html
有一条虫子，它的整个身体由 n 节构成，每一节要么是有瑕疵的 1 ，要么是没有瑕疵的 0 ，因而整个虫子的身体结构就可以用一个 n 位 01 串来表示。你的目标是把整个虫子变成 000...00 的完美形式。每一次，你可以砍掉虫子最右侧的一节，同时虫子会在最左侧长出新的一节，以保持虫子的总长度不变。如果你砍掉的是一个 1 ，那么你可以指定虫子在最左侧长出的是 1 还是 0 ；但如果你砍掉的是一个 0 ，那么你无法控制虫子会在最左侧长出什么——它可能会长出 0 ，也可能会长出 1 ，因而你不得不假定，概率总是会和你做对，上天会竭尽全力地阻挠你。我们的问题是：不管虫子的初始状态是什么，你总能保证在有限步之内让虫子变成 000...00 吗？

hujunhua

规则1：111↔空，意味着连续的“1”片段，段长模3相等者等价。
规则2：00↔空，意味着连续的“0”片段，段长奇偶相同者等价。
规则3：0101↔空 ←→ 101↔0，即相邻的连续“1”段长之差不变则保持等价。
综合起来就是mathe总结的不变量了。

hujunhua

“好像是那么回事，但结论总显得不流畅”

那就用数学归纳法证明一下吧。
假定串是`L_00L_10L_20...0L_i0...0L_{n-1}0L_n`
这里`L_i`表示两个0之间有`L_i`个连续"1" ，按mathe的说法，`L_i`是可以等于0的。
我们要证明的是`L_00L_10L_20...0L_i0...0L_{n-1}0L_n↔[ΣL_n]_30_{[n]_2}`
这里`ΣL_n=\D\sum^n_{i=0}(-1)^iL_i=L_0-L_1+L_2-\cdots+(-1)^iL_i+\cdots+(-1)^nL_n`，即交错和差，`[\ ]_3`表示取模3最小非负余数，
`[n]_2`表示取模2最小非负余数. `0_{[n]_2}`当`n`为奇数时为0，当`n`为偶数时为空。
当`n=0`时由规则一不证自明。
当`n=1`时，先运用 "插入111” 将`L_0`加长到不短于`L_1`,
                    然后反复运用`101→0`同步削减`L_0`和`L_1`，
                    直到将`L_1`耗尽，得到`[L_0-L_1]_30`.
                    成立。
当`n=2`时，前已得到`L_00L_1↔[L_0-L_1]_30`, 所以`L_00L_10L_2↔[L_0-L_1]_300L_2`,
                   接着运用规则一删去00，成立。
假定`n=k`成立，
当`n=k+1时`，按假定先化成`[ΣL_k]_30L_{k+1}`(k为偶数时）或者`[ΣL_k]_300L_{k+1}`(k为奇数时）
                      前者，`[ΣL_k]_30L_{k+1}`按`n=1`的过程化成`[ΣL_{k+1}]_30`，成立。
                      后者，`[ΣL_k]_300L_{k+1}`运用规则一删去00，得`[ΣL_{k+1}]_3`，成立。
所以，对于任意长的串，上述公式都成立。