设有2n×2n个正方形方格棋盘,在其中任意的3n个方格中各有一枚棋子.求证:可以选出n行和n列,使得3n枚棋子都在这n行和n列中.
问题描述:
设有2n×2n个正方形方格棋盘,在其中任意的3n个方格中各有一枚棋子.求证:可以选出n行和n列,使得3n枚棋子都在这n行和n列中.
答
知识点:此题主要考查了抽屉原理的证明思路,从题设出发进行分析得出与题设出现矛盾,从而得出原命题的正确性.
证明:设各行的棋子数分别P1,P2,Pn,Pn+1,P2n.且P1≥P2≥Pn≥Pn+1≥P2n.
由题设P1+P2+Pn+Pn+1+P2n=3n,①
选取含棋子数为P1,P2,Pn,的这n行,则P1+P2+Pn≥2n,
否则,若P1+P2+Pn≤2n-1,②
则P1,P2,Pn中至少有一个不大于1,
由①,②得Pn+1+P2n≥n+1,
从而Pn+1P2n中至少有一个大于1,这与所设矛盾.
选出的这n行已含有不少于2n枚棋子,再选出n列使其包含其余的棋子(不多于n枚),
这样选取的n行和n列包含了全部3n枚棋子.
答案解析:利用整体换元法,假设出各行棋子数,得出P1+P2+Pn≥2n,分析得出Pn+1+P2n≥n+1,得出与已知矛盾,从而证明n行和n列包含了全部3n枚棋子.
考试点:抽屉原理.
知识点:此题主要考查了抽屉原理的证明思路,从题设出发进行分析得出与题设出现矛盾,从而得出原命题的正确性.