Question

（1）在4×4的方格纸中，把部分小方格涂成红色，然后划去2行和2列，若无论怎么划，都至少有一个红色的小方格没有被划去，则至少要涂多少个小方格？证明你的结论．
（2）如果把上题中的“4×4的方格纸”改成“n×n的方格纸（n≥5）”，其他条件不变，那么，至少要涂多少个小方格？证明你的结论．

Answer 1

（1）至少要涂7个小方格，
证明：假设只涂了6格或更少，则4行中至少有1行未涂或只涂了1格，
若某行未涂，其他3行至少有1行涂了不多于2格，划去这2格所在的2列，划去其他2行，剩下的4格都未涂色，
若某行只涂了1格，其他3行涂了5格或更少，则其中至少有1行涂了不多于1格，划去这2格所在的2列，划去其他2行，剩下的4格都未涂色，
所以只涂了6格或更少，不能满足要求，
另一方面，如果第1行涂1，2格，第2行涂2，3格，
第3行涂1，3格，第4行涂第4格，能满足要求，
所以至少要涂7个小方格．

（2）至少要涂5个小方格，
证明：显然涂4格或更少是不满足要求的，
如果选5个不同行不同列的小方格（如对角线上的5个小方格）涂成红色，能满足要求，
因为，这时任何2行2列，至多只能包含其中4个小方格．