Question

给定大于2004的正整数n，将1、2、3、…、分别填入n×n棋盘（由n行n列方格构成）的方格中，使每个方格恰有一个数。如果一个方格中填的数大于它所在行至少2004个方格内所填的数，且大于它所在列至少2004个方格内所填的数，则称这个方格为“优格”。求棋盘中“优格”个数的最大值。

Answer 1

解析：为叙述方便，如果一个方格中填的数大于它所在行至少2004个方格中所填的数，则称此格为行优的。由于每一行中填较小的2004个数的格子不是行优的，所以每一行中有n－2004个行优的。一个方格为“优格”一定是行优的，所以棋盘中“优格”个数不大于。

    另一方面，将棋盘的第i行，第（大于n时取模n的余数）列中的格子填入“*”。将1、2、3、…、2004n填入有“*”的格子，其余的数填入没有“*”的格子。没有“*”的格子中填的数大于有“*”的格子中任何一个数，所以棋盘上没有“*”的格子都为“优格”，共有个。

    此时每行有2004个格子有“*”，每列也有2004个格子有“*”（如图）。实际上，当时，第i列的第1、2、…、i、n+i－2003、n+i－2002、...、n行中有“*”。当时，第i列的第i－2003、i－2002、...、i行中有“*”。所以每行有2004个格子有“*”，每列也有2004个格子有“*”（如图）

*	*	*
	*	*	*
		*	*	*
			*	*	*
				*	*	*
					*	*	*
*						*	*
*	*						*

所以棋盘中“优格”个数的最大值是。