Question

設(shè)有2n×2n個正方形方格棋盤，在其中任意的3n個方格中各有一枚棋子．求證：可以選出n行和n列，使得3n枚棋子都在這n行和n列中．

Answer 1

分析：利用整體換元法，假設(shè)出各行棋子數(shù)，得出P₁+P₂+P_n≥2n，分析得出P_n+1+P_2n≥n+1，得出與已知矛盾，從而證明n行和n列包含了全部3n枚棋子．

解答：證明：設(shè)各行的棋子數(shù)分別P₁，P₂，P_n，P_n+1，P_2n．且P₁≥P₂≥P_n≥P_n+1≥P_2n．
由題設(shè)P₁+P₂+P_n+P_n+1+P_2n=3n，①
選取含棋子數(shù)為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，這與所設(shè)矛盾．
選出的這n行已含有不少于2n枚棋子，再選出n列使其包含其余的棋子（不多于n枚），
這樣選取的n行和n列包含了全部3n枚棋子．

點評：此題主要考查了抽屜原理的證明思路，從題設(shè)出發(fā)進(jìn)行分析得出與題設(shè)出現(xiàn)矛盾，從而得出原命題的正確性．