搭桥(3)

KeyTo9_Fans

KeyTo9_Fans又和KeyTo9一起玩游戏了。 这次他们还是玩搭桥游戏。 他们面前有一条宽度为$N$的长河（无限长）。 ———————————————————— 1 ～～～～～～～～～～～～～～～～～～ 2 ～～～～～～～～～～～～～～～～～～ 3 ～～～～～～～～～～～～～～～～～～ . . . N ～～～～～～～～～～～～～～～～～～ ———————————————————— KeyTo9想搭桥过河。 而KeyTo9_Fans在捣乱。 KeyTo9每次可在河里放$2$块$1$*$1$的木板■。 而KeyTo9_Fans每次只能在河里放$1$块$1$*$1$的障碍▓。 KeyTo9的木板是四连通的： 　↑ ←■→ 　↓ 而KeyTo9_Fans的障碍是八连通的： ↖↑↗ ←▓→ ↙↓↘ 木板与障碍不能重叠。 即木板不能放在障碍上。 障碍也不能放在木板上。 KeyTo9_Fans和KeyTo9都是绝顶聪明的。 问： 是否无论河有多宽，KeyTo9都能把桥搭成？ 如果是，请证明之。 如果不是，请找$1$个$N$使得KeyTo9不能把桥搭成。

geslon

那个阻挡者为什么还要说8联通？联通对他有用吗？

geslon

木板可以像下棋一样随便放？还是必须从第一块开始每次都“联通”？

hujunhua

那个阻挡者为什么还要说8联通？联通对他有用吗？ geslon 发表于 2010-10-20 22:53

哈哈哈，我有一次想说，写好帖子又放弃了的话。言之有理，通否无碍。

leeweb

呵呵呵呵呵啊

musi

同样的疑问、

KeyTo9_Fans

八连通只是一个说法。 像下棋一样随便放。

KeyTo9_Fans

现在回想起这个搭桥游戏，发现没什么意思。 无论河宽$N$等于多少，KeyTo9都可以把桥搭成，而且桥长为$N$。 方法如下： KeyTo9选取$2^N$列，各放$1$块木板。 Fans最多只能挡掉其中的$2^{N-1}$列。 KeyTo9在剩余的$2^{N-1}$列中各放$1$块木板。 Fans最多只能挡掉其中的$2^{N-2}$列。 KeyTo9在剩余的$2^{N-2}$列中各放$1$块木板。 Fans最多只能挡掉其中的$2^{N-3}$列。 依次类推。 最后KeyTo9把某一列的$N$个格子全部放满了，于是搭桥成功，桥长为$N$。