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個格子有“*”（如圖）

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

所以棋盤中“優格”個數的最大值是。