討論為主, 把分金沙先答案附上。

來源: guest007 2010-08-20 23:13:19 [] [舊帖] [給我悄悄話] 本文已被閱讀: 次 (3295 bytes)
三人分金沙, 如何公平 答案有些長, 需要有耐心,稍微明白人應該可以讀懂, 值得一讀. 不一定人人拍案驚奇,但其 嚴密性是山寨解無法比擬的。

原文自wiki, 隨便很多網站也有解釋. 自1961年此解後,有若幹書和 論文優化探討證明(envy-free division) . 三人解法現有10多種了, 四人隻能有 moving knife 的解 法. 若幹教授專業於此領域.

英文不好,打字又慢, 大概翻譯一下主要步驟. 請以原文為主. 找茬的亂棒打出, 自己去獨英文部分好了.
-------
把三個人叫p1 p2 p3 . 準備好… 開始…!
(1步: P1 切蛋糕為三份)
1- P1 divides the cake into three pieces he considers of equal size. Let's call A the largest piece according to P2.
(2 步: P2 將三份中 p2 認為大的一份(A) 切下一點, 使得被切後的 A和第二大的那塊相同(當然這是對於P2認為的來說的). 切下的叫A2, 悲切後的A叫 A1.
2- P2 cuts off a bit of A to make it the same size as the second largest. Now A is divided into: the trimmed piece A1 and the trimmings A2. Leave the trimmings A2 to one side.
(3, 4, 5, 6 步, 簡要的說 -調整後的三大塊由p3, p2, P1 的順序來選 )
3- If P2 thinks that the two largest parts are equal, then each player chooses a part in this order: P3, P2 and finally P1.
4- P3 chooses a piece among A1 and the two other pieces.
5- P2 chooses a piece with the limitation that if P3 didn't choose A1, P2 must choose it.
6- P1 chooses the last piece leaving just the trimmings A2 to be divided.
(-恭喜!, 到此時,除了A2那小塊 ,蛋糕主體已被公平分配好了(envy free). --現在來看看如何分配那一小塊A2….----)
- Now, the cake minus the trimmings A2 has been divided in an envy free manner.
( 注意當初得到A1那塊蛋糕的(即被p2切 後的那塊)隻有可能被p3, p2 其中的一個選走, 我們在此重新定義得到這個A1 的人是 PA , 另一人是PB。(P1當然還是那個老p1.)
The trimmed piece A1 has been chosen by either P2 or P3. Let's call the player who chose it PA and the other one Player PB.
(6, 7, 8步: 簡要的說 -PB再切那一小塊 A2為三份,然後PA, P1, PB 依次選定。 結束!)
6- PB cuts A2 into three equal pieces.
7- PA chooses a piece of A2. P1 chooses a piece of A2.
8- PB chooses the last remaining piece of A2.


------------
(最後關於證明不難,就留給大家娛樂了,
P1會認為他得到的〉= PA 的, 也〉= PB的;
PA會認為他得到的〉= P1 的, 也〉= PB的;
PB會認為他得到的〉= P1 的, 也〉= PA的;
let's see why the procedure is envy-free. It must be shown that each player believes that no other player received more than him. In the following analysis "largest" means "largest according to the player". Without loss of generality, we call B the piece that PB received and C the piece that P1 received.
PA received A1 plus the largest piece of A2. For him, A1 ≥ B and A1 ≥ C. So obviously, no other player received more than him.
PB received B plus a piece of A2. For him, B ≥ A1 and B ≥ C. Also, he cut A2 in 3 piece, so for him all the pieces are equal.
P1 received C plus a piece of A2. For him, C ≥ A1 and C = B.
P1 believes that PB didn't receive more than him because P1 chose his piece of A2 before PB.
P1 believes that PA didn't receive more than him because for P1, C is equal to A and A = A1 + A2; therefore C is larger than A1 plus the piece of A2 that PA received. (Even if PA took the whole A2, P1 would not envy PA.)
請您先登陸,再發跟帖!

發現Adblock插件

如要繼續瀏覽
請支持本站 請務必在本站關閉/移除任何Adblock

關閉Adblock後 請點擊

請參考如何關閉Adblock/Adblock plus

安裝Adblock plus用戶請點擊瀏覽器圖標
選擇“Disable on www.wenxuecity.com”

安裝Adblock用戶請點擊圖標
選擇“don't run on pages on this domain”