班型：实验班
内容：组合，棋盘问题
组合题与其他版块题目最大的区别在于，看着特接地气，有现实世界中的影子，可操作性强．
实验班暑假后6讲是组合，其中有几道题比较有意思，方法也比较具有一般性，这里分享一下．
原题出自罗马尼亚
在
的正方形棋盘内最多可以放多少个“王”，使得每个王恰好可以吃到另外一个王？（一个王可以吃到它所在单元格有公共顶点的单元格内的棋子）
引王是国际象棋最重要的棋子，没有之一．
但这题显然不太符合国际象棋的规则，太多王了，棋盘也不对．
所以我们改变一下思路，把它变成现实中的“王”．
身为王，最喜欢的事是什么？开疆拓土．翻开历史书，会发现，对“王”的评价，必有一条是领土的扩张与缩小，除非闭关锁国，专心内斗的．地盘大到超乎想象的，叫帝王，比如终身都在抢地盘的某两位……
呃，跑题了……
回到原题，重新理解一下题意：
在一个面积为的正方形陆地上，有一些王，每个王的实力都相当，谁也干不死谁．每个王的周围8格内恰好一个王，问这块陆地上最多能有多少王？
分析既然谁也干不死谁，那相邻的王大概率最终会结成同盟．
于是这块陆地上，就会有一些“双王同盟”与一些“孤家寡人”．
（似乎有什么奇怪的东西混入？）
所有的王开始争锋，最终局势平稳的时候，每个空余地盘都会被瓜分．
那“双王同盟”与“孤家寡人”各自会有多少地盘？
如果没有其他王，他们地盘，至少有下面那么多：
但有其他王还在抢，于是，周围一圈地盘，恐怕就得缩水了．
最终会占多少地盘？（外围的小格子是
格）
即“双王联盟”地盘至少是6，“孤家寡人”地盘至少是4．
这时总地盘出了点问题．处在地图边缘的王，并不能向外继续延伸地盘？
来看看现实世界地图，会发现大陆边缘的国家会把一部分海洋也划进去．
所以，我们也给这些王发点“领海”．
于是，含海洋，总面积变成了．
，多余的1并不能安排一个“孤家寡人”．
所以最多安排28个“双王联盟”，总计56个王．
构造（中心点放个“圣杯”，完美~）
其实，构造里也有学问，以后再讲.
无独有偶与之相关的题是两道课前补充题．第1次的题目把原题的n改成4，让大家动手算算，
第2次的题目是原题，题源是年欧洲女子数学奥林匹克，T2．
（第2题，不用P2是因为身为英语渣的直癌．）
给定正整数
，在
方格表上放置若干块多米诺骨牌，使得该方格表的每个格恰与一个被多米诺骨牌覆盖的格相邻．求可以放置的多米诺骨牌个数的最大值．
注：一块多米诺骨牌是大小为
或
的方格表．每块多米诺骨牌只能放置在方格表的两个格上，且不同的多米诺骨牌不能重叠．若两个不同的格有一条公共边，则称它们是相邻的．
分析“每个格恰与一个被多米诺骨牌覆盖的格相邻”，这与领土互不重叠是不是很像？
那我们把每张骨牌当作一个王，那它的地盘有多大？
一张骨牌占的地盘有8格．
同样的，边缘的骨牌，得给它发点“领海”．
但周围一圈（如图蓝色一圈），不再全是“领海”．
写着1的是，写着0的不是．
可以发现，写了多少个1，必定写多少个0．
所以这圈蓝色地盘，至多只有一半是领海．
现在可以算算能放多少王，骨牌．
总面积
，
至多
张骨牌．
取个整数，最大值为
．
构造这里分别给出
两种情况的，其他的自己类推．
为奇数时，从内到外，第偶数圈不放，其作间隔放．
为偶数时，从内到外，第奇数圈不放，其作间隔放．
更多昨天写的台湾T11，扫雷那题，最终解答出来，也是数地盘，有兴趣可以自己试试，当作练习．
台湾IMOC-组合T11
心宏容天