Question

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

（1）求f(2)的值；

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

Answer 1

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

【解析】

(1)如圖①，將T2的4個1×1格子(以下簡稱“格子”)分別記為A、B、C、D，將9個格點(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均為好方格.

由對稱性，不妨設(shè)邊界上8個數(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個稱格子的一條邊為一段“格線”我們對Tn的每段格線標(biāo)記一個箭頭若格線連結(jié)了兩個格點(diǎn)U、V，其中U上的數(shù)小于V上的數(shù)，則對格線UV標(biāo)上一個指向順時(shí)針旋轉(zhuǎn)90°后所得方向的箭頭.

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

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

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

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

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

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

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

綜上可得，.