white elephant gift exchange

MITBBS.com 首页 分类讨论区 精华区 博客 移民专栏 影视专栏 美食专栏 新闻中心 分类广告
◇在线[7777]
查寻网友：
版面搜索：
首页 - 分类讨论区 - - 金融工程版 - 同主题阅读文章 首页
同主题阅读：面试题 - white elephant gift exchange
[版面：金融工程] [首篇作者：person] , 2006年10月29日12:21:10
[首页] [上页] [下页] [末页] [分页： 1 2 ]
person
身份：用户
上站次数：46
发表文章：55 篇
经验值：183
表现值：16
生命力：120
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 1 ]
发信人: person (幸福的黄马甲), 信区: Quant
标 题: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Sun Oct 29 12:21:10 2006)


上来他问我只不知道white elephant gift exchange，我说不知道，于是他介绍问题如下

设置
1. 2n (n>3)个礼物，价值依次为1至2n的整数，标价公开
2. 有2n个人，编号1至2n， 人分两组，编号为奇数的一组，编号为偶数的一组
3. 胜负：
游戏终止时，若编号为奇数的一组拿到礼物总值大于n(n+1)，奇数的一组赢
若编号为偶数的一组拿到礼物总值大于n * n，偶数的一组赢
否则平

规则
1. 开始时，没有人有礼物，
2. 由没有礼物的编号最大的人选礼物
他/她可以选一样还没人要的礼物，
或他/她可以抢一样已经有人要的礼物，但是
这个礼物不能是上一轮中刚被抢过的礼物
也不能是已被抢过三次的礼物
3. 若不是每个人都有礼物了，返回第2条

问哪个组可以必胜，如何？

--

我花开后百花杀
满城尽带黄马甲

※ 来源:·BBS 未名空间站 http://mitbbs.com·[FROM: 69.110.]

美国嘉盛FOREX.COM 为您提供精准汇市分析, 模拟账户免费注册
skydive
身份：用户
上站次数：2642
发表文章：29593 篇
经验值：43169
表现值：127
生命力：365
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 2 ]
发信人: skydive (跳跳~~备战备荒为人民), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Sun Oct 29 12:25:45 2006), 转信


被抢过礼物的人转变成没礼物的？

下一轮立刻可以参与？


【 在 person (幸福的黄马甲) 的大作中提到: 】
: 上来他问我只不知道white elephant gift exchange，我说不知道，于是他介绍问题
如下
: 设置
: 1. 2n (n>3)个礼物，价值依次为1至2n的整数，标价公开
: 2. 有2n个人，编号1至2n， 人分两组，编号为奇数的一组，编号为偶数的一组
: 3. 胜负：
: 游戏终止时，若编号为奇数的一组拿到礼物总值大于n(n+1)，奇数的一组赢
: 若编号为偶数的一组拿到礼物总值大于n * n，偶数的一组赢
: 否则平
: 规则
: 1. 开始时，没有人有礼物，
: ...................


--

※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 69.118.]


person
身份：用户
上站次数：46
发表文章：55 篇
经验值：183
表现值：16
生命力：120
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 3 ]
发信人: person (幸福的黄马甲), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Sun Oct 29 12:29:30 2006)

是

只是由于规则不能把刚被抢走的礼物抢回来

【 在 skydive (跳跳~~备战备荒为人民) 的大作中提到: 】
: 被抢过礼物的人转变成没礼物的？
: 下一轮立刻可以参与？
: 如下



--

我花开后百花杀
满城尽带黄马甲

※ 来源:·BBS 未名空间站 http://mitbbs.com·[FROM: 69.110.]


juedr
身份：用户
上站次数：2273
发表文章：354 篇
经验值：3328
表现值：10
生命力：665
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 4 ]
发信人: juedr (我的不是你的我的前世今生), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Sun Oct 29 14:55:25 2006)

平。
分析一下可以看出：
1，偶数方先拿，然后奇数方，如此循环下去，无论发生抢夺与否。
2，任何一个数三次易手后就定了。所以先选择这个数的一方最后肯定得不到这个数。
3，由2知，最佳策略是选择没有OPEN的数里面最小的一个。把大数的初夜权留给对方，
最终再夺过来。
因此，偶数方选择的是开始的选择次序是1，3，5。。。奇数方选择的是2，4，6。。。
最后双方交换。
所以最后结果是平。

"上来他问我只不知道white elephant gift exchange，我说不知道，于是他介绍问题
如下

设置
1. 2n (n>3)个礼物，价值依次为1至2n的整数，标价公开
2. 有2n个人，编号1至2n， 人分两组，编号为奇数的一组，编号为偶数的一组
3. 胜负：
游戏终止时，若编号为奇数的一组拿到礼物总值大于n(n+1)，奇数的一组赢
若编号为偶数的一组拿到礼物总值大于n * n，偶数的一组赢
否则平

规则
1. 开始时，没有人有礼物，
2. 由没有礼物的编号最大的人选礼物
他/她可以选一样还没人要的礼物，
或他/她可以抢一样已经有人要的礼物，但是
这个礼物不能是上一轮中刚被抢过的礼物
也不能是已被抢过三次的礼物
3. 若不是每个人都有礼物了，返回第2条

问哪个组可以必胜，如何？"
--

※ 来源:·BBS 未名空间站 http://mitbbs.com·[FROM: 24.61.]


person
身份：用户
上站次数：46
发表文章：55 篇
经验值：183
表现值：16
生命力：120
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 5 ]
发信人: person (幸福的黄马甲), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Sun Oct 29 16:38:19 2006)



谢谢， 但我不是很明白你的解答

1，“偶数方先拿，然后奇数方，如此循环下去，无论发生抢夺与否”
如编号为2n的人先挑x，编号为2n-1的人抢x, 编号2n的人再挑y，
下面轮到编号2n-2的人挑或抢
所以此时序列是偶数方，奇数方，偶数方，偶数方....
2. "先选择这个数的一方最后肯定得不到这个数"
若如你的例中所说“偶数方选择的是开始的选择次序是1.. ”
奇数方以后可永不抢1号礼物啊，那1号礼物不就死在偶数方了？



【 在 juedr (我的不是你的我的前世今生) 的大作中提到: 】
: 平。
: 分析一下可以看出：
: 1，偶数方先拿，然后奇数方，如此循环下去，无论发生抢夺与否。
: 2，任何一个数三次易手后就定了。所以先选择这个数的一方最后肯定得不到这个数。
: 3，由2知，最佳策略是选择没有OPEN的数里面最小的一个。把大数的初夜权留给对方，
: 最终再夺过来。
: 因此，偶数方选择的是开始的选择次序是1，3，5。。。奇数方选择的是2，4，6。。。
: 最后双方交换。
: 所以最后结果是平。
: "上来他问我只不知道white elephant gift exchange，我说不知道，于是他介绍问题


--

我花开后百花杀
满城尽带黄马甲

※ 来源:·BBS 未名空间站 http://mitbbs.com·[FROM: 69.110.]


zgsun
身份：用户
上站次数：1161
发表文章：141 篇
经验值：2882
表现值：6
生命力：666
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 6 ]
发信人: zgsun (源泉), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Sun Oct 29 17:06:27 2006)

How do you define next round?

Does round mean at least a new item should be openned? Or it means someone
makes a decision steal/getnew?

【 在 person (幸福的黄马甲) 的大作中提到: 】
: 上来他问我只不知道white elephant gift exchange，我说不知道，于是他介绍问题
如下
: 设置
: 1. 2n (n>3)个礼物，价值依次为1至2n的整数，标价公开
: 2. 有2n个人，编号1至2n， 人分两组，编号为奇数的一组，编号为偶数的一组
: 3. 胜负：
: 游戏终止时，若编号为奇数的一组拿到礼物总值大于n(n+1)，奇数的一组赢
: 若编号为偶数的一组拿到礼物总值大于n * n，偶数的一组赢
: 否则平
: 规则
: 1. 开始时，没有人有礼物，
: ...................



--

※ 来源:·BBS 未名空间站 http://mitbbs.com·[FROM: 24.98.]


person
身份：用户
上站次数：46
发表文章：55 篇
经验值：183
表现值：16
生命力：120
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 7 ]
发信人: person (幸福的黄马甲), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Sun Oct 29 17:53:38 2006)


我从没提到过next round啊

如果一定要的话，应该是
someone makes a decision steal/getnew

当每个人都有礼物的时候，游戏就结束了，没有下一轮

【 在 zgsun (源泉) 的大作中提到: 】
: How do you define next round?
: Does round mean at least a new item should be openned? Or it means someone
: makes a decision steal/getnew?
: 如下



--

我花开后百花杀
满城尽带黄马甲

※ 来源:·BBS 未名空间站 http://mitbbs.com·[FROM: 69.110.]


zgsun
身份：用户
上站次数：1161
发表文章：141 篇
经验值：2882
表现值：6
生命力：666
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 8 ]
发信人: zgsun (源泉), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Sun Oct 29 19:48:29 2006)

I mean this.
这个礼物不能是"上一轮"中刚被抢过的礼物

Suppose A just steal x from B, and B steals y from C, now can C steal from A?

If next round is defined that "only one new gift is open", C cannot steal
from A.

【 在 person (幸福的黄马甲) 的大作中提到: 】
: 我从没提到过next round啊
: 如果一定要的话，应该是
: someone makes a decision steal/getnew
: 当每个人都有礼物的时候，游戏就结束了，没有下一轮



--

※ 来源:·BBS 未名空间站 http://mitbbs.com·[FROM: 24.98.]


bushel
身份：用户
上站次数：2050
发表文章：2512 篇
经验值：7720
表现值：21
生命力：666
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 9 ]
发信人: bushel (失乐园), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Sun Oct 29 19:59:15 2006), 转信

我怎么觉得是后拿的必胜阿
也就是单号必胜阿

【 在 person (幸福的黄马甲) 的大作中提到: 】
: 上来他问我只不知道white elephant gift exchange，我说不知道，于是他介绍问题
如下
: 设置
: 1. 2n (n>3)个礼物，价值依次为1至2n的整数，标价公开
: 2. 有2n个人，编号1至2n， 人分两组，编号为奇数的一组，编号为偶数的一组
: 3. 胜负：
: 游戏终止时，若编号为奇数的一组拿到礼物总值大于n(n+1)，奇数的一组赢
: 若编号为偶数的一组拿到礼物总值大于n * n，偶数的一组赢
: 否则平
: 规则
: 1. 开始时，没有人有礼物，
: ...................


--

※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 71.58.]


person
身份：用户
上站次数：46
发表文章：55 篇
经验值：183
表现值：16
生命力：120
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 10 ]
发信人: person (幸福的黄马甲), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Sun Oct 29 20:00:00 2006)


sorry

yes, suppose A just steal x from B, and B steals y from C, now can C steal
from A.

【 在 zgsun (源泉) 的大作中提到: 】
: I mean this.
: 这个礼物不能是"上一轮"中刚被抢过的礼物
: Suppose A just steal x from B, and B steals y from C, now can C steal from
A?
: If next round is defined that "only one new gift is open", C cannot steal
: from A.



--

我花开后百花杀
满城尽带黄马甲

※ 来源:·BBS 未名空间站 http://mitbbs.com·[FROM: 69.110.]


oolong
身份：用户
上站次数：988
发表文章：82 篇
经验值：1986
表现值：7
生命力：365
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 11 ]
发信人: oolong (乌龙茶), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Sun Oct 29 20:18:34 2006), 转信

后拿的最后要求的分数也高阿

【 在 bushel (失乐园) 的大作中提到: 】
: 我怎么觉得是后拿的必胜阿
: 也就是单号必胜阿
: 如下



--

※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 137.132.]


person
身份：用户
上站次数：46
发表文章：55 篇
经验值：183
表现值：16
生命力：120
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 12 ]
发信人: person (幸福的黄马甲), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Sun Oct 29 22:52:34 2006)


若even numbers好，the odd side也可以上来就抢even numbers啊

【 在 cashine (Who Am I) 的大作中提到: 】
: You're right.
: Basically no one will go for no.1, so there are really just 2n-1 gifts.
: At most they can be snatched (2n-1)*3 times which is odd.
: Now the gift-picking process is a rotation between even and odd number, so
: it is definite that the last snatch is from an even number person instead
of
: the odd number person.
: This means that "1" belongs to the odd group, hence they will lose.
: The even side should win.
: My strategy is, they always go for even numbers (2,4,...) or snatch odd
: numbers from the odd side, and the odd side will have to snatch these even
: ...................



--

我花开后百花杀
满城尽带黄马甲

※ 来源:·BBS 未名空间站 http://mitbbs.com·[FROM: 69.110.]


zgsun
身份：用户
上站次数：1161
发表文章：141 篇
经验值：2882
表现值：6
生命力：666
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 13 ]
发信人: zgsun (源泉), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Mon Oct 30 01:55:21 2006)

应该是偶数组赢.可以用归纳法证明偶数组至少能拿到2-2n的偶数(如果奇数组尽量使自
己的数字和大的话).
假设n=k-1的时候成立.并且这2k-2个数字是从3到2n.
最后拿数字的奇数组只能拿3,所以只可能有三种情况:(注)
A) 4被抢过一次.
B) 4被抢过两次.
C) 4被抢过三次.

n=k,考虑多两个数字1和2.两个组抢.图上画一下就知道任何哪种情况偶数组总能拿到4
和2(甚至4和3).

【 在 person (幸福的黄马甲) 的大作中提到: 】
: 上来他问我只不知道white elephant gift exchange，我说不知道，于是他介绍问题
如下
: 设置
: 1. 2n (n>3)个礼物，价值依次为1至2n的整数，标价公开
: 2. 有2n个人，编号1至2n， 人分两组，编号为奇数的一组，编号为偶数的一组
: 3. 胜负：
: 游戏终止时，若编号为奇数的一组拿到礼物总值大于n(n+1)，奇数的一组赢
: 若编号为偶数的一组拿到礼物总值大于n * n，偶数的一组赢
: 否则平
: 规则
: 1. 开始时，没有人有礼物，
: ...................



--

※ 来源:·BBS 未名空间站 http://mitbbs.com·[FROM: 24.98.]


Vishnu
身份：用户
上站次数：492
发表文章：569 篇
经验值：1552
表现值：35
生命力：120
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 14 ]
发信人: Vishnu (Time Dealer), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Mon Oct 30 06:31:16 2006), 转信

A same-group member can grab a high-numbered gift from his own group in
order to secure a gift, can't he?

【 在 zgsun (源泉) 的大作中提到: 】
: 应该是偶数组赢.可以用归纳法证明偶数组至少能拿到2-2n的偶数(如果奇数组尽量使自
: 己的数字和大的话).
: 假设n=k-1的时候成立.并且这2k-2个数字是从3到2n.
: 最后拿数字的奇数组只能拿3,所以只可能有三种情况:(注)
: A) 4被抢过一次.
: B) 4被抢过两次.
: C) 4被抢过三次.
: n=k,考虑多两个数字1和2.两个组抢.图上画一下就知道任何哪种情况偶数组总能拿到
4
: 和2(甚至4和3).
: 如下
: ...................


--

※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 207.237.]


person
身份：用户
上站次数：46
发表文章：55 篇
经验值：183
表现值：16
生命力：120
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 15 ]
发信人: person (幸福的黄马甲), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Mon Oct 30 06:32:08 2006)


谁说得对呢？

【 在 diehard75 (diehard) 的大作中提到: 】
: By the analysis, the even team will leave the gift 2n to player 1 because
: they know they have no chance to keep it.
: So we can reduce the problem to "we have gift 2n-1, 2n-2, ..., 1 and
player
: 2,
: 3, 4,..., 2n." By the same argument, player 2 can keep the gift 2n-1 (
player
: 1 won't take gift 2n-1 since he will take gift 2n).
: So recursively, odd team will have gift 2n, 2n-2, ... 2 and even team will
: have gift 2n-1, 2n-3, .. 1. So in the end, it will be a draw.
: This is just my analysis.


【 在 zgsun (源泉) 的大作中提到: 】
: 应该是偶数组赢.可以用归纳法证明偶数组至少能拿到2-2n的偶数(如果奇数组尽量使自
: 己的数字和大的话).
: 假设n=k-1的时候成立.并且这2k-2个数字是从3到2n.
: 最后拿数字的奇数组只能拿3,所以只可能有三种情况:(注)
: A) 4被抢过一次.
: B) 4被抢过两次.
: C) 4被抢过三次.
: n=k,考虑多两个数字1和2.两个组抢.图上画一下就知道任何哪种情况偶数组总能拿到
4
: 和2(甚至4和3).
: 如下



--

我花开后百花杀
满城尽带黄马甲

※ 来源:·BBS 未名空间站 http://mitbbs.com·[FROM: 69.110.]


Vishnu
身份：用户
上站次数：492
发表文章：569 篇
经验值：1552
表现值：35
生命力：120
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 16 ]
发信人: Vishnu (Time Dealer), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Mon Oct 30 06:34:45 2006), 转信

It seems neither is a concrete proof.
【 在 person (幸福的黄马甲) 的大作中提到: 】
: 谁说得对呢？
: player
: player
: 4



--

※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 207.237.]


loveleader
身份：用户
上站次数：1360
发表文章：526 篇
经验值：3118
表现值：12
生命力：365
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 17 ]
发信人: loveleader (hatefree), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Mon Oct 30 12:10:19 2006), 转信


偶数组赢. 下面是偶地理解,不知道对不对,请指正.
因为偶数组首先开始抢礼物,并且
如果偶数组想赢,就需要至少占据一个偶数号礼物.

因为每个礼物最多被抢三次,并且不能抢刚被抢过地.
所以基本第一次选地都会被抢走,但是除了接近
边界地时候不一样. 所以最后一轮抢夺会决定胜负.

那么偶得策略是: 让2n尽量抢最大地,
然后用2n-2最后中介,尽量hold住最大地,
显然这个最大地会被2n-1最后占有.
但是没有关系,这样可以保证最后会赢.
如果2n-1不这么干,那就更要输.

2n 抢 2n
2n-1 抢 2n-1
2n-2 抢 2n
2n 抢 2n-1
2n-1 抢 2n (2n done)
2n-2 抢 2n-1 (2n-1 done)
2n 抢 2n-2 ....
...
2n 抢 2(win)
1 抢 1.

假设n=4. 抢地过程是这样地:
8 -> 8 ( x-> y means x gets gift y)`
7->7
6->8
8->7
7->8 (8 done)
6->7 (7done)
8->6
5->5
4->6
8->5
5->6 (6done)
4->5 (4done)
8->4
3->3
2->4
8->3
3->4 (4done)
2->3(3done)
8->2 (win)
1->1
game over.
final even group (7,5,3,2) odd group (8,6,4,1)


【 在 person (幸福的黄马甲) 的大作中提到: 】
: 上来他问我只不知道white elephant gift exchange，我说不知道，于是他介绍问题
如下
: 设置
: 1. 2n (n>3)个礼物，价值依次为1至2n的整数，标价公开
: 2. 有2n个人，编号1至2n， 人分两组，编号为奇数的一组，编号为偶数的一组
: 3. 胜负：
: 游戏终止时，若编号为奇数的一组拿到礼物总值大于n(n+1)，奇数的一组赢
: 若编号为偶数的一组拿到礼物总值大于n * n，偶数的一组赢
: 否则平
: 规则
: 1. 开始时，没有人有礼物，
: ...................


--

※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 130.127.]


cashine
身份：版主
上站次数：1577
发表文章：677 篇
经验值：5629
表现值：11
生命力：666
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 18 ]
发信人: cashine (Who Am I), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Mon Oct 30 14:56:52 2006), 转信

I guess I was wrong in the previous post.
Think of it this way, each gift can be picked or snatched at most three
times, therefore gives a maximum of being in the hand of 4 people.
No one is going to snatch the "1" gift, therefore there are in total 4*(2n-1
)+1 rounds of picking or snatching, which is an odd number, since the
picking or snatching alternates from even to odd, this means the last person
to pick (because all other gifts have been snatched 3 times) will be from
the even group, so they have to pick 1.

The following argument does not apply to the case when people in each group
can snatch from each other.
Now think of the first person, he would not pick the large ones since they
will be snatched and finally in the hands of the opposite, so he should
start from the smallest, i.e., 2, the opposite won't need to snatch it, but
pick 3 instead, then the even group pick 4, none of them need to snatch from
the others because ultimately each group will have exactly what the other
group has after odd number of snatches, before anyone picks 1 and the game
ends.
So I guess the final result will be tied.

【 在 person (幸福的黄马甲) 的大作中提到: 】
: 若even numbers好，the odd side也可以上来就抢even numbers啊
: of



--

※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 131.215.]


cashine
身份：版主
上站次数：1577
发表文章：677 篇
经验值：5629
表现值：11
生命力：666
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 19 ]
发信人: cashine (Who Am I), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Mon Oct 30 14:57:51 2006), 转信

Think of 2 people playing the game,
with two gifts, 1 and 2.
you pick first, how can you win?
【 在 loveleader (hatefree) 的大作中提到: 】
: 偶数组赢. 下面是偶地理解,不知道对不对,请指正.
: 因为偶数组首先开始抢礼物,并且
: 如果偶数组想赢,就需要至少占据一个偶数号礼物.
: 因为每个礼物最多被抢三次,并且不能抢刚被抢过地.
: 所以基本第一次选地都会被抢走,但是除了接近
: 边界地时候不一样. 所以最后一轮抢夺会决定胜负.
: 那么偶得策略是: 让2n尽量抢最大地,
: 然后用2n-2最后中介,尽量hold住最大地,
: 显然这个最大地会被2n-1最后占有.
: 但是没有关系,这样可以保证最后会赢.
: ...................


--

※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 131.215.]


skydive
身份：用户
上站次数：2642
发表文章：29593 篇
经验值：43169
表现值：127
生命力：365
我的博客

[回复文章] [回信给作者] [本篇全文] [进入讨论区] [返回顶部] [删除文章] [转寄] [转贴] [ 20 ]
发信人: skydive (跳跳~~备战备荒为人民), 信区: Quant
标 题: Re: 面试题 - white elephant gift exchange
发信站: BBS 未名空间站 (Mon Oct 30 15:49:31 2006), 转信


n>3

that might matter.


【 在 cashine (Who Am I) 的大作中提到: 】
: Think of 2 people playing the game,
: with two gifts, 1 and 2.
: you pick first, how can you win?



--

※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 129.44.]

[首页] [上页] [下页] [末页] [分页： 1 2 ]
[快速返回] [进入金融工程讨论区] [返回顶部]
回复文章
帐号：
密码：
标题：
内 容：


赞助链接
www.jiaoyou8.com
mv column
www.rencai8.com
将您的链接放在这儿


版权所有，未名空间（mitbbs.com），since 1996

Contact Us - Terms and Conditions - Privacy Policy