電影院座位的選擇模型研究（電影院今天復工）

2023-06-16 15:00:12 1

曉查 編譯整理量子位 報導 | 公眾號 QbitAI

今天，國內電影院在停業將近半年後終於復工了。為了保持合理的隔離距離，國家電影局規定每場電影的上座率不得超過30%。

那麼問題來了：

如果有一間影廳要復工，在保持安全距離的情況下，如何才能儘可能多的安排觀影人群？

這個問題，在當初辦公室復工的時候也同樣適用。

我們先來把這個問題轉化成一個幾何問題：

把每個人所在的位置看做圓心，隔離距離的一半（也就是3英尺）為半徑畫圓。怎樣才能讓這些圓排列得最密。

這個問題在現實中似乎有個最佳答案，我們可以買來一箱汽水，看看廠商怎麼排列一罐罐圓形的汽水的。

上面可樂罐的這種排列方法叫做「正方形堆積」，因為將每個圓的圓心連接起來是正方形。

我們來算算這種飲料包裝究竟能佔據多少比例的空間。

假設上圖中圓的半徑是r，那么正方形的邊長就是2r。圓的面積是πr2，正方形的面積是(2r)2。

那麼這種排列方法所佔的面積比例為：

也就是說平面有78.54%的面積被圓覆蓋，這是正方形堆積的密度。難道這就是效率最高的排列方式了嗎？

不難發現，其實還有一種排得更緊密的方法，將一排的可樂滑動到另一排的縫隙中，這種排列方式被叫做「六角堆積」。

這樣圓之間的縫隙更小，排列的密度也更高了。實際情況怎樣，我們來算算。

每個六角形內都是有1個整圓和6個1/3圓，所以相當於有3個整圓。

假設圓的半徑是r，六邊形邊長是s=2r，根據六邊形面積計算公式：

而一個六邊形內共有3個整圓，所以圓佔據的面積是：

可以看到，填充率一下子提升到了90.69%，六角比正方形排列的效率更高。實際上也沒有其他方法比六角排列的填充率更高了。

但這個顯而易見的結論要獲得嚴格的數學證明卻非易事，包括拉格朗日、高斯等數學大神為之付出大量努力，直到1940年代，這個問題才得到嚴格證明。

既然六角排列的效率更高，為何飲料要採用正方形排列？那是因為飲料外包裝箱一般是方形，如果用六角排列，反而無法照顧到邊角。

倘若邊角佔據的面積較小，那麼90.69%相比78.54%帶來的提升還是能把邊角浪費的空間彌補回來。

到了三維空間，情況更為複雜。如何讓球體排列的密度更高，需要一層一層來。

第一層，我們用六角堆積的方式佔據儘可能多的空間：

每3個球體之間都有1個孔隙，按照二維空間的方式，把第二層球體插入到孔隙中。但是我們不可能把每個孔隙都放上球體，因為相鄰孔隙之間的距離小於球體的直徑，我們只能間隔插入。就像下面這樣：

接下來第三層怎麼排列，有兩種選擇：

一種方式是堆積六角堆積（HCP），就是填補如下的孔洞：

這樣就相當於第三層球位置與第一層一樣。從上面俯看下去，第一層和第三層重合，也就是ABABAB……的排列方式。

另一種是面心立方（FCC），填充以下位置：

從上面俯看下去，一二三層互不重合，也就是ABCABC……的排列方式。

如果你小時候壘過玻璃球，那麼一般都會壘成面心立方。

巧合的是，兩種排列方式佔據的空間比例都是

雖然填充空間的比例一樣，但這在物理和化學中卻是兩種完全不同的排列方式。

如果把球體看做是原子，那麼怎麼排列就決定了這種物質的晶體結構，也會影響其物理化學性質。

六角堆積和面心立方是不是三維空間中最密集的堆積方式呢？

早在1611年，著名天文學家克卜勒就提出了這種猜想，但是直到1998年，才由數學家託馬斯·黑爾斯（Thomas Hales）提供完整的證明。

至此，2維、3維的情況都已經完全解決，但是在維度更高的空間裡，哪種方式的排列密度最高，數學家們一直沒有解決，即使只是到4維。

直到2016年傳來了一個好消息，8維和24維空間的最密堆積問題已經被一位烏克蘭女數學家Maryna Viazovska證明。

為何偏偏是這兩種維數？因為隨著維度的增加，n維球與它的外切立方體的體積之比也越來越小。這一點有個直觀的理解方法：

n維立方體有2^n個角，而邊角是球體填充不到的地方，邊角數會隨著維度增加，所以球體填充率降低也在意料之中。

8維和24維中的球體收縮得恰到好處，讓球體之間的的孔隙正好能被另一相同同半徑球體填充，從而獲得了一種特殊的超密堆積。

現在科學家已經解決了1、2、3、8、24維的最密堆積情況，還有更多的維度等著他們去探索。

參考連結：https://www.quantamagazine.org/the-math-of-social-distancing-is-a-lesson-in-geometry-20200713/

— 完 —

量子位 QbitAI · 頭條號籤約

關注我們，第一時間獲知前沿科技動態