找回密码
 欢迎注册
查看: 2804|回复: 20

[讨论] 01串的增减操作问题

[复制链接]
发表于 2023-7-28 21:06:31 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
对于一个由0、1组成的序列,定义操作:在此序列开头或者结尾或者中间任意位置,填上或删去00,111,0101,问:序列01是否能通过若干次操作变成序列10?
注:中间位置删去后自动合拢
精华
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-7-29 10:37:24 | 显示全部楼层
如果答案是肯定的,即0和1是可以交换位置的,那么串的次序就无关紧要了,串就等价于集合了。
0,2个2个地删,最后只剩一个或被删光。
1,3个3个地删,配合2个2个地删,可以全部删光。
结果所有的串,要么变成0,要么变成空。这不太可能。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-7-29 12:35:52 | 显示全部楼层
操作都是可逆的,如果串 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”和“空”两个等价类了.

这不太可能。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-7-29 13:04:25 | 显示全部楼层
0011->0101没看懂?

点评

哦,没仔细看前提。  发表于 2023-7-29 17:37
在假设 01->10 可互变的前提下,将 0011 中间的两位从 01->10,即得 0101  发表于 2023-7-29 17:21
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-7-29 20:46:52 | 显示全部楼层
看起来6个等价类好像互不等价,不能进一步归并。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-7-29 23:50:29 | 显示全部楼层
能互转的肯定可以列出转换过程,但不能转换的怎么来证明呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-7-30 07:48:51 来自手机 | 显示全部楼层
找到解决方案了,序列中的所有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类,互相不能转化

点评

mathe洞察力还是那么敏锐!  发表于 2023-7-31 12:49
需要证明,不过把规则中0101替换为hu的规则101->0(容易证明替换后等价)会更加容易证明。  发表于 2023-7-30 17:05
“容易看出”,是不是要经过证明?  发表于 2023-7-30 08:53
为啥要这样分列?根本原理是啥?  发表于 2023-7-30 08:42
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-7-31 14:03:08 | 显示全部楼层
联想到之前的01虫子问题。http://www.cs.cmu.edu/puzzle/puzzle37.html
有一条虫子,它的整个身体由 n 节构成,每一节要么是有瑕疵的 1 ,要么是没有瑕疵的 0 ,因而整个虫子的身体结构就可以用一个 n 位 01 串来表示。你的目标是把整个虫子变成 000...00 的完美形式。每一次,你可以砍掉虫子最右侧的一节,同时虫子会在最左侧长出新的一节,以保持虫子的总长度不变。如果你砍掉的是一个 1 ,那么你可以指定虫子在最左侧长出的是 1 还是 0 ;但如果你砍掉的是一个 0 ,那么你无法控制虫子会在最左侧长出什么——它可能会长出 0 ,也可能会长出 1 ,因而你不得不假定,概率总是会和你做对,上天会竭尽全力地阻挠你。我们的问题是:不管虫子的初始状态是什么,你总能保证在有限步之内让虫子变成 000...00 吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-7-31 16:42:11 | 显示全部楼层
规则1:111↔空,意味着连续的“1”片段,段长模3相等者等价。
规则2:00↔空,意味着连续的“0”片段,段长奇偶相同者等价。
规则3:0101↔空 ←→ 101↔0,即相邻的连续“1”段长之差不变则保持等价。
综合起来就是mathe总结的不变量了。

点评

好像是那么回事,但结论总显得不流畅。  发表于 2023-7-31 20:12
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-8-4 10:43:03 | 显示全部楼层
“好像是那么回事,但结论总显得不流畅”

那就用数学归纳法证明一下吧。
假定串是`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`,成立。
所以,对于任意长的串,上述公式都成立。

评分

参与人数 1威望 +3 金币 +3 贡献 +3 经验 +3 鲜花 +3 收起 理由
aimisiyou + 3 + 3 + 3 + 3 + 3 很给力!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-4-19 13:11 , Processed in 0.063540 second(s), 24 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表