据说是IMO Shortlist

我就不知道怎么才能过审核了

题目如下：

一个正五边形，每个顶点上有一个水桶。水桶的容量为2L。Alice的任务是每次从河中取1L的水，并随意分配到五个水桶中。Bob的任务是随便挑两个有边相连的水桶，将里面的水倒掉。如果有个水桶装满了Alice就赢了，问：Bob能否阻止Alice获胜？

 

嗯果然直接空行就可以了。

能。

这个题最坑的地方在于上届是紧的，即对于任意小于2的数，Alice都可以构造出来一种方案，使得Bob无法阻止她灌满水。然而，这不重要。

以下是自己当时写的解答。并非标准答案。

重要的是策略：

如下：

如果有一桶里水大于等于1L，那么把它和与它相连的两桶水中最多的倒掉。

否则，考虑任何两个不相邻的水桶，取容量最少的一组。（它们讲五边形分成两半，一半一个点一半两个点）然后将两个点的那一侧的两桶水倒掉

首先证明：采用这样的策略，每次倒空两个桶后，不会存在连续的三个桶ABC使得AC内水的和大于等于1L，或B中的水大于等于1L。

采用数学归纳法，一开始显然满足条件

设k步之后仍然满足，则k+1步之后

还是按照顺时针标号。不妨设上次Bob倒空了DE中的水。那么ABC是满足条件的。

考虑Alice操作完毕后的情况

(i)D E中的水大于等于1L ，意即Alice把全部的水灌入了DE中的某个桶内。那么只需要把DE再次倒掉即可。

(ii)A C中的水大于等于1L。不妨设为A。显然，CE的和小于1L，B中的水小于1L。那么只需将AB倒掉即可

(iii)B中的水大于等于1L。显而易见，A+D,C+E的和小于等于2，且DE小于1.因此两组中必然有一组满足条件。不妨设AD满足条件，则倒掉BC即可。

(iv)由于A＋D＋C＋E＝2，因此AD，CE中必有一组的和小于等于1.因此条件必然可以满足。

 

其次证明，在这样的情况下，Alice无法达成胜利条件。

采用反证法，不妨设Alice在某一步将第K个水桶灌到2L。

显然，在上一步Bob倒空之后，水桶K中的水大于等于1L。矛盾。

下学期要选博弈论了。听说这门课有30分的作业是写一篇6页以上的论文。然而我这辈子还没写过论文呢。祝好运

上一篇[Puzzle_Toad#10]Card Tricks

顶 0 踩 0

我的同类文章

猜你在找

查看评论

* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场

个人资料

Vkrms

访问：59次

积分：31

等级：

积分：31

排名：千里之外

文章搜索

文章分类

概率(1)

博弈论(0)

友情链接 北京PM2.5

文章存档

2015年12月(3)

阅读排行

第一篇blog(17)

(17)

评论排行

2015IIIS二招数学压轴题(1)

第一篇blog(0)

(0)

推荐文章

*Hadoop节点"慢磁盘"监控

*假如你想成为全栈工程师…

*没有躲过的坑--正则表达式截取字符串

*CardView完全解析与RecyclerView结合使用(三十二)

*And roid 高仿微信发朋友圈浏览图片效果

*通过Ajax的方式执行GP服务

最新评论

AaronGZK: 给THU大神跪了！