二進位蟲 - 拼圖

Dinah avatar
By Dinah
at 2012-12-19T18:58

Table of Contents

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必然陷入僵局？


- - -
--
Tags: 拼圖

All Comments

Christine avatar
By Christine
at 2012-12-21T11:09
若自0101起 B每次回最左之異號 A將以何策攻之?
Jack avatar
By Jack
at 2012-12-26T03:47
嗯...這樣不行
Christine avatar
By Christine
at 2012-12-30T14:22
不太懂"A聰明一點即可強迫取勝"中101怎樣變110的?
Linda avatar
By Linda
at 2013-01-01T15:16
因為最右是1，由A決定，所以左邊生出1或0，A選1這樣
Charlie avatar
By Charlie
at 2013-01-05T21:12
蠻有趣的題目 A的目的是要變全0但是在能成功前的那一步
他的選擇大多要是1 B則相反
Madame avatar
By Madame
at 2013-01-10T08:06
如果不求最小次數的話 A就無腦填1 不管B怎麼填A一定贏
Tom avatar
By Tom
at 2013-01-10T10:43
好像不太完整 某些情況A要填0整理一下牌型…
Daph Bay avatar
By Daph Bay
at 2013-01-13T15:20
有趣吧フフフフ
James avatar
By James
at 2013-01-14T16:41
有趣是有趣 不過因為太難 過了一個禮拜都沒後續 XD

將棋 詰棋 011

Suhail Hany avatar
By Suhail Hany
at 2012-12-13T23:14
┬─┬─┬─┬─┐ ┬─┬─┬─┬─┐ ┬─┬─┬─┬─┐ │ │ │ │玉│ │金│銀│ │玉│ │ │銀│ │玉│ ┼─┼─┼─┼─┤ ┼─┼─┼─┼─┤ ┼─┼─┼─┼─┤ │ │ │ │ │ 持 ...

ProjectEuler 405 A rectangular tiling

Barb Cronin avatar
By Barb Cronin
at 2012-12-11T08:33
405. A rectangular tiling http://projecteuler.net/problem=405 我們想要拼出一個長是寬的兩倍的矩形 令 T(0) 為一個完整未分割的矩形 對於所有 nandgt;0 定義 T(n) 為對 T(n-1) 中的每一個構成矩形進行如下的代換 ht ...

ProjectEuler 404 Crisscross Ellipses

Yedda avatar
By Yedda
at 2012-12-11T08:19
404. Crisscross Ellipses http://projecteuler.net/problem=404 E_a 是平面坐標系上由方程式 x^2 + 4y^2 = 4a^2 定義的橢圓 E_aand#39; 是 E_a 以原點為旋轉中心逆時針旋轉角度θ所形成的圖形 其中0°andlt; ...

educa補片

Quanna avatar
By Quanna
at 2012-12-07T23:28
想請問大家 有沒有透過educa網站申請補片的經驗 今天好不容易完成一幅很久以前親戚送的拼圖 http://ppt.cc/LDrz 但卻在偏中間的天空缺了一片(崩潰中) 爬了一下文發現大家多是去小雷補片 想請問有沒有人是從他們官網填過申請單 http://www.puzzlepassion.co ...

將棋 詰棋 010 (已解答)

Joe avatar
By Joe
at 2012-12-06T23:23
│ │王│ │ │1 │ │ │王│香│2 │ │ │玉│ │3 ┼─┼─┼─┼─┤ ┼─┼─┼─┼─┤ ┼─┼─┼─┼─┤ │ │ │銀│ │持 │ │ │ │ │持 │ │ │ │ │持 ┼─┼─┼─┼─┤駒 ...