nn的格子區域，隨機向其中放置mm的小格子，m小於n，直至無法放置，小格子佔據面積比例期望多少？

01-21

添加一些條件的詳細解釋。單位是固定的，小格子不允許重疊，但是可以不對齊，無法斜著放，因為格子無法旋轉，放置的過程中位置是隨機的。下圖舉例
------------------------------------------分割線--------------------------------------------------
首先感謝各位答主的分析和解答，周末沒有時間對各位的疑問做出解釋和回答（主要是內容需要消化，數學戰5渣(*/ω＼*)）
在此主要回答 @0613 的問題，這個問題的來由和現實問題。這個問題主要是為了模擬和解答這麼一個場景的問題，簡單點的版本就是：在一個公園內，遊客可以進行露營，每個遊客會佔據一定的區域面積作為自己的活動範圍，那麼給定公園面積和遊客活動面積的時候，我應該允許多少遊客進場可以保證儘可能高的利用率和遊客滿意度。

原來的提問我已經對這個問題進行了抽象和條件限定，覺得這樣可能會讓問題簡單些。這個問題的核心條件在於一個前提假設：遊客的對滿意度的敏感度是無限大的，也就是說遊客不能容忍自身的活動區域與其他人的範圍有交叉，也不能容忍有人干預自己的選擇，安排自己的落腳點。這個假設應該是這個問題最核心的條件，至於區域形狀是否是正方形還是矩形應該不太重要，只是我簡單化的條件而已。歡迎大家提供條件補充或者方便模擬計算的條件限定和假設。以上。
當然我也不知道類似的問題是不是已經有人考慮過，我搜索過，沒有找到。問題的答案要求並不局限在給出數學的準確計算和公式，有分析方法和思路，提供模擬計算方法和近似答案就已經滿足了題主的需求，希望大家集思廣益，謝謝各位~

更新：連續情況的討論

==================================================================

二維的情況除了模擬以外難以下手，但是一維的情況是有解析解的，可以先考慮1*n的格子上放置1*m的格子的情況，然後看看它的平方能否作為一個近似值。

這個問題不難解答，因為放下1*m個格子之後恰好將剩下的格子分成兩份，這樣我們記1*n個格子上放1*m方塊，最後空下的格子的期望值為 $f(n,m)$ ，則

$f(n,m) = frac{1}{n-m+1}sum_{i=0}^{n-m} left(f(i,m) + f(n - i - m, m) ight) = frac{2}{n-m+1}sum_{i=0}^{n-m} f(i,m)$

邊界條件：當n&

記

$S(n,m) = sum_{i=0}^{n}f(i,m)$

則

$S(n,m) - S(n-1,m) = frac{2}{n-m+1}S(n-m,m)$

注意雖然有n和m兩個符號，但m是個固定的量，這是一維數列的遞推。

算一下m=2的情況，和 @王贇 Maigo 的答案一樣，畫出佔比和佔比平方：

可以看出基本是一致的，平方的極限大約是0.745

固定n=100的情況也與 @王贇 Maigo 的結果基本一致。

二維情況的期望約等於一維情況的平方，沒有想到很好的嚴格證明方法，但是解釋起來是不困難的：考慮二維中的每個方格，這個方格所在的行和所在的列，可以看成是一個一維的隨機擺放問題，這兩個擺放應該是獨立的，那麼這個格子實際被占的概率（也就是0-1變數的期望值）就是兩個一維擺放的乘積，然後我們用霸道的「期望和等於和的期望」對它求和，那麼應該就是一維擺放的期望值的平方。當然這個解釋是很粗糙的，實際上在某些邊界條件上，它們可能是不相等的。

畫出n=1000的情況：

可以看到形狀幾乎沒有發生變化，只是第一段更陡了而已。約1/4的地方的確有個很小的波動，但是與 @王贇 Maigo 的猜測不太一樣的是，似乎這個凸起並沒有比n=100變得更明顯。

我們可以設想當n足夠大的時候，我們可以將這個問題看成是連續版本的：在固定大小的正方形當中隨機放入小正方形，位置均勻分布，平均能放下多少個。在整數比例上期望值的突變來源於我命名為「整除」效應的效果：要讓接近於整數倍的正方形（或者一維條形）剛好放進去，需要讓形狀恰好排在整數比例附近，概率會急劇減小，因此在整數k倍附近，最大覆蓋比例會從 $frac{k-1}{k}$ 突變到 $frac{k-2}{k-1}$ 。注意到兩者的差別是 $frac{1}{k(k-1)}$ ，隨著k變大這個值會迅速變小，因此整除效應會越來越不明顯。

連續版本的方程可以將求和改寫成積分得到，記 $f(x)$ 為在長度為1的線段上覆蓋長度為x的區間的平均覆蓋率：

$f(x) = x + frac{2}{1-x} int_x^{1-x} uf(frac{x}{u})du = x+ frac{2x^2}{1-x} int^1_frac{x}{1-x} frac{1}{t^3}f(t)dt$

邊界條件為： $f(x) = x ,frac{1}{2} le x le 1$

這個方程甚至不需要微分就可以解出來，注意右邊的積分下限，當 $frac{1}{k+1} le x < frac{1}{k}$ 時， $frac{1}{k} le frac{x}{1-x} < frac{1}{k-1}$ ，它是個簡單分段的函數……接下來我們可以計算一下每一段的函數表達式。

==========================================================

接上文：

當 $frac{1}{3} le x < frac{1}{2}$ 的時候， $f(x) = x + frac{2x^2}{1-x} int^1_frac{x}{1-x} frac{1}{t^3}tdt = x + frac{2x^2}{1-x} left(left.-frac{1}{t} ight|_frac{x}{1-x}^1 ight) = x + frac{2x^2}{1-x}(frac{1}{x} - 2)$

$=x + frac{2x(1-2x)}{1-x} = frac{3x-5x^2}{1-x}=3x - frac{2x^2}{1-x}$

當 $frac{1}{4}le x < frac{1}{3}$ 的時候，

$f(x) = x + frac{2x^2}{1-x} left(1 + int^frac{1}{2}_frac{x}{1-x} frac{1}{t^3}(3t - frac{2t^2}{1-t})dt ight)$

$=x + frac{2x^2}{1-x} left(1 + left.left(-frac{3}{t} - 2ln frac{t}{1-t} ight) ight|^frac{1}{2}_frac{x}{1-x} ight)$

$=x + frac{2x^2}{1-x} left(-8+frac{3}{x} + 2ln frac{x}{1-2x} ight)$

和離散的情況符合得還是很好的。

但是接下來就沒有那麼容易了，直接積分顯然不靠譜，改寫一下遞推式：

$frac{1}{k+1} le x < frac{1}{k}$ 時，

$f(x) =x+ frac{2x^2}{1-x} int^1_frac{x}{1-x} frac{1}{t^3}f(t)dt=x+ frac{2x^2}{1-x} left(int^frac{1}{k-1}_frac{x}{1-x} frac{1}{t^3}f(t)dt + int^1_frac{1}{k-1} frac{1}{t^3}f(t)dt ight)$

而

$f(frac{1}{k}) =frac{1}{k}+ frac{2}{k(k-1)} int^1_frac{1}{k-1} frac{1}{t^3}f(t)dt$

所以

$f(x) =x+ frac{2x^2}{1-x} left(int^frac{1}{k-1}_frac{x}{1-x} frac{1}{t^3}f(t)dt + frac{(kf(frac{1}{k})-1)(k-1)}{2} ight)$

我們想為k足夠大的時候的f(x)找一個近似，那就簡單粗暴令 $f(x) = Ax + B$ 好了，代回去

$f(x) =x+ frac{2x^2}{1-x} left(int^frac{1}{k-1}_frac{x}{1-x} frac{1}{t^3}(At + B)dt + frac{(A + Bk - 1)(k-1)}{2} ight)$

$=x+ frac{2x^2}{1-x} left(left.-frac{A}{t}-frac{B}{2t^2} ight|^frac{1}{k-1}_frac{x}{1-x} + frac{(A + Bk - 1)(k-1)}{2} ight)$ $=x+ frac{2x^2}{1-x} left(-A(k-1)-frac{B(k-1)^2}{2}+frac{A(1-x)}{x}+frac{B(1-x)^2}{2x^2} + frac{(A + Bk - 1)(k-1)}{2} ight)$

$=x+ frac{2x^2}{1-x} left(frac{A(1-x)}{x}+frac{B(1-x)^2}{2x^2} + frac{(-A + B - 1)(k-1)}{2} ight)$

$=x+ 2Ax + B(1-x) + frac{2x^2}{1-x} left(frac{(-A + B - 1)(k-1)}{2} ight)$

當 $B = A + 1$ 時，原式恰好等於 $Ax + B$ 。也就是 $f(x) = A(x+1) + 1$

我們可以用f(1/4)算個近似值出來，因為f(1/4) = 0.6856，所以 $A = -0.2515$ ， $B = 0.7485$ 。或者我們可以乾脆猜測B=0.75。

這四段擬合可以作為一維情況的最終結果，它的平方可以作為二維情況的最終結果。不過，連續情況無法解釋固定m=2,m=3這樣的情況下的極限值。

首先，這題一看就知道解析計算幾乎是不可能的，所以採用模擬的方法。

模擬時採用 @Yivan 的等價表述：在 (n-m+1) * (n-m+1) 的棋盤上選點，讓任意兩點在兩個方向上的距離都至少為 m。為了不喧賓奪主，代碼就略了。

我對 100 以內的所有 n,m 都模擬了 1000 次，計算平均覆蓋率。這個範圍算是對 @醬紫君答案的拓展。其中，m = 1 和 m &> n/2 的情況是不用模擬的，因為答案顯然。

平均覆蓋率的圖如下：

立體圖：

分析：在 m = n/2 處有一條比較深的溝壑，即小正方形邊長為大正方形一半的時候，空出的面積會顯著地比較大。在 m = n/3 處也有一條比較淺的溝壑，這條溝壑在 @醬紫君的答案里看不出來，它產生的原因跟第一條溝壑應該是類似的。我猜想，如果繼續增大 n,m 的範圍，在 m = n/4, m = n/5 等處也都會產生溝壑，但會越來越淺，以至於看不出來了。

觀察固定 n = 100 時的截面，可以看到兩條溝壑：

觀察固定 m = 2 時的截面，可以看到覆蓋率的確收斂，我猜想收斂於 0.75：

事實上，m 取其它比較小的值，例如 3, 4 時，覆蓋率也都收斂。這個極限應該是 m 的函數，具體表達式是什麼是一個有意思的研究課題。

同時注意到由於溝壑的存在，上面這種收斂並不是一致收斂。

這個問題很像統計物理中的hard sphere問題，不過並不是一般考慮的「最密堆積」或者是另一個答主里說的「MAX」 independent set（對應於轉了45°，m=sqrt{2}的方塊）。因為我們只是隨機的放格子直到放不下，所以最後得到的一定不是全局最優解，而是某種意義下的local最優解。

還有一個讓問題更複雜的因素是，隨機放格子「直到放到」第N個，和隨機「放」N個格子，最後產生的格子分布是不一樣的。第一種在最開始的階段會更浪費一些。這也讓分析更複雜，不能直接套用後者已經被分析的很清楚的各種phase transition。

如果固定m令n趨於無窮，個人猜測的最後的密度應該趨近於某種「liquid phase」的臨界點，即長程無序，短程有序。但要是考慮具體的值，哪怕是Independent set感覺也至少可以發一篇Physics review E或者Annals of applied probability了，如果能編出一個好故事且沒有人已經考慮過了的話. ┑(￣Д ￣)┍

其他答主的回答已經進行了大量的數值模擬，甚至連續情況的表達式都已解出，本回答主要關注離散的一維情況的極限值，關鍵在於求解一個 @靈劍得到遞推式的極限（二維情況參考靈劍的用一維的平方來估計的方法）。

考慮1*n的格子上放置1*m的格子，最終剩餘格子的期望記為 s(n,m) ，其遞推式是

$s(n,m)= frac 2 {n-m+1} sum_{k=0}^{n-m} s(k,m)$ ,

邊界條件是n&

$egin{align} G_m(z) equiv sum_{k geq 0} z^ks(k,m) \ =sum_{k=0}^{m-1}kz^k+ 2sum_{n geq m} frac{z^n}{n-m+1} sum_{k=0} ^{n-m} s(k,m) end{align}$ .

為了消去分母 n-m+1，我們稍微整理一下

$frac{G_m(z) -sum_{k=0}^{m-1}kz^k}{z^{m-1}} = 2sum_{n geq m} frac{z^{n-m+1}}{n-m+1} sum_{k=0} ^{n-m} s(k,m)$ .

然後式子兩邊對z求導，得到

$frac{G_m$ ,

觀察到上式的右邊等於 2Gm(z)/(1-z)，再整理一下得到關於G的一階微分方程

$G_m$ .

初始條件是 $G_m^{(k)}(0)=k cdot k!$ (0&<=k&

$egin{align} G_m(z)=frac{z^{m-1}}{(1-z)^2 exp left{ 2sum_{k=1}^{m-1}z^k / k ight} } left ( c+int left ( frac{sum_{k=0}^{m-1}k z^k }{z^{m-1}} ight )$

式子裡面的那個積分不好處理，我這兒就粗糙地假設存在一個在|z|&<=1上解析的函數 $f_m(z)$ ，使得 $f_m(z)/z^{m-1}$ 等於該積分了-_-。為了要確定常數c，我們需要對G求m-1階導數

$egin{align} (m-1)!(m-1) = G_m^{(m-1)}(0) \ = sum_{k=0}^{m-1} inom{m-1}{k} left ( frac{1}{(1-z)^2 exp left{ 2sum_{k=1}^{m-1}z^k / k ight} } ight ) ^{(k)} left ( c z^{m-1} +f_m(z) ight ) ^{(m-1-k)}Bigg |_{z=0} \ = frac{left ( c z^{m-1} +f_m(z) ight ) ^{(m-1)}}{(1-z)^2 exp left{ 2sum_{k=1}^{m-1}z^k / k ight} } Bigg |_{z=0} \ = frac{ (m-1)!c +f_m^{(m-1)} (z) }{(1-z)^2 exp left{ 2sum_{k=1}^{m-1}z^k / k ight} } Bigg |_{z=0} \ = (m-1)!c+ f_m^{(m-1)} (0) end{align}$

上式中的第三個等號是由於 $1 / (1-z)^2 e^{2sum_{k=1}^{m-1}z^k / k}$ 的k(1&

$c=m-1-frac{f_m^{(m-1)}(0)}{(m-1)!}$

接著，我們希望從Gm(z)的表達式得到s(n,m)的漸進近似，這需要一點奇點分析（singularity analysis）的技術。我們繼續假設Gm(z)中除了1/(1-z)^2，其餘部分在|z|&<=1上解析。而1/(1-z)^2有一個二階極性奇點z=1，這對應於漸進近似表達式中的n+1項，其餘的函數解析的部分用奇點z=1帶入即可。那麼s(n,m)的漸進近似應該是

$egin{align} s(n,m) equiv left [ z^n ight ]G_m(z) sim frac{cz^{m-1} + f_m(z)}{exp left{ 2sum_{k=1}^{m-1}z^k / k ight} } Bigg |_{z=1} (n+1) \ = frac{m-1+f_m(1) -f_m^{(m-1)}(0)/(m-1)!}{e^{2H_{m-1}}} (n+1) end{align}$ .

其中Hn是調和數， $H_n= sum_{k=1}^{n} 1/k$ 。得到了s(n,m)的近似就可以去估計一維的極限值了，算一下極限 1-lim s(n,m)/n 就行，對二維的估計就是這個極限的平方。

特別地，當m=2時，f2(z)=0，s(n,2) 漸進近似於 (n+1)/e^2，對二維的情況下覆蓋率極限的估計是 (1-1/e^2)^2 約為 0.7476450724155088（這個極限值應該是 @醬紫君最先得到的）；

當m=3時，在 Wolframalpha 的幫助下，我們解出了f3(z)

$f_3(z)=z e^{2z+z^2}- frac{3 sqrt {pi}}{2e} z^2 ext{erfi} (1+z)$ ,

這裡erfi是虛誤差函數，其表達是

$ext{erfi} (z) = frac {2} {i sqrt{pi}} int _{0} ^{iz}e^{-t^2}dt$ .

然後，同樣的計算出s(n,3)的漸進近似

$egin{align} s(n,3) sim left ( 1 - frac{3 sqrt{pi}}{2e^4} left ( ext{erfi}(2) - ext{erfi}(1) ight ) ight ) (n+1) \ approx 0.176347036822661663n end{align}$ ,

對應估計二維的情況下覆蓋率的極限是 $frac{9 pi}{4e^8} left ( ext{erfi}(2) - ext{erfi}(1) ight )^2$ 約為 0.6784042037508；

當m=4時，Wolframalpha 也罷工了，看來這個積分確實有些棘手-_-。

當然，我們可以直接用遞推式求出任意項的值，但是收斂速度沒有保證，也不知道具體會收斂到哪裡。這裡其實給出了一個計算具體收斂值的方法，但是前提是要能數值計算那個複雜的積分。

這個問題可以轉化為卡普的21個NP-complete問題中的 獨立集合問題 / 極大團問題 的一種特殊情況。

這個子問題有可能是NP-hard的。也就是說，除非把所有可能的放置方案枚舉一遍，有可能不能在多項式時間內得到期望。但也有可能是P的，可以根據其特殊結構得到解析解。

（感謝評論區解釋）

————————————

也以題主的圖為例，其實我們不需要考慮小格子中的每個方格，因為一旦位置確定了，是否與其他小格子衝突也就確定了。不失一般性，考慮小格子中最左上角的方格。

如圖所示，在 n×n (13×13) 的格子區域中放置 m×m (3×3) 的小格子，

相當於在 (n-m+1)×(n-m+1) (11×11) 的格子區域中選擇一些點，使其「互不衝突」。

選擇的順序其實並不重要。我們想要知道選擇k個點有多少種方法。

————————————

而這個「互不衝突」其實也是很好定義的。如圖所示。

當我們選中一個點時，則上下左右距離為 m (3) 的點均不可選為小格子的左上角的點。

這樣，我們就構造了一個包含 (n-m+1)×(n-m+1) 個頂點的圖。每個頂點與上述範圍內除了自己的所有頂點相連。我們的任務是在這個圖中找到一些點的集合，使得集合中的任意兩頂點互不相連。此外，對應於「直至無法放置」的條件，我們希望這個集合是「極大」的，即無法添加任何頂點使其不與集合中的任一頂點相連。

並且我們想知道包含k個點的集合有多少。

————————————

熟悉圖論的朋友估計已經看出來了，這就是 極大獨立頂點集合 (Maximal Independent Vertex Set)，給定任意圖求大小為k的極大獨立頂點集合的數量是NP-complete的。

(credit: Independent Vertex Set -- from Wolfram MathWorld)

如果沒聽說過這個，可能更熟悉另一個等價的問題，稱為 極大團 (Maximal Clique)：在圖中找到極大完全子圖。如果我們對原來的圖取補圖 (graph complement)，邊由表示「相斥」變為表示「相容」。則我們希望得到大小為k的完全子圖——團 (clique) 的數量。這是卡普總結的21個極其難解的NP-complete問題中的一個。

求極大團有 Bron-Kerbosch 演算法，雖然不用枚舉所有子圖，但在最差情況下仍然是 $O(3^{frac{n}{3}})$ 的指數級時間複雜度。

此外，上述鏈接中提到了Mathematica中有求極大獨立頂點集合的函數：

A maximal independent vertex set of a graph can be computed in the Wolfram Language using FindIndependentVertexSet[g, Infinity], and all maximal independent vertex sets can be computed using FindIndependentVertexSet[g, Infinity, All].

@醬紫君是否有興趣構造幾個簡單的圖求一下精確解？

特別地，2×2的情況相當於一種特殊的已經被命名的圖，國王圖 (King Graph)，其名稱來源於國際象棋中國王可以移動的方向。

(credit: King Graph -- from Wolfram MathWorld)

似乎 GraphData[{"King", {n-1,n-1}}] 就可以了。

（評論區給出了結果）

————————————

雖然這個問題看上去很困難，但我只是說 很有可能 除了枚舉沒有別的辦法了。上述獨立集合/極大團問題是針對任意圖的。對於某幾類特殊的圖，團的數量是有解析解的。

況且上述圖結構良好，具有對稱性，局部稠密全局稀疏，不排除針對這種圖存在解析解的可能。若得到大小為k的獨立集合/極大團的公式，剩下的就是簡單的四則運算求平均了。

拋磚引玉一下:

我們來模擬這個過程

要是每拋一次都要對之前拋的所有物體判定的話程序效率一定是極低的

我們可以採用非法區標記的方式:

首先開一個表,然後取隨機數

考慮左上角,紅色的是物塊,X表示非法區...

然後迭代的時候只要從合法區取隨機數就行了

迭代到空表為止,迭代長度就是解.

選擇24×24的大方格為例(因為24因數多,我覺得可能存在相變)

GridsSelect[n_,m_]:=Block[{M=ConstantArray[0,{n-m+1,n-m+1}],drop,points,p}, drop[{x_,y_}]:=M[[Max[x-m+1,1];;Min[x+m-1,n-m+1], Max[y-m+1,1];;Min[y+m-1,n-m+1]]]=1; points=Position[M,0];p={}; While[points!={}, AppendTo[p,RandomChoice@Position[M,0]]; drop[Last@p]; points=Position[M,0]]; Association[{"Points"-&>p,"Area"-&>1.-Length[p]m^2/n^2}]];

try[n_,m_]:=Mean[(GridsSelect[n,#]/@ConstantArray[m,100])[[All,"Area"]]] try[n_,1]:=1; AbsoluteTiming[data=Table[N@try[24,i],{i,1,24}]] ListLinePlot[data,PlotTheme-&>"Detailed",LabelingFunction-&>(#1 )]

其實後半部分跑都不用跑的,反正只能放一個.

10那邊一個小坡,挺有趣的...

縱向對比,n×n上選取2×2方塊,似乎趨於一個常數...

越來越有趣了...這個極限應該是可以算出來的...

該問題應該可以等價於：

「二位空間中基於切比雪夫距離的球最密堆積問題」

該問題是作為Kepler猜想的推論之一。

對於這一系列問題，Gauss曾經猜測，等距球最密堆積密度上限為 $frac{pi}{3sqrt{2}} approx 0.74$ 。

Hales已證明，Gauss的猜測是正確的。參見https://arxiv.org/pdf/1603.06518.pdf

試著做了一下一維的情況。令s=n/m，根據相似性可知所求期望只是s的函數，記為f(s)，然後根據遞歸可以得到微分方程，可解，是分段可微的，一些關鍵點的值如下f(0)=0,f(1)=f(2)=1,f(3)=2,f(4)=2.675

過程的話大家有興趣再寫吧，實在受不了知乎的編輯器。。

兩維的難點在於在於複雜的拓撲結構，很難判斷在一個多孔的區域內，還有多少「面積」能放下一個新的方形，從而導致整個遞歸式幾乎不可計算。不過至少可以放下(n/2m)^2個

單純覺得這種問題如果上下左右考慮為互聯的，結果極有可能應該會比上下左右都是牆要優美些【可以考慮先做這種情況

這是個很好的問題。據我所知，如果將每個用戶視為一個sensor（感測器/集合元素/網路用戶），學術上與這個問題相近的問題有sensor placement，集合覆蓋問題，影響力最大化問題等等，只不過樓主的約束中更要求sensor之間不能重複或者相互覆蓋，只是在目標函數之餘加了約束條件而已。

這類問題是NP-hard，沒有最優解，只能獲得一個還可以的次優解。有論文已經證明，針對這類問題，貪心演算法能夠保證至少最優解（1-1/e）的精度，已經能夠滿足要求。具體求解演算法都是基於貪心演算法，後續論文都是如何改進計算效率。當時，不同目標函數也會導致不同演算法設計，大都是這樣。

另一種則是基於啟發式演算法，如遺傳演算法，這種是為了改善貪心演算法局部優化的問題，但還是不能得到全局最優解。

先就這樣，有人看的話還可以再細說。

手機碼字真是不容易π_π

我先說點自己的初步想法和思路。如果小格子的大小m為1的話，無論n為多少，期望比例應該是100%。

若m&<=n&<2m，則放置一個小格子之後便無法再繼續放置，此時比例應該是m^2/n^2

若n=2m，則若第一次隨機到四個邊角的任意區域，則此後佔據比例應為100%，若隨機到非四個邊角的區域，則只能放置一個小格子，則佔據比例為m^2/n^2。可放置總選擇數為(n-m+1)^2。則第一種情況的概率為4/(n-m+1)^2，第二種情況為1-4/(n-m+1)^2.則佔據面積比例期望為1*4/(n-m+1)^2+(m^2/n^2)*(1-4/(n-m+1)^2)

若n&>2m，情況就開始複雜了，繼續思考

補充@maigo的答案，並結合實際直接給結論：

1.明顯k＝m÷n一定時概率基本相同。2.考慮題主題設條件，海灘普遍並排能放下至少10個帳篷。

故：概率大於0.6，在k遠大於100（海灘相對無限大）時概率約收斂與0.74

能模擬就直接暴力跑蒙特卡洛。

錯的別看了，抱歉

以下原答案

mark

不錯的想法

想出來再寫

//一維是顯然的,直接dp就好了

----------------我是分割線--------------------

好像直接期望線性性直接上就好了吧,直接考慮每個m*m的格子分別算貢獻,就可以避免考慮很多東西了

有人贊就詳細寫寫(不保證我想法沒問題)

----------------我是分割線--------------------

有人贊了,詳細寫一下

原問題是等價於這樣一個問題的:

有(n-m+1)^2個可行的位置,把這麼多個位置隨機排成一個排列,某個位置產生1的貢獻當且僅當會和這個位置的產生矛盾的位置們都在排列中這個位置的後面

單獨考慮在(n-m+1)^2的每個位置,計算出和它矛盾的位置的數量x,這個位置的貢獻就是S/(x+1)

最後求和就好了

複雜度O(n^2),可能還能式子拆拆優化一維

先說一下結論：

當n=13，m=3時，填充比例在62％左右。(隨機模擬1000次結果)

模擬計算方法：

工具：MATLAB，方法：按題主所述規則編寫程序即可，在此簡述一下(用01矩陣，填充前判斷，可填充就隨機填充，直至不可填充，統計這一過程填充個數；重複1000遍，計算出填充比)。具體程序不方便附上。

n*n的格子區域，隨機向其中放置m*m的小格子，m小於n，直至無法放置，小格子佔據面積比例期望多少？

nn的格子區域，隨機向其中放置mm的小格子，m小於n，直至無法放置，小格子佔據面積比例期望多少？