Question

【題目】設n為正整數，稱n×n的方格表Tn的網格線的交點(共(n+1)2個交點)為格點.現將數1，2，……，(n+1)2分配給Tn的所有格點，使不同的格點分到不同的數.稱Tn的一個1×1格子S為“好方格”，如果從2S的某個頂點起按逆時針方向讀出的4個頂點上的數依次遞增(如圖是將數1，2，…，9分配給T2的格點的一種方式，其中B、C是好方格，而A、D不是好方格)設Tn中好方格個數的最大值為f(n).

（1）求f(2)的值；

（2）求f(n)關于正整數n的表達式.

Answer 1

【答案】（1）f(2)=3.（2）.

【解析】

(1)如圖①，將T2的4個1×1格子(以下簡稱“格子”)分別記為A、B、C、D，將9個格點上的數分別記為a、b、c、d、e、f、g、h、i.

當a，b，……，i依次取為1，2，……，9時，易驗證B、C、D均為好方格，這表明f(2)≥3.

現假設f(2)=4，即存在一種數的分配方式，使A、B、C、D均為好方格.

由對稱性，不妨設邊界上8個數a，b，……，h中的最小數為a或b.此時由A為好方格知，或者有a<b<i<h，或者有b<i<h<a，故b<i<h總是成立的.進而由B、C為好方格知，必有i<f<g<h，b<c<d<i，但這時d<i<f，與D為好方格矛盾.

綜上可得f(2)=3.

(2)設Tn的各格點的數已被分配好，此時好方格有k個稱格子的一條邊為一段“格線”我們對Tn的每段格線標記一個箭頭若格線連結了兩個格點U、V，其中U上的數小于V上的數，則對格線UV標上一個指向順時針旋轉90°后所得方向的箭頭.

稱一個格子S及S的一條邊UV所構成的有序對(S，UV)為一個“對子”，如果UV上所標的箭頭由S內指向S外設對子總數為N.

一方面，每個格子S至少貢獻1個對子(否則沿逆時針方向讀S頂點上的數將永遠遞減，矛盾)，而根據好方格的定義每個好方格貢獻3個對子，于是.

另一方面，Tn的每段格線至多貢獻1個對子，且Tn邊界上至少有一段格線標有向內的箭頭(否則，沿逆時針方向讀n邊界上的數將永遠遞增，矛盾)，從而不貢獻對子.注意到Tn的格線段數為2n(n+1)，所以又有.

綜合兩方面得，2k+n2≤2n(n+1)－1，即好方格的個數.

最后，對n為奇數和n為偶數的情況，分別如圖②和圖③，將1，2，……，(n+1)2按粗線經過的次序依次分配給所有格點對圖中標有“▲”記號的每個格子，易驗證，按被粗線經過的先后次序排列其4個頂點，恰是一種逆時針排列，因而這些格子均為好方格.

圖②中好方格數為.

圖③中好方格數為.

綜上可得，.