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。
第 5/5 步:在全部 20212021 次操作后得出矛盾
∃ frozen black block of length 2 forever\exists\ \text{frozen black block of length } 2\ \text{forever}
详细分析

从长度为 20202020 的偶数块开始,每次分裂都产生一个偶数子块和一个奇数子块,而每个偶数子块最终都会(通过进一步分裂)归约为长度恰为 22 的冻结块,它永远无法完全变红。因此至少有一对黑色核桃永远存在。但第 kk 次操作会把核桃 kk 染红,对所有 k=1,…,2021k=1,\ldots,2021 都成立,所以全部 20212021 次操作后每颗核桃都应变红——矛盾。因此假设不成立,必有某次操作 kk 交换了满足 a<k<ba<k<b 的核桃。