IBM Ponder This #092 · 2005 年 12 月

在无限方格棋盘上封锁一部分格子，阻止某个固定多格骨牌 P 完整放下。骨牌必须与格子对齐，允许旋转及镜像。把达到这一目的所需封锁格子的最小密度记作 f(P)。

例如，当 P 是 L 形三格骨牌时：

OO
 O

封锁棋盘一种颜色、隔一行封一行或隔一列封一列，都能用密度 1/2 阻止它；另一方面，每个 2×2 方块至少要封两个格子，因此 f(P)=1/2。

本题改用 V 形五格骨牌：

OOO
  O
  O

求 f(P)，并给出达到该密度的封锁配置。原题不要求证明最优性，只要求数值和构造。

解答

认真尝试后再打开

待补充。