http://www.matrix67.com/blog/archives/3944對(duì)問題有細(xì)致的分析，可能解決各位的一些疑惑，如果進(jìn)不去可以試試這個(gè)，https://site.douban.com/151509/widget/notes/7799594/note/225303961/ 。

※不建議碳基生物看下面這段廢話！

????????好像在上輩子的300歲生日宴上，俺和幾位大佬打算分一個(gè)像像蛋糕一樣大的蛋糕一樣大的蛋糕，那個(gè)蛋糕像蛋糕一樣大，一樣圓，分完蛋糕后，有幾位大佬覺得自己分到的蛋糕比別人少，于是要求重新分，俺們只好用膠水把蛋糕合起來重新分，結(jié)果還是不行，看著逐漸變成“α－氰基丙烯酸乙酯—反式脂肪酸混合物”/502的蛋糕，大佬們陷入了沉思，怎樣分蛋糕才能讓所有人都滿意。俺因?yàn)橄氩怀龆y過的要死，睡覺經(jīng)驗(yàn)豐富的俺還是因?yàn)槭?，最后在稿紙的海洋中掛了。還好在我-1歲時(shí)，因DNA突變使我有“會(huì)解決公平分割問題”的性狀，但也有“語言功能障礙”性狀，所以在我學(xué)會(huì)說話寫字后，我才能展示我解決公平分割問題的能力，可惜已經(jīng)有數(shù)學(xué)家把它解決了，那我直接展示這些公平分割方案好了。

????????在政治（？）學(xué)科中，有這樣的選擇題↓

????????于是，兩個(gè)人的分法自然就知道了↓

????????切蛋糕的人必須公平分割，不然有可能……

????????把分割權(quán)和選擇權(quán)分散，是實(shí)現(xiàn)公平的前提。

????????如果分蛋糕的人數(shù)不止兩個(gè)，那怎么辦？

????????其實(shí)只要改進(jìn)二人分配原則就行↓

????????還有一種方法——最后消減者。

? ? ? ? Wikipedia上還有一個(gè)辦法（有爭議）→單一分配者：三人時(shí)適用，由一人分配，剩下的人依次選擇。若他們的選擇不同，那么分配者再取得最后一份，分配結(jié)束。如果選擇了同一份，那么分配者在未被選擇的兩份中隨機(jī)選取一份，再讓兩名選擇者按分配—選擇者方案對(duì)剩下兩份重新選擇。

????????但這個(gè)方法在理論上有缺陷，因?yàn)樗玫搅恕半S機(jī)選取”來顯現(xiàn)公平性。如果我們?cè)试S用隨機(jī)分配來解這個(gè)命題，則答案可以簡化為“由一人分配，隨機(jī)分給三人；為了不讓自己拿到價(jià)值最差的一份，分配者必會(huì)完全公平?！比绱艘粊韯t失去了意義。

????????可否把“隨機(jī)”拿掉？改為由分配者自行選擇一份？答案是不行的。假設(shè)資源價(jià)值是12，分配者分成{1,5,6}三份。兩位選擇者都很理性地選擇了6那一份，而分配者就可以自行選取5那一份，大于他應(yīng)得的4(=12*1/3)。因此可知單一分配者無法解決本命題。（設(shè)計(jì)方案時(shí)需考慮貪得無厭的參與者們的各種心思，避免bug）

END

是不可能的，如果所有人眼中的蛋糕是同一個(gè)蛋糕，那么只要平均分蛋糕就行，但現(xiàn)實(shí)是每個(gè)人眼中的蛋糕可能不一樣，他們自己必須分到他們眼中的1/n的蛋糕（甚至更多），其實(shí)上文已經(jīng)暗示了這一點(diǎn)，而且上述方法是有效的。

END

都沒有？如果真的是這樣，那為啥貪官會(huì)互相舉報(bào)？雖然他們分到了到他們眼中的1/n的“蛋糕”（甚至更多），但如果有人覺得別人分到的比自己更多，產(chǎn)生了嫉妒，就可能會(huì)舉報(bào)，所以想出在任何情況下無嫉妒的分割方案是解決公平分割問題的關(guān)鍵。（分完蛋糕時(shí)，如果一個(gè)人不會(huì)嫉妒別人，那這個(gè)人一定分到了1/n及以上的蛋糕）

????????所以，“單一選擇者”和“最后消減者”方法就不適用了，而“分配者-選擇者”仍然適用（上面的GIF可以解釋這一點(diǎn)），而這只是二人分配原則，如果不只有兩個(gè)人分蛋糕，那就要用其他方法了。

https://cacm.acm.org/magazines/2020/4/243651-a-bounded-and-envy-free-cake-cutting-algorithm/fulltext

1960 年， John Selfridge 和 John Conway 各自獨(dú)立地分析了人數(shù)為 3 的情況，構(gòu)造出了第一個(gè)滿足免嫉妒條件的三人分割方案。這種分割方案就被稱為“Selfridge-Conway 算法”。(from.Matrix67)

? ? ? ? 如果用分割整個(gè)蛋糕的方法分割消減下來的蛋糕，那這個(gè)蛋糕可能完全分不完。利用第一輪分配時(shí)得到的“A不會(huì)嫉妒X”信息，可以解決這個(gè)問題，利用信息是解決多人的公平分割問題的關(guān)鍵。

? ? ? ? 那n=4時(shí)該怎么解決呢？我在自修課上想了幾個(gè)小時(shí)也沒想出來（小孩和不懂事的大人建議別模仿），可能是我的DNA出問題了，我打算讓A分割，BCD同時(shí)選，對(duì)于一些情況，可以Selfridge-Conway算法解決，但如果BCD選同一塊，就可能要對(duì)兩塊進(jìn)行消減。而分割消減下來的蛋糕時(shí)，兩個(gè)選了消減蛋糕的人順序難以決定，而且A此時(shí)只能對(duì)兩人中的一人（這時(shí)分割的消減下來的蛋糕對(duì)應(yīng)的A分割的蛋糕的另一部分蛋糕的選擇者）消除嫉妒，所以這個(gè)問題確實(shí)很難，難倒了數(shù)學(xué)家們幾十年。

????????2016年，Aziz和Mackenzie想出了n=4時(shí)的分割方案→?http://de.arxiv.org/pdf/1508.05143v2?

????????直接看這些圖也是可以的↓

????????這篇paper作者在此基礎(chǔ)上得到了任意人數(shù)的分割方法。易得，該方法步驟數(shù)基本上低于.

????????可以在這找到分割方案，相應(yīng)的證明，以及執(zhí)行次數(shù)的計(jì)算過程?https://arxiv.org/pdf/1604.03655.pdf?.

????????這個(gè)分配過程大概是這樣的↓

? ? ? ? 這個(gè)方法相對(duì)于“移動(dòng)刀法”（荷官移動(dòng)刀，對(duì)刀經(jīng)過的部分滿意的玩家喊“?！?，分到切下來的蛋糕中刀經(jīng)過的部分）更容易實(shí)現(xiàn)，因?yàn)檫@是個(gè)離散有限步數(shù)的分割方案，分到是能分……不過這樣分完之后一堆人只能拿著一堆碎片離開。所以俺期待各位大佬們能提出更好的方案，因?yàn)檫@不只是數(shù)學(xué)家的腦力游戲，還可能是解決政治爭端的關(guān)鍵（？）。

1. ? ? ? ? 有一說一，上述的papers實(shí)在是太艱深晦澀了。不過我們可以思考下它的變體問題：如何公平且無嫉妒地分配“負(fù)面資源”（例如罰款），即分配完畢后，每個(gè)人都覺得自己罰的最少（對(duì)于最簡單的情況，把“最后消減者”改成“最后添加者”是可行的）？各位可以給出你們的方案。我的方法和Selfridge-Conway算法差不多，但又不是完全一樣。因?yàn)?，?dāng)BC選擇同一塊且B認(rèn)為這一塊最小時(shí)，B不應(yīng)該進(jìn)行消減，而是“借”一塊，使最小的兩塊一樣大。最后把它“還”回去，讓"Y"把借的這塊切成三份，最后按"X,A,Y"的順序“還”，關(guān)鍵是這一步實(shí)在是難以實(shí)現(xiàn)，因?yàn)闆]有一個(gè)公正的裁判判斷“還”的量。

? ? ? ? 當(dāng)然這些只是理論的分析，認(rèn)為蛋糕是一個(gè)長條，而且只能從最左邊消減?！皩?shí)際”情況是……

? ? ? ? 在這種情況下，分割者很難把蛋糕切成相等的兩塊，就是說用平面把圓柱平分。其實(shí)也沒有這么難，只要在側(cè)視圖中把蛋糕沿對(duì)角線切開就行，即平面同時(shí)經(jīng)過圓柱的上沿和下沿。如果可以平移蛋糕的話，還會(huì)有其他方法。

? ? ? ? 最后出幾道思考題：（下次公布答案）

1. 用圓規(guī)切圓形蛋糕

2. 用圓規(guī)切正方形蛋糕

3. 學(xué)會(huì)公平分割問題的解決算法(Doge)