Re: [討論] 精華區中Solomon分寶藏問題

作者: tihsllub (no man's land)   2017-02-10 00:59:09
回一個超久以前的文。
好像可以找到把寶藏分給三個人,而且大家都覺得公平的方法。
此方法與三人選擇寶藏的先後次序無關。假設有A、B、C三人。
第一步:
請A將寶藏分成自認為公平的三等分:a1、a2、a3。
第二步:
請B將三份寶藏中,自認為最少的一分放在一旁,在不失一般性下假設a1最少。
然後請B把a2、a3混和後,再分成自認為公平的兩等分:b2、b3。
此時,共分成有三份寶藏:a1、b2、b3。
a1:A自認為是公平的1/3
b2、b3:B自認為這兩堆一樣多,都是大於等於公平的1/3
第三步:
請C任選一堆寶藏。對於C來說,他可以任選自認為最多的那一堆。
第四步:
若C選b2或b3,則A拿a1,B拿b3或b2。
若C選a1,則換A從b2或b3選A自認為比較多的那一分,B拿剩下的。
以上是充分發揮solomon分寶藏給兩個人的精神設計出來的方法。
若要分給三個人以上,則狀況就很複雜了,可能要請版友們指導一下。
作者: noodleT (麵T)   2017-02-12 00:17:00
作者: tihsllub (no man's land)   2017-02-13 01:59:00
謝謝n大。連結中的第一種分法感覺不是很公平,假設是在沙漠中ABC三人要分水,AB兩人串通,要犧牲A來救B,讓B分到最多水。則A可先把水分成極少、極多兩分。A選極少、B選極多那份。AB兩人再把自己的水分成公平的三等分,讓C從中各選一分。則C雖然可以得到約1/3的水,但B永遠可以得到最多的水。連結中「最後削減人算法」真的是一個分給n個人的好辦法

Links booklink

Contact Us: admin [ a t ] ucptt.com