在4×4的方格中,把部分方格涂红,然后划去2行2列,若无论怎样划,都至少有一个红色小方格没有被划去,则至少要涂多少格?证明你的结论.如把上题的“4×4”改为“2n×2n”’（n>3）,然后划去n行n

Question

在4×4的方格中,把部分方格涂红,然后划去2行2列,若无论怎样划,都至少有一个红色小方格没有被划去,则至少要涂多少格?证明你的结论.
如把上题的“4×4”改为“2n×2n”’（n>3）,然后划去n行n列,其他不变,那么结论应该是至少要涂多少格?

Answer 1

答案是4n
令（a,b）代表第a行第b列,可以考虑以下染色,染红的4n个格子有
(1,1) ,(2,2),……（2n,2n） （就是对角线 ）
(1,n),(2,1),(3,2),……（2n,2n-1） (相当于将对角线向下平移了一格)
对这4n个红格,任意n行中的红格都占了至少n+1 列,所以任意划去n行,还剩n行,这剩下的n行中有n+1 列有红格,所以用n列盖不住
由于4n个红格可以被构造出来,所以结论肯定