题目

设有2n×2n个正方形方格棋盘，在其中任意的3n个方格中各有一枚棋子．求证：可以选出n行和n列，使得3n枚棋子都在这n行和n列中．

提问时间：2021-01-04

答案

证明：设各行的棋子数分别P₁，P₂，P_n，P_n+1，P_2n．且P₁≥P₂≥P_n≥P_n+1≥P_2n．
由题设P₁+P₂+P_n+P_n+1+P_2n=3n，①
选取含棋子数为P₁，P₂，P_n，的这n行，则P₁+P₂+P_n≥2n，
否则，若P₁+P₂+P_n≤2n-1，②
则P₁，P₂，P_n中至少有一个不大于1，
由①，②得P_n+1+P_2n≥n+1，
从而P_n+1P_2n中至少有一个大于1，这与所设矛盾．
选出的这n行已含有不少于2n枚棋子，再选出n列使其包含其余的棋子（不多于n枚），
这样选取的n行和n列包含了全部3n枚棋子．