[問題] 二進位蟲
看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者jurian0101 (Hysterisis)時間13年前 (2012/12/19 18:58)推噓6(6推 0噓 4→)留言10則, 4人參與討論串1/2 (看更多)
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)
推
12/19 20:06, , 1F
12/19 20:06, 1F
推
12/19 21:41, , 2F
12/19 21:41, 2F
推
12/20 04:08, , 3F
12/20 04:08, 3F
→
12/20 08:22, , 4F
12/20 08:22, 4F
推
12/20 13:20, , 5F
12/20 13:20, 5F
→
12/20 13:20, , 6F
12/20 13:20, 6F
推
12/20 13:34, , 7F
12/20 13:34, 7F
推
12/20 13:37, , 8F
12/20 13:37, 8F
→
12/20 20:21, , 9F
12/20 20:21, 9F
※ 編輯: jurian0101 來自: 140.112.213.88 (12/20 20:27)
→
12/28 19:30, , 10F
12/28 19:30, 10F
討論串 (同標題文章)
puzzle 近期熱門文章
5
21
PTT遊戲區 即時熱門文章
