一個 n*n 的方格陣，至多塗黑多少個使得不存在 4 個黑格為某矩形頂點？

01-15

矩形指平行於方格表軸的。

從有限幾何的角度來看：把方格陣看成一個點-線結構的關聯矩陣(incidence matrix), 那麼「不存在黑矩形」的條件就轉化成了「過兩點至多有一條線，兩線至多交於一點」……

你想起了什麼？沒錯，有限射影平面的關聯矩陣就滿足這個條件，此時 $n=q^2+q+1$ ，而黑格的個數等於射影平面的flag個數 $(q+1)(q^2+q+1)$ 。

這就說明黑格個數至少是 $O(n^{3/2})$ 。上界的話 @Braid 已經有了一個證明，而且可以證明取等號時相應的結構一定是一個射影平面。

翻了一下別人的答案，發現和@Braid 的思路一樣。不過他沒有給出下界的構造，在此說明一下。

————————

答案是 $Theta(n^{frac{3}{2}})$

首先證明上界。對於一種染色方法，設第i行染黑了ci個格子。

定義集合 $I={(i,j,k)|(i,j),(i,k) 是黑色的}$ .

則由於不存在矩形， $|I|leqinom{n}{2}$ 。另一方面，顯然 $|I|=sum_{i=1}^n inom{c_i}{2}$ ，又由柯西不等式 $sum_{i=1}^n c_i^2geq frac{1}{n} (sum_{i=1}^n c_i)^2$ ，我們得到:

$frac{1}{n}(sum_{i=1}^n c_i)^2-sum_{i=1}^n c_i -n(n-1)leq 0$

解這個不等式得，

$sum_{i=1}^n c_ileq nsqrt{n-frac{3}{4}}+frac{n}{2}=O(n^{frac{3}{2}})$

另一方面，我們給出一個構造來證明下界。注意到當 $n$ 充分大時， $frac{1}{2}sqrt{n}到2sqrt{n}之間有一個素數$ ，這樣一來 $frac{1}{4}n到4n$ 之間有一個素數的平方。所以由單調性，我們只需要證明，當 $n=p^2,p$ 為素數，存在一種染黑 $p^3$ 個格子且沒有四個頂點都被染黑的矩形的方案，就可以證明 $Omega(n^{frac{3}{2}})$ 是原問題下界。構造方法如下:

對於第 $(i-1)p+j$ 行， $(k-1)p+l$ 列的格子，它被染黑當且當 $lequiv ki+j;(mod; p)$

這樣一來，如果我們把每行的格子分成p個block,每個block包含p個格子，每個block里恰好有一個格子被染黑。由於一共有 $p^3$ 個block，故一共有 $p^3$ 個格子被染黑。

用反證法，設第 $(i_1-1)p+j_1$ 行，第 $(i_2-1)p+j_2$ 行與第 $(k_1-1)p+l_1$ 列，第 $(k_2-1)p+l_2$ 列組成的矩形的四個頂點全被染黑了。

這樣一來，我們得到 $l_1equiv k_1i_1+j_1equiv k_1i_2+j_2 (mod;p)$ 與 $l_2equiv k_2i_1+j_1equiv k_2i_2+j_2 (mod;p)$ 。於是，

$(k_1-k_2)(i_1-i_2)equiv 0 (mod;p)$ 。若 $k_1equiv k_2 (mod; p)$ ，則帶入原式得， $l_1equiv l_2 (mod;p)$ ,矛盾。

若 $i_1equiv i_2 (mod;p)$ ,則帶入原式可得， $j_1equiv j_2(mod;p)$ ,矛盾。

故不存在四個頂點都被染黑的矩形。

更新：回家發現這個趣味數學問題居然這麼多回答了！最喜歡 @Wiener ES 的回答，因為最近正在和大佬 @Xf Yuan 做一個類似的染色問題，這個回答給了一個幾何角度構造例子的想法。

回到這個問題，下面的 $sqrt2$ 果然猜錯了，正確的係數是1 。具體構造就是下面的 $Gotimes K_2$ ，感謝評論的提醒。上界就是standard的分析就好了。

－－－－－－－－－－原回答

如果沒理解錯，答案大概是 $Theta(n^{frac{3}{2}})$ ，估計在 $(sqrt2 +o(1))n^{frac{3}{2}}$ 左右，可能有錯。

由於 $K_{n,n}$ 的line graph是 $K_nsquare K_n$ ，所以問題可以轉化成，一個二部圖 $K_{n,n}$ 至多有多少條邊，使得其不包含子圖 $C_4$ 。

這個問題困難之處在於Erdos-Stone theorem用不了，因為 $chi(C_4)=2$ 。但是Turan他們給過一個經典證明，對於n點C4-free圖，最多有 $Theta(n^{frac{3}{2}})$ 條邊，一個達到極值的例子是定義在 $mathbb{Z}_p imesmathbb{Z}_p$ 上的圖， $(x,y)sim(x$ 當且僅當 $x+x$ ，可惜這個不是bipartite的。不過另一個經典結果是幾乎所有的n點C4-free圖都有 $cn^{frac{3}{2}}$ 條邊，其中c是常數，所以我覺得二部圖也應該有一些達到極值的例子，具體的明天再想想，凌晨一點了有點晚了。。

設第 $i$ 行塗了 $p_{i}$ 格，易知 $sum_{i=1}^{n}{inom{p_{i}}{2}}leqinom{n}{2}$ ,順便 $(sum_{i=1}^{n}{p_{i}})^{2}leq nsum_{i=1}^{n}{p_{i}^2}$ ,解得 $sum_{i=1}^{n}{p_{i}}leq (sqrt{n-frac{3}{4}}+frac{1}{2})n$ 。

怎麼證明下界也是這個級別呢……構造好了。習題，求一個 $n=p^{2}$ 時塗黑 $p^3$ 格的構造。

沒仔細看可能有錯。

我記得OI的2004年冬令營上我們討論過這個題……

大家普遍寫程序搜索到了n=7還是多少，然後根據搜出來的玩意提出了各種猜想。然而樓教主的搜索跑到了n=10，於是拿著搜出來的解幹掉了大家提出的所有猜想。於是就討論不下去了。就不了了之了。

（具體數字記不清了，大概是這個意思）

所以如果試圖搜答案找規律的話，請先優化你的搜索……

等價於任意兩行至多只有一個位置同時被塗黑

一些比較小的時候的結果（可能有錯）：

n=2時為3

n=3時為6

n=4時為9

n=5時為12

3n-3是個下界，方法是第一排塗黑前 $leftlceil frac{n+1}{2} ight ceil$ 個，第二排塗黑第一個以及第一排剩下的，其他的行在第二個到第 $leftlceil frac{n+1}{2} ight ceil$ 中塗黑一個，在 $leftlceil frac{n+1}{2} ight ceil + 1$ 個到n個中塗黑一個，保證每兩行都不重複即可。但我猜應該還不是答案。