这篇文章源自于笔者曾在大学学习运筹学期间的一次演讲,由于老师分配的时间不够等原因,个人当时表现的比较一般,很多同学可能连题目都没搞清楚就结束了。笔者觉得,该题是近几年来微软编程之美中最有趣的一道,无论你是否熟悉数学或编程,都可以看懂这道题目并产生一些自己的想法。
题目
时间限制:1000ms
内存限制:256MB
描述
Alice和Bob都要向同一个商人购买钻石。商人手中有 N 颗钻石,他会将它们 一颗颗 地卖给他们,Alice和Bob通过竞价的方式来决定钻石的归属。具体的过程如下:商人首先指定其中一个人开始报价,之后两人轮流报价,要求是一定要比对方报的价格 更高。任何时候,如果一个人不愿出价或者出不起价钱时,可以宣布 弃权,则对手以最后一次报的价格将钻石买下。当然,如果两人都没钱,商人是不会卖钻石的。首次报价至少为 1,并且只能报 整数 的价钱。
Alice和Bob特别爱攀比,因此他们都希望 能比对方买到更多的钻石。Alice和Bob各自带了 CA 和 CB 的钱用于竞拍钻石。此外,Alice和商人有很不错的私人关系,因此商人总是会让 Alice先报价。现在请问,在Alice和Bob都用 最优策略 的情况下,谁能买到更多钻石? 假设双方都知道对方手中的现金数量,以及商人将要拍卖的钻石数量 N。
输入
输入文件包含多组测试数据。
第一行,给出一个整数 T,为 数据组数。接下来依次给出每组测试数据。
每组数据为三个用空格隔开的整数 N,CA,CB,表示 钻石的数量,以及 双方带的现金数量。
输出
对于每组测试数据,输出一行 Case #X: Y,其中 X表示测试数据编号,Y的取值为{-1, 0, 1},-1 表示Alice买到的钻石会比Bob 少,0 表示两人能买到 一样多,1 表示Alice能买到 更多 钻石。所有数据按读入顺序从1开始编号。
数据范围
1≤T≤1000
小数据:0≤N≤10; 0<CA, CB≤10
大数据:0≤N≤105; 0<CA, CB≤106
样例输入
2
4 3 5
7 4 7
样例输出
Case #1: 0
Case #2: 1
博弈论,论博弈
在讨论博弈论之前,我想先谈谈 博弈。博弈的目的是 利益,利益形成博弈的基础。参与博弈者是为了自身收益的最大化才进行互相竞争。也就是说,参与博弈的各方形成相互竞争、相互对抗的关系, 以争得利益的多少来决定胜负,而一定的外部条件又决定了竞争和对抗的具体形式,这就形成了博弈。
博弈论的 4 个要素:
- 2个或2个以上的参与者。在博弈中存在一个必需的条件即不是一个人在一个毫无干扰的环境中做决策。博弈者的身边充斥着其他具有主观能动性的决策者,他们的选择与其他博弈者的选择相互作用、相互影响。这种互动关系自然会对博弈各方的思维和行动产生重要的影响,有时甚至直接影响博弈结果。
- 博弈要有参与各方争夺的资源或收益。资源指的不仅仅是自然资源,还有人文资源。人们之所以参与博弈是受到利益的吸引,因此预期将来所获得利益的大小直接影响到博弈的吸引力和参与者的关注程度。
- 参与者有自己能够选择的策略。策略,指的是直接、实用地针对某一个具体问题所采取的应对方式。通俗地说,策略就是计策,是博弈参与者所选择的手段方法。博弈论中的策略,是先对局势和整体状况进行分析确定局势特征,找出其中关键因素,为达到最重要的目标进行手段选择。博弈论中的策略是牵一发而动全身的,直接对整个局势造成重大影响。
- 参与者拥有一定量的信息。博弈就是个人或组织在一定的环境条件与既定的规则下,同时或先后,一次或是多次选择策略并实施从而得到某种结果的过程。本题中,Alice和Bob知道对方和钻石商人的一切信息,属于 完全信息博弈。
题目分析
首先考虑钻石足够多的情况,即 CA+CB≤N,易知Alice和Bob谁拥有的钱多谁会获胜,一样多则为平局。
若 CA+CB>N,我们先来简单分析一下Alice的想法。他如果想要赢得胜利就要尽可能消耗Bob的钱,不能让Bob轻易得到任何一颗钻石。(比如Bob只花费很少的钱买一颗钻石这种事是绝对不可能的,除非Alice没钱了。)但是他也必须通过抬价才能实现上述这个目的。但是Bob也知道Alice拥有的钱,如果Alice漫天要价,Bob就不需要继续跟。那么Alice抬价到多少合适呢?
我们再分析一下Alice要抬高多少颗钻石的价格。Alice需要把所有的钻石的价格都抬到 CA/N 吗?显然不需要,注意Alice和Bob的目的仅仅是 买得比对方多,而不是买光所有的钻石。因此,设 n=[N/2]+1,我们可以知道Alice或者Bob最少拿到n颗钻石就可以获得胜利,所以Alice要把任意n颗钻石价格抬高到一个特定的数值。 (注:[x]表示不超过x的最大整数。)
接下来我们讨论一个命题的正确性:
仅仅在1颗钻石的竞价中,只会出现1次或2次报价,3次及以上的报价是毫无意义的。
由刚才的结论我们知道,Alice在心中有一个 标准价格(Bob也知道),所以如果Alice先开价,他就一定会开到这个价格。(开低了Bob就会跟,开高了Bob可以选择放弃。)但是在Alice开低价格的情况下,如果Bob跟的价格恰好是 标准价格,Alice则会面临一个很尴尬的情况—— 如果他选择跟,就相当于多花了1元钱而没有对Bob造成损失;如果他不跟,则相当于Bob少花了1元钱就买到了钻石。
综上,Alice只会开出 标准价格,而Bob也只有 两种选择——加一元或者是放弃。
题解
竞价情况可以分为2种:N为奇数或偶数。因为N为奇数不会出现平局,N为偶数可能会出现平局。
N为奇数时:n=[N/2]+1,考虑CA/n,若能整除,显然
现金比较 | 胜负结果 |
---|---|
CB≥(CA/n+1)*n | Bob胜 |
CB<(CA/n+1)*n | Alice胜 |
若不能整除,则在n颗钻石中会出现一些价格为 [CA/n] 的和一些价格为 [CA/n]+1 的,易知 Bob只会在[CA/n]的钻石后跟价,即
现金比较 | 胜负结果 |
---|---|
CB≥([CA/n]+1)*n | Bob胜 |
CB<([CA/n]+1)*n | Alice胜 |
举个例子:下为N=5,CA=8,CB=9的情况——Bob胜利
人物 | 第1次 | 第2次 | 第3次 | 第4次 | 第5次 |
---|---|---|---|---|---|
Alice | 3 | 3 | 2 | 2 | 2 |
Bob | 放弃 | 放弃 | 3 | 3 | 3 |
N为偶数时,n=[N/2]+1,由奇数情况易推知
现金比较 | 胜负结果 |
---|---|
CB≥([CA/(n-1)]+1)*n | Bob胜 |
CB≥([CA/n]+1)*(n-1) | 平局 |
CB<([CA/n]+1)*(n-1) | Alice胜 |
第一个式子的含义是:Bob连平局的机会(即Alice只想买前一半数量的钻石)都没有给,在Alice最大程度的阻挠下依然赢得比赛所满足的条件。
第二个式子的含义是:Alice想赢得比赛,所以要给前n颗钻石抬价,但是Bob仍然有能力买下一半的钻石阻止Alice获胜。
至此,题目得到解决。