Question

（1）在4×4的方格紙中，把部分小方格涂成紅色，然后劃去2行和2列，若無論怎么劃，都至少有一個紅色的小方格沒有被劃去，則至少要涂多少個小方格？證明你的結(jié)論．
（2）如果把上題中的“4×4的方格紙”改成“n×n的方格紙（n≥5）”，其他條件不變，那么，至少要涂多少個小方格？證明你的結(jié)論．

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個小方格．