多個圓的最小外切三角形-1

問題

看到一個很有意思的問題:

把面積分別為 1, 2, 3, …, 99, 100 的 100 個圓平鋪在一個三角形裡, 這個三角形至少有多大?

然後我瞬間聯想到了這個:

天知道這是怎麼算出來的……

這個問題的本質大概就是尋找多個圓的最小外切三角形 (顯然必須相切, 不然就不能最小, 且每個圓也最好是相切的), 在網上查了一下, 沒發現什麼相關信息. 感覺很有趣, 那就稍微研究一下.

由於大小不同的圓過於複雜, 這裡先考慮大小相等的圓.

一個圓

先考慮一個圓的情況.

嚴格證明

一個圓的外切三角形面積最小值很好求, 設圓半徑為 $r$, 三角形三個角 $A,B,C$, 對邊分別為 $a,b,c$, 於是 $S=1/2\cdot r(a+b+c)$, 同時可以用 $r$ 和三個角表示三邊:

$$\begin{aligned} a=r\cot\frac{B}{2}+r\cot\frac{C}{2}\\ b=r\cot\frac{A}{2}+r\cot\frac{C}{2}\\ c=r\cot\frac{A}{2}+r\cot\frac{B}{2} \end{aligned}$$

所以 $S=r^2\left(\cot\frac{A}{2}+\cot\frac{B}{2}+\cot\frac{C}{2}\right)$, 余切函數在 $(0,\pi/2)$ 是凸函數, 直接用 Jensen 不等式就可以得到:

$$S_{min}=3r^2\cot\frac{A+B+C}{6}=3\sqrt{3}r^2$$

此時 $A=B=C$, 這是個等邊三角形.

幾何直觀

雖然使用 Jensen 不等式也很簡單, 但似乎不易推廣到多個圓的情況, 所以我想到了一種借助幾何直觀的方法.

當然這種方法很不嚴格, 只是投機取巧的做法罷了, 談不上證明.

如圖, 固定兩條切線 $AC$ 和 $AB$, 觀察第三條切線 $BC$, 不妨設 $CD>BD$. 作圓的切線 $MN$, 且切點為 $MN$ 中點, 作 $NE\parallel MB$.

顯然 $\triangle MDB\sim\triangle NDE$, 因為 $ND>MD$, 所以 $S_{\triangle MDB}<S_{\triangle NDE}$, 那麼 $S_{\triangle MDB}<S_{\triangle NDC}$, $S_{\triangle AMN}<S_{\triangle ABC}$, 可知 $\triangle AMN$ 面積最小. 由於對稱性, 三邊切點都是中點時面積最小, 此時外切三角形是等邊三角形.

兩個圓

分成兩種情況考慮: 一是一邊與兩個圓相切, 二是三邊都只與一個圓相切.
至於為什麼是兩種, 請顯然.

情形一

本來想直接建系算的, 但計算太複雜, 超出了我的能力范圍. (算出來大概也求不了最值)
那就故技重施, 取切點為中點的情況:

很容易就能看出此時三角形為等腰直角三角形, 面積 $S=(6+4\sqrt{2})r^2\approx11.657r^2$.

情形二

還是一樣的方法, 但計算繁瑣一些.

設底邊長為 $2x$, 根據勾股定理列方程:

$$\left(\sqrt{(3r)^2+x^2}+3r\right)^2+x^2=\left(2\sqrt{(3r)^2+x^2-r^2}\right)^2$$

解得 $x=\sqrt{\frac{1}{2}(3\sqrt{17}-5)}r$, 於是可以算出面積:

$$S=\frac{\sqrt{6\sqrt{17}-10}\cdot(\sqrt{17}+9)}{4}r^2\approx12.595r^2$$

比較

那麼就可以對比面積了, 顯然第一種情況面積更小一些. 於是得出結論: 兩個等大圓的最小外切三角形是等腰直角三角形, 面積最小值 $S=(6+4\sqrt{2})r^2$.
雖然不能嚴格證明, 但這確實是我找到的最小了.

還有一個問題是: 為什麼情形一比情形二面積小?
兩種情況都是等腰三角形, 可以從中間切開考慮, 得到兩個直角三角形都包含了一個圓, 情形二的空隙更大一些, 直覺上說就是這樣 (唉說了跟沒說一樣).

提出猜想1: 類似情形一的面積始終比類似情形二的小, 且兩情況的差距會隨圓個數的增加而增加.

這個猜想在後面其實沒什麼用處.

三個圓

這裡要分3種情況考慮:

1. 類似上述情形一,
2. 類似上述情形二,
3. 平面六角密堆積式排列, 外切等邊三角形.

從直覺來看, 顯然情形3是最小的, 且情形1小於情形2, 但我沒有什麼簡單的比較方法, 那就干脆全部算出來好了 (順便鍛煉計算能力).

情形一

直接建系如圖, 並設圓的半徑為 $1$.

設 $A$ 點坐標 $(0,a)$, $B$ 點 $(b,0)$, $AB$ 中點 $C$ 坐標 $(b/2,a/2)$, 可得 $AB$ 的解析式:

$$AB:y=-\frac{a}{b}x+a$$ $AB$ 與圓在 $C$ 點相切時, $OC\perp AB$, 由此可以算出 $OC$ 的解析式: $$OC:y=\frac{b}{a}x+\frac{a^2-b^2}{2a}$$

根據 “$OC$ 過 $O$ 點” 和 “$C$ 在圓 $O$ 上” 列出方程:

$$\begin{cases} 2\cdot\frac{b}{a}+\frac{a^2-b^2}{2a}=1\\ \left(\frac{1}{2}b-2\right)^2+\left(\frac{1}{2}a-1\right)^2=1 \end{cases}$$

整理一下就出現了喜聞樂見的一元四次方程:

$$x^4-12 x^3+49 x^2-80 x+48=0$$

這、完全不會解.

沒關係, 還有 Wolfram|Alpha, 輕松得到答案為:

$$b=\frac{1}{3} \left(\sqrt[3]{3 \sqrt{183}+62}+\sqrt[3]{62-3 \sqrt{183}}+8\right)\approx5.15276$$

繼續代回式子, 得到:

$$S=ab\approx18.727$$

所以 $S\approx18.727r^2$.

情形二

這種情況簡單許多, 和一個圓時類似, 設底邊為 $2x$, 根據勾股定理列方程 (圖都懶得畫了):

$$\left(\sqrt{(5r)^2+x^2}+5r\right)^2+x^2=\left(2\sqrt{(5r)^2+x^2-r^2}\right)^2$$

解得 $x=\sqrt{\frac{1}{2} \left(5 \sqrt{33}-21\right)}r$, 於是算出面積:

$$S=\frac{1}{2} \sqrt{\frac{1}{2} \left(5 \sqrt{33}-21\right)} \left(\sqrt{10 \sqrt{33}+58}+10\right)r^2\approx20.382r^2$$

情形三

看起來很好算, 實際上確實很好算. 如果建系死算大概會比較複雜, 但直接算高 $CF$ 就會輕松很多.

首先易知 $CD=r$, 然後由於 $\triangle OAB$ 是等邊三角形, $OD=\sqrt{3}r$, 由於 $\triangle OEF$ 是帶60°的直角三角形, $OF=2OE=2r$, 所以 $CF=3+\sqrt{3}$, 容易算出三角形面積:

$$S=(6+4\sqrt{3})r^2\approx12.928r^2$$

比較

到這裡, 差距就很明顯了, 情況三顯著小於情況一和二, 甚至與兩個圓的最小外切三角形面積相差無幾, 看來這的確是一種節省空間的排列方式. 因此對於較多的圓, 前兩種情況可以不用考慮了, 差距只會越來越大.

提出猜想2: 對於三角形數個圓, 最小外切三角形必然是類似情況三的等邊三角形.

可以總結出這類三角形的面積公式: 若圓的個數為 $k(k+1)/2$, 則可算出高為 $h=1+2+(k-1)\sqrt{3}=3+(k-1)\sqrt{3}$, 由此得到三角形面積

$$S=\sqrt{3}k^2+(6-2\sqrt{3})k+4\sqrt{3}-6$$

那麼需要特別考慮的就是非三角形數個圓的情況.

三角形數: 該數目個點或等大圓在等距情況下可排列成三角形, 對於相切的等大圓, 即可排列成等邊三角形的形狀.

前10個三角形數為: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55.

四、五、六

經過以上的探究, 總結出兩條經驗:

1. 若某條線段僅與一個圓相切, 盡量使切點在切線段的中點.
2. 盡量排列緊密, 最好以平面六角密堆積式排列.

接下來對四、五、六個圓的情況進行分析. 為方便起見, 接下來默認 $r=1$.

情形一

六個圓用平面六角密堆積式排列, 形成的外切三角形同時也可容納四個或五個圓:

這時候直接代公式就可以了, $k=3$,

$$\begin{aligned} S&=\sqrt{3}k^2+(6-2\sqrt{3})k+4\sqrt{3}-6\\ &=9\sqrt{3}+18-6\sqrt{3}+4\sqrt{3}-6\\ &=12+7\sqrt{3}\\ &\approx24.124 \end{aligned}$$

情形二

對於四個或五個圓, 還有另一種面積較小的情況如圖, 切點 $C$ 為 $AB$ 中點.

還是建系計算, 思路與前述相同.
設 $A(0,a)$, $B(b,0)$, 可以列出方程:

$$\begin{cases} \frac{b}{a}+\frac{a^2-b^2}{2a}=3\\ \left(\frac{1}{2}b-1\right)^2+\left(\frac{1}{2}a-3\right)^2=1 \end{cases}$$

根式解很複雜, 所以就直接寫近似結果了: $b\approx3.759$, $S\approx26.132>24.124$.

情形一在空缺兩位的情況下, 空間利用率仍比情況二高, 再一次展現了平面六角密堆積式的優越性. 事實上, 觀察情形二的圖可知情形一等價於下層兩圓移至兩邊, 可以在底不變甚至減小的情況下減小高, 如此能夠減小面積就不顯奇怪了.

情形三

當然, 情況一雖排列合理, 但終究空缺兩位, 對於四個圓, 很容易發現更小的外切三角形, 即圖中左下的直角三角形:

觀察圖形可只此直角三角形恰為10個圓的最小外切三角形的一半, 於是可以用前述方法先求大等邊三角形的面積, 除以2即為直角三角形面積:

$$\begin{aligned} S&=(\sqrt{3}n^2+(6-2\sqrt{3})n+4\sqrt{3}-6)/2\\ &=(16\sqrt{3}+24-8\sqrt{3}+4\sqrt{3}-6)/2\\ &=9+6\sqrt{3}\\ &\approx19.392 \end{aligned}$$

對於像 $4$ 這樣可以形成等邊三角形的一半的數, 不妨稱其為半三角形數. 半三角形數就是三角形數減去分割線通過的圓, 再除以 $2$. 容易得到半三角形數的通項公式:

$$a=\begin{cases} n^2/4, &n\text{ is even} \\ (n^2-1)/4, &n\text{ is odd} \end{cases}$$

此時突然發現 $6$ 也是半三角形數: $6=(5^2-1)/4$, 於是作出6個圓的外切直角三角形:

然後用和前面一樣的方法計算面積:

$$\begin{aligned} S&=(\sqrt{3}n^2+(6-2\sqrt{3})n+4\sqrt{3}-6)/2\\ &=(25\sqrt{3}+30-10\sqrt{3}+4\sqrt{3}-6)/2\\ &=12+9.5\sqrt{3}\\ &\approx28.454 \end{aligned}$$

明顯比上面的情形一大.

同時是三角形數和半三角形數的情況不多見, 可通過解方程 $n^2/4=k(k+1)/2$ 或 $(n^2-1)/4=k(k+1)/2$ 得到. $1000$ 以下共有如下幾組解 ($n$ 表示半三角形層數, $k$ 表示三角形層數, $c$ 表示對應圓的個數):

$$\begin{align*} n=2,k&=1,c=1\\ n=12,k&=8,c=36\\ n=70,k&=49,c=1225\\ n=408,k&=288,c=41616 \end{align*}$$

或:

$$\begin{align*} n=5,k&=3,c=6\\ n=29,k&=20,c=210\\ n=169,k&=119,c=7140\\ n=985,k&=696,c=242556 \end{align*}$$

除去相等的情況, 三角形數和半三角形數分布很不均勻. 兩個三角形數之間的半三角形數分布不均, 因此對於三角形數個圓, 不能確定究竟是其排成的直角三角形, 還是稍大於其的三角形數排成的等邊三角形面積更小.

例如, 4個圓排成的直角三角形面積小於6個圓排成的等邊三角形, 而9個圓排成的直角三角形面積 (約39.249) 大於10個圓排成的等邊三角形 (約38.785).

提出猜想3: 在猜想2的基礎上, 對於上述半三角形數個圓 (不等於某個三角形數), 最小外切三角形可能為等邊三角形的一半 (帶60°的直角三角形), 面積為: $$S=\frac{\sqrt{3}}{2}n^2+(3-\sqrt{3})n+2\sqrt{3}-3$$ 也可能為稍大於其的三角形數排成的等邊三角形, 面積為: $$S=\sqrt{3}k^2+(6-2\sqrt{3})k+4\sqrt{3}-6$$ 不需要考慮其他的情況.

What about 100？

雖然沒有得到一般的結論 (甚至特殊的結論也沒有證明), 但對這個問題大致了解並提出猜想後, 至少可以給出100個等大圓的外切三角形面積上界.

100恰是半三角形數, 於是根據猜想3, 只需算100個圓排成的直角三角形面積和105個圓排成的等邊三角形面積, 分別為:

$$S_1=\frac{\sqrt{3}}{2}n^2+(3-\sqrt{3})n+2\sqrt{3}-3=57+182\sqrt{3}\approx372.233$$ $$S_2=\sqrt{3}k^2+(6-2\sqrt{3})k+4\sqrt{3}-6=78+172\sqrt{3}\approx375.913$$

兩者相差不大, 最小面積大概是 $S_1=57+182\sqrt{3}\approx372.233$.

不等大的情況

不等大的情況比等大的複雜很多, 關鍵在於圓與圓相切的方式更多樣, 需要考慮的情況多得多. 需要注意的是不能太高估空隙的容納能力, 本來我以為大圓相切產生的空隙足夠將小圓全部容納其內, 結果發現面積為100, 99, 98的三個圓相切產生的空隙僅能容納面積大約為2.369的小圓, 面積為100, 99, 98, 97的四個圓相切產生的空隙也只能至多容納面積大約為16.7的圓.

對於這個問題我還完全沒有思路, 還得留到以後解決. 我覺得解析方法是不可能的, 最終只能使用數值方法, 那就需要一些編程技巧了.