数学吧 关注:876,010贴子:8,694,313
  • 0回复贴,共1

捉猫游戏(八连通地板)

只看楼主收藏回复

正方形格子铺成的无限大的地板中,某个格子里有一只猫。 
每一回合,我们可以在某个格子里下一个陷阱(猫当前所在的那个格子不能下陷阱)。 
每下一个陷阱,猫可以移动一步到相邻的格子里。
猫可以横走竖走或斜走,因此相邻的格子有八个。
猫不可以走到下过陷阱的格子里。 
陷阱永远都不会消失。 
我们可以假设猫是绝顶聪明的,总是采取最佳策略:能逃开一定会逃开;若逃不开,它会尽量在被围死前走尽可能多的步数。
问能否可以把猫围得无路可走? 
如果可以,至少需要多少个陷阱? 
如果不可以,最好能证明一下。


IP属地:安徽1楼2009-02-09 17:17回复