d********t
发帖数: 9628 | 1 一块蛋糕一把刀，一次只能一个人切，要保证公平分配。
2个人的情况下，可以产生一套规则，一个人切，一个人选择，这样切的人肯定会平分。
问3个人怎么办？
我本来想1st切，让第三个选择，然后剩下两个人分。但1st和3rd可以合谋，让1st给
3rd一块大的，然后3rd给1st回扣。 |
S*******w
发帖数: 24236 | 2 一次一个人切 可以切几刀？
分。
【在 d********t 的大作中提到】
: 一块蛋糕一把刀，一次只能一个人切，要保证公平分配。
: 2个人的情况下，可以产生一套规则，一个人切，一个人选择，这样切的人肯定会平分。
: 问3个人怎么办？
: 我本来想1st切，让第三个选择，然后剩下两个人分。但1st和3rd可以合谋，让1st给
: 3rd一块大的，然后3rd给1st回扣。
|
d********t
发帖数: 9628 | 3 一刀
【在 S*******w 的大作中提到】
: 一次一个人切 可以切几刀？
:
: 分。
|
d********t
发帖数: 9628 | 4 不防说说可以切多刀的情况下怎么做？
【在 S*******w 的大作中提到】
: 一次一个人切 可以切几刀？
:
: 分。
|
S*******w
发帖数: 24236 | 5 1 任选一个人切（怎么选可以猜拳） 他的目标是尽可能的得到1/3
2. 在剩下2个没切的人当中选一个切（怎么选可以猜拳） 他的目标是剩下的蛋糕尽可
能平分
3. 剩下的那个人选第二个人切的那2快当中一块
4. 第二个切的人选剩下的2快中的一块
5. 第一个切的人选最后一块
分。
【在 d********t 的大作中提到】
: 一块蛋糕一把刀，一次只能一个人切，要保证公平分配。
: 2个人的情况下，可以产生一套规则，一个人切，一个人选择，这样切的人肯定会平分。
: 问3个人怎么办？
: 我本来想1st切，让第三个选择，然后剩下两个人分。但1st和3rd可以合谋，让1st给
: 3rd一块大的，然后3rd给1st回扣。
|
d********t
发帖数: 9628 | 6 你这个解法不要每个人的目标这个limitation还成立吗？
【在 S*******w 的大作中提到】
: 1 任选一个人切（怎么选可以猜拳） 他的目标是尽可能的得到1/3
: 2. 在剩下2个没切的人当中选一个切（怎么选可以猜拳） 他的目标是剩下的蛋糕尽可
: 能平分
: 3. 剩下的那个人选第二个人切的那2快当中一块
: 4. 第二个切的人选剩下的2快中的一块
: 5. 第一个切的人选最后一块
:
: 分。
|
S*******w
发帖数: 24236 | 7 应该成立吧
如果不按照那个目标做，那个人最后选的时候肯定就吃亏了 所以为了his self-
interest 他必须这么做。
就像2个人的case 第一个切的人目标就是尽可能的得到一半
【在 d********t 的大作中提到】
: 你这个解法不要每个人的目标这个limitation还成立吗？
|
r***e
发帖数: 213 | |
d********t
发帖数: 9628 | 9 好像行啊
【在 r***e 的大作中提到】
: 切完后抓阄行吗
|
d********t
发帖数: 9628 | 10 这个不行，如果1&2合谋，1切去个大的，那么3只能选个小的，然后1&2再自己内部分赃。
【在 S*******w 的大作中提到】
: 1 任选一个人切（怎么选可以猜拳） 他的目标是尽可能的得到1/3
: 2. 在剩下2个没切的人当中选一个切（怎么选可以猜拳） 他的目标是剩下的蛋糕尽可
: 能平分
: 3. 剩下的那个人选第二个人切的那2快当中一块
: 4. 第二个切的人选剩下的2快中的一块
: 5. 第一个切的人选最后一块
:
: 分。
|
|
|
S*******w
发帖数: 24236 | 11 如果只能切成三块的话 就对了。。。。
看你题目怎么定义了。
赃。
【在 d********t 的大作中提到】
: 这个不行，如果1&2合谋，1切去个大的，那么3只能选个小的，然后1&2再自己内部分赃。
|
z****u
发帖数: 104 | 12 任意一个人切，简称切客，切客最后拿。另外两个人（简称拿客）抽签决定谁先拿。
假设切客把蛋糕分成三块 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****t
发帖数: 10904 | 13 选一个人做刀手切，先切一个半径，
从第二刀开始，切法是让刀作极坐标旋转，\theta 从 0 以 2 pi/n 增加，
n 是人数。
剩下的人在刀移动的过程中叫“切”，然后刀手动刀，切下来的蛋糕属
于叫“切”的那个人。
这个是小学时候一个数学趣味题书里面看来的。
分。
【在 d********t 的大作中提到】
: 一块蛋糕一把刀，一次只能一个人切，要保证公平分配。
: 2个人的情况下，可以产生一套规则，一个人切，一个人选择，这样切的人肯定会平分。
: 问3个人怎么办？
: 我本来想1st切，让第三个选择，然后剩下两个人分。但1st和3rd可以合谋，让1st给
: 3rd一块大的，然后3rd给1st回扣。
|
d********t
发帖数: 9628 | 14 what if two persons "cut" at the same time?
【在 r****t 的大作中提到】
: 选一个人做刀手切，先切一个半径，
: 从第二刀开始，切法是让刀作极坐标旋转，\theta 从 0 以 2 pi/n 增加，
: n 是人数。
: 剩下的人在刀移动的过程中叫“切”，然后刀手动刀，切下来的蛋糕属
: 于叫“切”的那个人。
: 这个是小学时候一个数学趣味题书里面看来的。
:
: 分。
|
b*****k
发帖数: 26 | 15 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********t
发帖数: 9628 | 16 这样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****t
发帖数: 10904 | 17 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******l
发帖数: 10760 | 18 这个以前Scientific American上专门有一期讲这个题目，可以用于n个人的情况。具体
方法是：第一个人先选定一个位置，如果切下去将得到他认为的1/n，但是不切。然后
让后面的每个人以此做出选择：如果某人觉得那一块比1/n大，那他就接过刀往回移动
，直到他认为的1/n为止；如果他觉得那一块比1/n小或者正好，那就什么都不做。这样
n个人全做完后，最后一个移动过刀的人切下蛋糕拿走。剩下n-1个人递归。 |
r****t
发帖数: 10904 | 19 这个不可能 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******l
发帖数: 10760 | 20 如果你觉得那块比1/n大，那就要动手将刀往回移。而你移动过刀以后，如果后面没人
动刀了，切下来的这块就是你的。所以没有人会将到移动到比他自己认为的1/n还要小
的地方。
【在 r****t 的大作中提到】
: 这个不可能 work, 每个人都会觉得剩下的比 1/n 大，即使只有 1/n^2 大，
: 因为最小化后面决定的人（也包括先拿的人）的份额就能最大化自己将要
: 拿到的份额。最后一个切的人只能拿到 0.
: 照你的办法，最终所有人都拿到 0， 只有最后一个切的人拿到整个蛋糕。
|
|
|
d********t
发帖数: 9628 | 21 关键是怎么判断如果有两人联手是不是能take advantage
【在 r******l 的大作中提到】
: 如果你觉得那块比1/n大，那就要动手将刀往回移。而你移动过刀以后，如果后面没人
: 动刀了，切下来的这块就是你的。所以没有人会将到移动到比他自己认为的1/n还要小
: 的地方。
|
r******l
发帖数: 10760 | 22 这种题目都是假设蛋糕一旦分完就不能私下二次分配了，所以没有你说的所谓“回扣”。
【在 d********t 的大作中提到】
: 关键是怎么判断如果有两人联手是不是能take advantage
|
r****t
发帖数: 10904 | 23 那你这个办法是找的上确界，我前面说的办法找下确界，没看出来你的好在哪儿。
【在 r******l 的大作中提到】
: 如果你觉得那块比1/n大，那就要动手将刀往回移。而你移动过刀以后，如果后面没人
: 动刀了，切下来的这块就是你的。所以没有人会将到移动到比他自己认为的1/n还要小
: 的地方。
|
r******l
发帖数: 10760 | 24 当然，这个方法只能保证每个人都拿到一块他自己认为不小于1/n的蛋糕。但是第一个
切蛋糕的人可能认为第二个切蛋糕的人拿的更大。那片文章后面还讨论了如何让每个人
都觉得别人拿的不比自己大，但是当时没看明白。
如果有谁能找到那期Scientific American放上来就好了，呵呵。
【在 r******l 的大作中提到】
: 这个以前Scientific American上专门有一期讲这个题目，可以用于n个人的情况。具体
: 方法是：第一个人先选定一个位置，如果切下去将得到他认为的1/n，但是不切。然后
: 让后面的每个人以此做出选择：如果某人觉得那一块比1/n大，那他就接过刀往回移动
: ，直到他认为的1/n为止；如果他觉得那一块比1/n小或者正好，那就什么都不做。这样
: n个人全做完后，最后一个移动过刀的人切下蛋糕拿走。剩下n-1个人递归。
|
r******l
发帖数: 10760 | 25 你说的叫停的办法也是经典算法，本质跟我说的是一样的。我没说我的算法更好啊。是
你说我的方法不work，我告诉你可以work而已。
【在 r****t 的大作中提到】
: 那你这个办法是找的上确界，我前面说的办法找下确界，没看出来你的好在哪儿。
|
m*******l
发帖数: 12782 | 26 你这个theta只能以2 pi / n非连续增加不行吧?
如果可以这样,那这个题
随便可以做了,
就规定切口必须是2pi/n,一次切下,每个人去那个2pi/n那一块,
都一样阿
【在 r****t 的大作中提到】
: 选一个人做刀手切，先切一个半径，
: 从第二刀开始，切法是让刀作极坐标旋转，\theta 从 0 以 2 pi/n 增加，
: n 是人数。
: 剩下的人在刀移动的过程中叫“切”，然后刀手动刀，切下来的蛋糕属
: 于叫“切”的那个人。
: 这个是小学时候一个数学趣味题书里面看来的。
:
: 分。
|
r******l
发帖数: 10760 | 27 他那个算法到应该是连续移动的，而不是以2pi/n跳动的（因为根本没法保证2pi/n么）
。本质应该跟我说的方法一样。
【在 m*******l 的大作中提到】
: 你这个theta只能以2 pi / n非连续增加不行吧?
: 如果可以这样,那这个题
: 随便可以做了,
: 就规定切口必须是2pi/n,一次切下,每个人去那个2pi/n那一块,
: 都一样阿
|
r******l
发帖数: 10760 | 28 Google了一下，那种“每个人都觉得别人拿的不比自己大”的情况，四个人以上就没有
切刀数目有限的解法了（也就更不能保证n个人只切n-1刀了）。
【在 r******l 的大作中提到】
: 当然，这个方法只能保证每个人都拿到一块他自己认为不小于1/n的蛋糕。但是第一个
: 切蛋糕的人可能认为第二个切蛋糕的人拿的更大。那片文章后面还讨论了如何让每个人
: 都觉得别人拿的不比自己大，但是当时没看明白。
: 如果有谁能找到那期Scientific American放上来就好了，呵呵。
|
d********t
发帖数: 9628 | 29 郁闷就在这里，interviewer一直强调可以有collusion吃回扣的
”。
【在 r******l 的大作中提到】
: 这种题目都是假设蛋糕一旦分完就不能私下二次分配了，所以没有你说的所谓“回扣”。
|
