yidingjizhu 封 anlawyer 在 pets 版 (转载) - 未名空间MITBBS历史存档

yidingjizhu 封 anlawyer 在 pets 版 (转载)# pets - 心有所宠

d*t2011-04-01 07:04

1 楼

一块蛋糕一把刀，一次只能一个人切，要保证公平分配。
2个人的情况下，可以产生一套规则，一个人切，一个人选择，这样切的人肯定会平分。
问3个人怎么办？
我本来想1st切，让第三个选择，然后剩下两个人分。但1st和3rd可以合谋，让1st给
3rd一块大的，然后3rd给1st回扣。

y*u2011-04-01 07:04

2 楼

【以下文字转载自 Notice 讨论区】
发信人: deliver (自动发信系统), 信区:
标题: yidingjizhu 封 anlawyer 在 pets 版
发信站: BBS 未名空间站自动发信系统 (Fri Apr 1 19:50:02 2011)
【此篇文章是由自动发信系统所张贴】
由于 anlawyer 在 pets 版的挑衅，PA行为行为，
被暂时取消在本版的发文权力 14 天。
备注:
http://www.mitbbs.com/article_t/pets/32033195.html
版主:yidingjizhu
Fri Apr 1 19:50:02 2011

S*w2011-04-01 07:04

3 楼

一次一个人切可以切几刀？

分。

【在 d********t 的大作中提到】

: 一块蛋糕一把刀，一次只能一个人切，要保证公平分配。
: 2个人的情况下，可以产生一套规则，一个人切，一个人选择，这样切的人肯定会平分。
: 问3个人怎么办？
: 我本来想1st切，让第三个选择，然后剩下两个人分。但1st和3rd可以合谋，让1st给
: 3rd一块大的，然后3rd给1st回扣。

d*t2011-04-01 07:04

4 楼

一刀

【在 S*******w 的大作中提到】

: 一次一个人切可以切几刀？
:
: 分。

d*t2011-04-01 07:04

5 楼

不防说说可以切多刀的情况下怎么做？

【在 S*******w 的大作中提到】

: 一次一个人切可以切几刀？
:
: 分。

S*w2011-04-01 07:04

6 楼

1 任选一个人切（怎么选可以猜拳）他的目标是尽可能的得到1/3
2. 在剩下2个没切的人当中选一个切（怎么选可以猜拳）他的目标是剩下的蛋糕尽可
能平分
3. 剩下的那个人选第二个人切的那2快当中一块
4. 第二个切的人选剩下的2快中的一块
5. 第一个切的人选最后一块

分。

【在 d********t 的大作中提到】

: 一块蛋糕一把刀，一次只能一个人切，要保证公平分配。
: 2个人的情况下，可以产生一套规则，一个人切，一个人选择，这样切的人肯定会平分。
: 问3个人怎么办？
: 我本来想1st切，让第三个选择，然后剩下两个人分。但1st和3rd可以合谋，让1st给
: 3rd一块大的，然后3rd给1st回扣。

d*t2011-04-01 07:04

7 楼

你这个解法不要每个人的目标这个limitation还成立吗？

【在 S*******w 的大作中提到】

: 1 任选一个人切（怎么选可以猜拳）他的目标是尽可能的得到1/3
: 2. 在剩下2个没切的人当中选一个切（怎么选可以猜拳）他的目标是剩下的蛋糕尽可
: 能平分
: 3. 剩下的那个人选第二个人切的那2快当中一块
: 4. 第二个切的人选剩下的2快中的一块
: 5. 第一个切的人选最后一块
:
: 分。

S*w2011-04-01 07:04

8 楼

应该成立吧
如果不按照那个目标做，那个人最后选的时候肯定就吃亏了所以为了his self-
interest 他必须这么做。
就像2个人的case 第一个切的人目标就是尽可能的得到一半

【在 d********t 的大作中提到】

: 你这个解法不要每个人的目标这个limitation还成立吗？

r*e2011-04-01 07:04

9 楼

切完后抓阄行吗

d*t2011-04-01 07:04

10 楼

好像行啊

【在 r***e 的大作中提到】

: 切完后抓阄行吗

d*t2011-04-01 07:04

11 楼

这个不行，如果1&2合谋，1切去个大的，那么3只能选个小的，然后1&2再自己内部分赃。

【在 S*******w 的大作中提到】

: 1 任选一个人切（怎么选可以猜拳）他的目标是尽可能的得到1/3
: 2. 在剩下2个没切的人当中选一个切（怎么选可以猜拳）他的目标是剩下的蛋糕尽可
: 能平分
: 3. 剩下的那个人选第二个人切的那2快当中一块
: 4. 第二个切的人选剩下的2快中的一块
: 5. 第一个切的人选最后一块
:
: 分。

S*w2011-04-01 07:04

12 楼

如果只能切成三块的话就对了。。。。
看你题目怎么定义了。

赃。

【在 d********t 的大作中提到】

: 这个不行，如果1&2合谋，1切去个大的，那么3只能选个小的，然后1&2再自己内部分赃。

z*u2011-04-01 07:04

13 楼

任意一个人切，简称切客，切客最后拿。另外两个人（简称拿客）抽签决定谁先拿。
假设切客把蛋糕分成三块 A，B，C，其中A >= B >= C。然后假设我们允许切客跟拿客
结这种盟：我，切客，愿意跟你们俩个拿客中拿到大块蛋糕的人结盟，共享我们的蛋糕
！让另一个拿客去吃使！拿客会不会同意？
先看一下，在这种情况下切客会怎么切？
max (A + C), subject to A >= B >= C >= 0 and A + B + C = 1
结论是： A = 1, B = 0, C = 0
从拿客的角度来说，他们有50%的概率先拿，成为结盟人，50%的概率后拿，成为受害者
。如果先拿，他可以分到一半的蛋糕；如果后拿，他只能吃使。所以说，作为拿客，如
果他结盟的话，他能拿到蛋糕的期望值是 0.5*50% + 0*50% = 0.25，而同时跟他结盟
的人的期望确是 0.5，所以从他的角度来说，他不会跟切蛋糕的人结盟！
如果没有结盟，切客该怎么切？
max C， subject to A >= B >= C >= 0 and A + B + C = 1
结论是： A = 1/3, B = 1/3, C = 1/3
所以“任意一个人切，简称切客，切客最后拿。另外两个人（简称拿客）抽签决定谁先
拿”是公平的。
ps.
从感觉有的地方漏了东西

分。

【在 d********t 的大作中提到】

: 一块蛋糕一把刀，一次只能一个人切，要保证公平分配。
: 2个人的情况下，可以产生一套规则，一个人切，一个人选择，这样切的人肯定会平分。
: 问3个人怎么办？
: 我本来想1st切，让第三个选择，然后剩下两个人分。但1st和3rd可以合谋，让1st给
: 3rd一块大的，然后3rd给1st回扣。

r*t2011-04-01 07:04

14 楼

选一个人做刀手切，先切一个半径，
从第二刀开始，切法是让刀作极坐标旋转，\theta 从 0 以 2 pi/n 增加，
n 是人数。
剩下的人在刀移动的过程中叫“切”，然后刀手动刀，切下来的蛋糕属
于叫“切”的那个人。
这个是小学时候一个数学趣味题书里面看来的。

分。

【在 d********t 的大作中提到】

: 一块蛋糕一把刀，一次只能一个人切，要保证公平分配。
: 2个人的情况下，可以产生一套规则，一个人切，一个人选择，这样切的人肯定会平分。
: 问3个人怎么办？
: 我本来想1st切，让第三个选择，然后剩下两个人分。但1st和3rd可以合谋，让1st给
: 3rd一块大的，然后3rd给1st回扣。

d*t2011-04-01 07:04

15 楼

what if two persons "cut" at the same time?

【在 r****t 的大作中提到】

: 选一个人做刀手切，先切一个半径，
: 从第二刀开始，切法是让刀作极坐标旋转，\theta 从 0 以 2 pi/n 增加，
: n 是人数。
: 剩下的人在刀移动的过程中叫“切”，然后刀手动刀，切下来的蛋糕属
: 于叫“切”的那个人。
: 这个是小学时候一个数学趣味题书里面看来的。
:
: 分。

b*k2011-04-01 07:04

16 楼

three people A, B, C.
A cut first piece X,
B cut left to two pieces: Y, and Z.
C pick first, can pick any of them.
B pick second, only can pick Y or Z if available.
A take the last.

d*t2011-04-01 07:04

17 楼

这样AC联手B就输了。

【在 b*****k 的大作中提到】

: three people A, B, C.
: A cut first piece X,
: B cut left to two pieces: Y, and Z.
: C pick first, can pick any of them.
: B pick second, only can pick Y or Z if available.
: A take the last.

r*t2011-04-01 07:04

18 楼

give it to either and repeat, won't affect the final result.
In fact, in the ith cut, there should be n-i people say "cut" if
all are rational.
The original answer I read says continuously changing \theta, so no two people
ask "cut" at the same time, but it is more precise to do discrete move.

【在 d********t 的大作中提到】

: what if two persons "cut" at the same time?

r*l2011-04-01 07:04

19 楼

这个以前Scientific American上专门有一期讲这个题目，可以用于n个人的情况。具体
方法是：第一个人先选定一个位置，如果切下去将得到他认为的1/n，但是不切。然后
让后面的每个人以此做出选择：如果某人觉得那一块比1/n大，那他就接过刀往回移动
，直到他认为的1/n为止；如果他觉得那一块比1/n小或者正好，那就什么都不做。这样
n个人全做完后，最后一个移动过刀的人切下蛋糕拿走。剩下n-1个人递归。

r*t2011-04-01 07:04

20 楼

这个不可能 work, 每个人都会觉得剩下的比 1/n 大，即使只有 1/n^2 大，
因为最小化后面决定的人（也包括先拿的人）的份额就能最大化自己将要
拿到的份额。最后一个切的人只能拿到 0.
照你的办法，最终所有人都拿到 0，只有最后一个切的人拿到整个蛋糕。

【在 r******l 的大作中提到】

: 这个以前Scientific American上专门有一期讲这个题目，可以用于n个人的情况。具体
: 方法是：第一个人先选定一个位置，如果切下去将得到他认为的1/n，但是不切。然后
: 让后面的每个人以此做出选择：如果某人觉得那一块比1/n大，那他就接过刀往回移动
: ，直到他认为的1/n为止；如果他觉得那一块比1/n小或者正好，那就什么都不做。这样
: n个人全做完后，最后一个移动过刀的人切下蛋糕拿走。剩下n-1个人递归。

r*l2011-04-01 07:04

21 楼

如果你觉得那块比1/n大，那就要动手将刀往回移。而你移动过刀以后，如果后面没人
动刀了，切下来的这块就是你的。所以没有人会将到移动到比他自己认为的1/n还要小
的地方。

【在 r****t 的大作中提到】

: 这个不可能 work, 每个人都会觉得剩下的比 1/n 大，即使只有 1/n^2 大，
: 因为最小化后面决定的人（也包括先拿的人）的份额就能最大化自己将要
: 拿到的份额。最后一个切的人只能拿到 0.
: 照你的办法，最终所有人都拿到 0，只有最后一个切的人拿到整个蛋糕。

d*t2011-04-01 07:04

22 楼

关键是怎么判断如果有两人联手是不是能take advantage

【在 r******l 的大作中提到】

: 如果你觉得那块比1/n大，那就要动手将刀往回移。而你移动过刀以后，如果后面没人
: 动刀了，切下来的这块就是你的。所以没有人会将到移动到比他自己认为的1/n还要小
: 的地方。

r*l2011-04-01 07:04

23 楼

这种题目都是假设蛋糕一旦分完就不能私下二次分配了，所以没有你说的所谓“回扣”。

【在 d********t 的大作中提到】

: 关键是怎么判断如果有两人联手是不是能take advantage

r*t2011-04-01 07:04

24 楼

那你这个办法是找的上确界，我前面说的办法找下确界，没看出来你的好在哪儿。

【在 r******l 的大作中提到】

: 如果你觉得那块比1/n大，那就要动手将刀往回移。而你移动过刀以后，如果后面没人
: 动刀了，切下来的这块就是你的。所以没有人会将到移动到比他自己认为的1/n还要小
: 的地方。

r*l2011-04-01 07:04

25 楼

当然，这个方法只能保证每个人都拿到一块他自己认为不小于1/n的蛋糕。但是第一个
切蛋糕的人可能认为第二个切蛋糕的人拿的更大。那片文章后面还讨论了如何让每个人
都觉得别人拿的不比自己大，但是当时没看明白。
如果有谁能找到那期Scientific American放上来就好了，呵呵。

【在 r******l 的大作中提到】

: 这个以前Scientific American上专门有一期讲这个题目，可以用于n个人的情况。具体
: 方法是：第一个人先选定一个位置，如果切下去将得到他认为的1/n，但是不切。然后
: 让后面的每个人以此做出选择：如果某人觉得那一块比1/n大，那他就接过刀往回移动
: ，直到他认为的1/n为止；如果他觉得那一块比1/n小或者正好，那就什么都不做。这样
: n个人全做完后，最后一个移动过刀的人切下蛋糕拿走。剩下n-1个人递归。

r*l2011-04-01 07:04

26 楼

你说的叫停的办法也是经典算法，本质跟我说的是一样的。我没说我的算法更好啊。是
你说我的方法不work，我告诉你可以work而已。

【在 r****t 的大作中提到】

: 那你这个办法是找的上确界，我前面说的办法找下确界，没看出来你的好在哪儿。

m*l2011-04-01 07:04

27 楼

你这个theta只能以2 pi / n非连续增加不行吧?
如果可以这样,那这个题
随便可以做了,
就规定切口必须是2pi/n,一次切下,每个人去那个2pi/n那一块,
都一样阿

【在 r****t 的大作中提到】

: 选一个人做刀手切，先切一个半径，
: 从第二刀开始，切法是让刀作极坐标旋转，\theta 从 0 以 2 pi/n 增加，
: n 是人数。
: 剩下的人在刀移动的过程中叫“切”，然后刀手动刀，切下来的蛋糕属
: 于叫“切”的那个人。
: 这个是小学时候一个数学趣味题书里面看来的。
:
: 分。

r*l2011-04-01 07:04

28 楼

他那个算法到应该是连续移动的，而不是以2pi/n跳动的（因为根本没法保证2pi/n么）
。本质应该跟我说的方法一样。

【在 m*******l 的大作中提到】

: 你这个theta只能以2 pi / n非连续增加不行吧?
: 如果可以这样,那这个题
: 随便可以做了,
: 就规定切口必须是2pi/n,一次切下,每个人去那个2pi/n那一块,
: 都一样阿

r*l2011-04-01 07:04

29 楼

Google了一下，那种“每个人都觉得别人拿的不比自己大”的情况，四个人以上就没有
切刀数目有限的解法了（也就更不能保证n个人只切n-1刀了）。

【在 r******l 的大作中提到】

: 当然，这个方法只能保证每个人都拿到一块他自己认为不小于1/n的蛋糕。但是第一个
: 切蛋糕的人可能认为第二个切蛋糕的人拿的更大。那片文章后面还讨论了如何让每个人
: 都觉得别人拿的不比自己大，但是当时没看明白。
: 如果有谁能找到那期Scientific American放上来就好了，呵呵。

d*t2011-04-01 07:04

30 楼

郁闷就在这里，interviewer一直强调可以有collusion吃回扣的

”。

【在 r******l 的大作中提到】

: 这种题目都是假设蛋糕一旦分完就不能私下二次分配了，所以没有你说的所谓“回扣”。