Question

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

（1）求f(2)的值；

（2）求f(n)關(guān)于正整數(shù)n的表達(dá)式.

Answer 1

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

【解析】

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

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

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

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

綜上可得f(2)=3.

(2)設(shè)Tn的各格點(diǎn)的數(shù)已被分配好，此時(shí)好方格有k個(gè)稱(chēng)格子的一條邊為一段“格線(xiàn)”我們對(duì)Tn的每段格線(xiàn)標(biāo)記一個(gè)箭頭若格線(xiàn)連結(jié)了兩個(gè)格點(diǎn)U、V，其中U上的數(shù)小于V上的數(shù)，則對(duì)格線(xiàn)UV標(biāo)上一個(gè)指向順時(shí)針旋轉(zhuǎn)90°后所得方向的箭頭.

稱(chēng)一個(gè)格子S及S的一條邊UV所構(gòu)成的有序?qū)?/span>(S，UV)為一個(gè)“對(duì)子”，如果UV上所標(biāo)的箭頭由S內(nèi)指向S外設(shè)對(duì)子總數(shù)為N.

一方面，每個(gè)格子S至少貢獻(xiàn)1個(gè)對(duì)子(否則沿逆時(shí)針?lè)较蜃xS頂點(diǎn)上的數(shù)將永遠(yuǎn)遞減，矛盾)，而根據(jù)好方格的定義每個(gè)好方格貢獻(xiàn)3個(gè)對(duì)子，于是.

另一方面，Tn的每段格線(xiàn)至多貢獻(xiàn)1個(gè)對(duì)子，且Tn邊界上至少有一段格線(xiàn)標(biāo)有向內(nèi)的箭頭(否則，沿逆時(shí)針?lè)较蜃xn邊界上的數(shù)將永遠(yuǎn)遞增，矛盾)，從而不貢獻(xiàn)對(duì)子.注意到Tn的格線(xiàn)段數(shù)為2n(n+1)，所以又有.

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

最后，對(duì)n為奇數(shù)和n為偶數(shù)的情況，分別如圖②和圖③，將1，2，……，(n+1)2按粗線(xiàn)經(jīng)過(guò)的次序依次分配給所有格點(diǎn)對(duì)圖中標(biāo)有“▲”記號(hào)的每個(gè)格子，易驗(yàn)證，按被粗線(xiàn)經(jīng)過(guò)的先后次序排列其4個(gè)頂點(diǎn)，恰是一種逆時(shí)針排列，因而這些格子均為好方格.

圖②中好方格數(shù)為.

圖③中好方格數(shù)為.

綜上可得，.