Question

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

Answer 1

分析：利用整体换元法，假设出各行棋子数，得出P₁+P₂+P_n≥2n，分析得出P_n+1+P_2n≥n+1，得出与已知矛盾，从而证明n行和n列包含了全部3n枚棋子．

解答：证明：设各行的棋子数分别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枚棋子．

点评：此题主要考查了抽屉原理的证明思路，从题设出发进行分析得出与题设出现矛盾，从而得出原命题的正确性．