[問題] 二進位蟲

[jurian0101 (Hysterisis)]

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)
推 walkwall:若自0101起  B每次回最左之異號  A將以何策攻之?
推 walkwall:嗯...這樣不行
推 jennya:不太懂"A聰明一點即可強迫取勝"中101怎樣變110的?
→ jurian0101:因為最右是1，由A決定，所以左邊生出1或0，A選1這樣
推 grooving:蠻有趣的題目 A的目的是要變全0但是在能成功前的那一步
→ grooving:他的選擇大多要是1 B則相反
推 grooving:如果不求最小次數的話 A就無腦填1 不管B怎麼填A一定贏
推 grooving:好像不太完整 某些情況A要填0整理一下牌型…
→ jurian0101:有趣吧フフフフ
※ 編輯: jurian0101      來自: 140.112.213.88       (12/20 20:27)
→ walkwall:有趣是有趣  不過因為太難  過了一個禮拜都沒後續 XD