没有2n*2n的正方形棋盘,在其中的任意3n个方格中各方如一枚棋子,求证：可以选出n行和n列使3n枚棋子在这n行和n列中

分类: 作业答案 • 2022-07-15 23:08:58

问题描述：

没有2n*2n的正方形棋盘
,在其中的任意3n个方格中各方如一枚棋子,求证：可以选出n行和n列使3n枚棋子在这n行和n列中

答

3n个棋子放入2n行中.一定可以找到n个行,棋子总数≥2n.证明.把各行棋子数按大到小的次序排列,a1≥a2≥……≥an≥a（n+1）≥……≥a2n.要证a1+……+an≥2n.假如a1+……+an＝2n-m（m＞0）,则a（n+1）+……+a2n＝3n-（2n...