MathLabs

第5题

两只松鼠 Bushy 和 Jumpy 为过冬收集了 20212021 颗核桃。Jumpy 把核桃从 11 编号到 20212021，并绕着它们最喜欢的树挖了 20212021 个排成圆形的小洞。第二天早上，Jumpy 发现 Bushy 已经往每个洞里放了一颗核桃，但完全没在意编号。Jumpy 很不满意，决定通过一系列 20212021 次操作重新排列核桃。在第 kk 次操作中，Jumpy 交换与核桃 kk 相邻的两颗核桃的位置。证明存在某个 kk，使得在第 kk 次操作中，Jumpy 交换的核桃 aa 与 bb 满足 a<k<ba<k<b。
第 4/5 步：证明偶数块在长度 22处冻结或不均匀分裂
上一步下一步
通俗地说

恰好由两颗黑色核桃组成的块永远不会被打破，因为要把其中一颗染红，就需要它外侧的邻居与它的伙伴颜色相同，而事实并非如此。

L even, L≥4:L−1=i+(L−1−i)L\ \text{even},\ L\ge4:\quad L-1=i+(L-1-i)
详细分析

由第 2 步，核桃只有在两侧邻居颜色已经相同时才能变红。因此长度恰为 22 的黑色块永远不会失去一颗核桃，因为其中每颗核桃都有一个黑色伙伴和一个红色外侧邻居——颜色不匹配。长度为偶数 L≥4L\ge4 的黑色块，当内部某颗核桃变红时（必然两侧邻居都是黑色），会分裂成长度为 ii 与 L−1−iL-1-i 的两个子块，且 i+(L−1−i)=L−1i+(L-1-i)=L-1 为奇数，故一个子块为偶数、另一个为奇数。