【解题笔记】2021台湾IMOC-组合T11

发布于 2021-08-30 14:53 ,所属分类:试题库考试资料大全

【解题笔记】2021台湾IMOC-组合T11

今天做一道(也许简单组合题,绕了N个圈,最后发现其实答案曾经摆在我的面前……

本文写下解题时的走过的弯路。读者可以当作提示,也可以当作警示,希望对大家解组合题目时有一点点启发。

题目是中国台湾IMOC-组合组T11

在一个

这样,中心


这个时候,如果再删一个雷,总和反而变大了:


这说明之前的构造有问题,

探索2

什么样的图会让

容易发现,这个图不能再加雷,或者删雷了。

然后我开始证明。

探索5

假设存在





然后我盯着第一张图…………

怎么证明它不存在呢

这种图刚好左右可以嵌合

嗯,试试看,然后我得到了下图。


中心区一半单元格写

……好吧,重来证明



明显,共同特点是,有一颗雷,周围至少有4个雷。

于是将这个雷删掉,



于是中心区域的总和不超过

按均值来算,

这显然更浪费,平均值只有可能吧?咦?不对,总和……不知道……

WTH!

好吧,有漏洞得补上。还有m或n万一奇数呢?这也是漏洞。

证明过程简直千创百孔,到处是漏洞!

冷静,重新思考一下。

破解

每个雷的周围是否可能有7个没雷的单元格?

这可以调整删除。

这7格必有一格,周围至少4格没雷。

因此这格可以放一个雷。仍然没有7或以上的数字,且总和不减小。

每个雷最多与6个没雷的单元格相邻。

于是我们把雷均分给其周围没有雷的单元格,每个单元格格至少分到雷。

因此,每个写k的单元格,其加上周围分得的雷,共至少“占有”个单元格,折合的平均值至多,等号当且仅当

最后的废话

答案整理顺序应该是:探索8,探索5。

此题并不难。解答不会超过10行。

实际探索8的方法,前面并非没有用过(探索7)

组合解题中,接触到真相,然后被自己忽视,是非常常见的事情。


怎么解决呢?这个无法解决,每个人脑子总会有间歇性脑残的时候。以下操作可能能减少一些,祝大家好运:

1、打草稿时,稍有序一点,至少自己得记得从哪儿开始的。

2、不要轻易否掉之前的工作与努力。

最后,这套题挺有趣的,给命题者点个赞!



相关资源