2016IMO Short List

最小的正整数 $k=2n$．
先构造一个将 $2n$ 个格做上标记且满足条件的例子：将行和列分别记为第 $1,2,\ldots,2n$ 行和第 $1,2,\ldots,2n$ 列，第 $i$ 行第 $j$ 列的格记为 $(i,j)$．
对 $i=1,2,\ldots,n$，标记格 $(i,i),(i,i+1)$，如图．接下来证明满足条件的分拆是唯一的．
注意到，方格表的两条对角线将方格表分成四个区域．再注意到，覆盖格 $(1,1)$ 的多米诺一定是竖直的．于是，知覆盖格 $(2,2),(3,3),\ldots,(n,n)$ 的多米诺也是竖直的．由递归的方法，知左边区域中的多米诺均是竖直的．由旋转对称性，知下面区域中的多米诺均是水平的；右边区域中的多米诺均是竖直的；上面区域中的多米诺均是水平的，如图．若只有 $k$（$k<2n$）个格被做上标记，且存在一个分拆 $P$ 满足条件，下面证明：存在另一个不同于 $P$ 的分拆也满足条件．
设 $d$ 为方格表的主对角线．构造一个图，其边被染为两种颜色之一：这个图的每个顶点均为方格表的格，若两个方格属于 $P$ 的同一个多米诺，则在图中的与这两个格对应的两个顶点之间连一条红边．将连接红边的两个顶点关于 $d$ 的对称点之间连一条蓝边，有可能两个顶点之间所连边的颜色是双色的，则每个顶点的红边的度和蓝边的度均为 $1$．于是，图被分拆为若干个圈，每个圈的颜色均交替出现（一个圈的长可以等于 $2$）．
考虑对角线 $d$ 上的任意一个格 $c$，与 $c$ 相邻的两条边关于 $d$ 是对称的．于是，与格 $c$ 相邻的格是不同的．这表明，包含格 $c$ 的圈 $C(c)$ 的长度至少为 $4$．考虑这个圈的一部分：$c_0 , c_1 , \ldots , c_m$，其中，$c_0 =c$，$m$ 为最小的正整数，使得格 $c_m$ 在对角线 $d$ 上，则格 $c_m$ 与 $c$ 不同．由于这部分关于对角线 $d$ 对称的通路也在这个圈上，于是，这两部分通路合起来构成了 $C(c)$．因此，$C(c)$ 恰包含 $d$ 上的两个格．这表明，$d$ 上的所有的 $2n$ 个格属于 $n$ 个圈 $C_1 , C_2 ,\ldots, C_n$，每个圈的长度至少为 $4$．
由抽屉原理，知存在一个圈 $C_i$ 最多包含 $k$ 个被标记的格中的一个．用下述方法修正 $P$：先移去 $C_i$ 中对应着红边的多米诺，再在 $C_i$ 中放入对应着蓝边的多米诺．
因为 $C_i$ 中至少有四个顶点，这样的拆分 $P'$ 与 $P$ 不同，且 $C_i$ 最多包含一个被标记的格，所以，在 $P'$ 中没有多米诺包含两个被标记的格．这就证明分拆不是唯一的．
因此，$k$ 不能小于 $2n$

略