题目
如果你想用不与正方形的边平行的直线覆盖一个10×10方格中的所有格点(顶点),需要多少条直线?
分析
解释:题目中“10×10 点阵”指每边有10个格点(原文是10×10 square grid,点坐标0..9),共100个格点。
下界(不可能少于18条)。边界上的格点数为\(4\times 10-4=36\)。任何不与正方形边平行的直线与大正方形的边相交于两点,至多通过两个边界格点,因此t条直线最多覆盖2t个边界格点,得\(2t\ge36\)`,故\(t\ge18\)。
上界(给出18条的构造)。取17条自西北到东南(NW–SE)的对角线,这些平移的对角线覆盖了除了两个对角角点之外的所有格点。再加上一条自西南到东北(SW–NE)的对角线,就可以覆盖这两个角点。因此总共18条不与边平行的直线就能覆盖全部100个格点。
结论:下界和上界一致,所需最少直线条数为18条。