作者jurian0101 (Hysterisis)
看板puzzle
标题[问题] 二进位虫
时间Wed Dec 19 18:58:56 2012
Edit: 把有解答的出处删除
- - -
有一只蠕虫的身体由完全相同的Ｎ节构成，每一节可能是完美的 (记作0)，
或有缺陷的 (记作1)。
有两名玩家Ａ与Ｂ。Ａ的目标是将虫变成全部完美的000...0，Ｂ的目标是
阻碍Ａ。
转变虫的规则是当从虫的最右边切下一节，若此段是1，Ａ可决定最左边长出0或1
若此段是0，则Ｂ可决定左边长出来的是0还是1。
请问是否对任何长度N的任何虫 (01字串)，Ａ都有保证在有限次切割内获胜的方法。
例如101 若A只是将1尽量变成0
A-> 010
则B可以使其进入循环
B-> 101
若A聪明一点即可强迫取胜
101
A-> 110
B-> 111/011 -> 无论如何，A胜
- - -
其实这题疑难在於，存不存在［无论A做什麽，B都可以强迫进入回圈］这样子的字串？
- - -
Update:
想完原题也可以变一下，原题中A有优势是因为000...0和111...1其实都是A赢 B很无奈
若改成一样，A控1，B控0，A胜利条件= 000...0，B胜利条件= 111...1。
是否对於每一个A或B无法马上获胜的序列 (如00111 A秒胜, 11000 B秒胜，我们排除
这些trivial状况) AB必然陷入僵局？
- - -
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.213.88
※ 编辑: jurian0101 来自: 140.112.213.88 (12/19 19:14)
1F：推 walkwall:若自0101起 B每次回最左之异号 A将以何策攻之? 12/19 20:06
2F：推 walkwall:嗯...这样不行 12/19 21:41
3F：推 jennya:不太懂"A聪明一点即可强迫取胜"中101怎样变110的? 12/20 04:08
4F：→ jurian0101:因为最右是1，由A决定，所以左边生出1或0，A选1这样 12/20 08:22
5F：推 grooving:蛮有趣的题目 A的目的是要变全0但是在能成功前的那一步 12/20 13:20
6F：→ grooving:他的选择大多要是1 B则相反 12/20 13:20
7F：推 grooving:如果不求最小次数的话 A就无脑填1 不管B怎麽填A一定赢 12/20 13:34
8F：推 grooving:好像不太完整 某些情况A要填0整理一下牌型… 12/20 13:37
9F：→ jurian0101:有趣吧フフフフ 12/20 20:21
※ 编辑: jurian0101 来自: 140.112.213.88 (12/20 20:27)
10F：→ walkwall:有趣是有趣 不过因为太难 过了一个礼拜都没後续 XD 12/28 19:30