當前位置:星座運勢大全官網 - 周易占卜 - 三個極端自私的人分享壹塊蛋糕。什麽策略能讓三個人都覺得公平?

三個極端自私的人分享壹塊蛋糕。什麽策略能讓三個人都覺得公平?

這就是著名的切蛋糕問題。公平分配

所謂“三人滿意”在數學上有很多可能的含義,常用的兩個是:

公平:三個人都認為自己的份額不低於1/3。

沒有抱怨:他們都不覺得別人比自己更沒有嫉妒。

不投訴壹定是公平的,但公平不壹定是不投訴。

大牛的回答,以上兩個條件不滿足,只會導致自責,不滿意/不公平,和錯誤。

他們的情況很簡單:我切,妳選。

三個人的情況很久都沒有解決。1940年代找到了公正的程序,1980年代公布了無申訴程序。

很多人投訴無門的切法壹直沒有圓滿解決。

大牛的回答是“動刀程序”。參見Stromquist動刀程序,由Stromquist於80年代提出。

需要壹個裁判,從左往右走,三個人拿著刀站在裁判的右邊,保持右邊平分蛋糕的位置(按照自己的標準)。壹旦三個人中有壹個人喊“停”,這個人就得到了裁判左邊的蛋糕。然後三個人中間的那個(b)把刀砍了。兩個沒有蛋糕的人,靠近裁判的拿中間壹塊,遠的拿右邊壹塊。

很容易證明,三個人都認為自己的份額最大。

feed程序的缺點是連續性,假設兩個人同時停下來的概率為零,假設蛋糕是無限可分的,現實中不容易操作。

離散程序由塞爾弗裏奇在20世紀60年代提出,90年代由康威獨立提出並發表。

a根據自己的標準把蛋糕切成三塊。

如果B認為最大的兩塊壹樣大,那就按照C、B、A的順序選蛋糕,完成。

如果B認為M最大,他就從M上切下壹小塊R,使之和第二大塊壹樣大,把R放在壹邊。

c先選。如果C不選M,那麽B壹定選M,否則壹切正常,A拿最後壹塊。

在B和C中沒有得到M的壹方把R分成三份,讓在B和C中得到M的壹方先選壹份,然後A選壹份,把最後壹份留給自己。結束。

可以證明三個人都認為自己的份額最大,證明可以在維基頁面找到。

四人無抱怨分段方案是由Brams,Taylor和Zwicker在1997中提出的。多人無訴分割的離散程序是由Brams和Taylor在1995中提出的,但需要切割的次數可能是無限的,所以應該說還沒有得到滿意的解決。

以上是“不抱怨”的切法。“公平”的切割更簡單。這裏有壹個非常通俗的介紹:數學在歐洲,波蘭數學家做出了巨大的貢獻。n人的壹般公平程序如下(由巴拿赫和克納斯特提出):

先把它整理好。

第壹個人剪下他認為是1/n的東西。

按順序,大家判斷這個是不是太大了。如果是,切掉壹點,替換原來的蛋糕,如果不是,跳過。

大家評完之後,這壹塊就給最後切蛋糕的人;如果沒人剝蛋糕,這塊就給第壹個人。

重復2-4直到只剩下兩個人,由我切妳的方式決定。

n=3的簡化程序是施泰因豪斯在1943中提出的。@ Park III的答案是施泰因豪斯方案的過於簡化版本,這是錯誤的。問題是A先選,B選第二。如果B選擇了A認為不是最少的杯子,那麽整個過程就是不公平的。

= = = =補充= = = =

為什麽公平不壹定沒有怨恨?這當然是建立在數學定義上的,它的表述已經指出了這種邏輯關系。

這兩個概念的現實意義是因為同壹塊蛋糕對每個人來說有不同的價值。

例如,下面是壹個誇張的例子:

想象壹個不同口味的蛋糕,比如巧克力、奶油、草莓等。分享蛋糕的人口味不同,所以給不同的部分賦予不同的價值。幾何上簡單的平均分配解決不了這裏的問題,公平分配也未必盡如人意。這是這道數學題要解決的問題。

也正是在這個意義上,很多人堅持“先斬後奏”,無論是@王成的五字超簡版,還是@陳啟航的多余“嚴謹”版,都是錯誤的。前者連完整的算法都沒有。第壹個切的人會盡量按照自己的標準平分,但這不壹定是另外兩個的標準,這可能會導致另外兩個之間的不公平。

比如A-B削減C-B-A選擇的“策略”,下面是不公平的情況:

a切1/3和2/3按大小分,但在BC看來,因為小塊的巧克力多,所以價值分別是3/7和4/7。這時候B的最佳策略是切掉自以為的3/7,3/7,1/7。c也有同樣的眼光,但是在A看來,分別是1/3,1/2,1/6,第二塊更大,但是巧克力不多。如果按照C-B-A的順序選擇,那麽A在他眼裏只能得到1/6,在BC眼裏只能得到1/7。