水木社区手机版
- 主题:IMO 2021
※ 修改:·liushuoshu 于 Jul 21 14:16:10 2021 修改本文·[FROM: 111.205.43.*]
※ 来源:·水木社区 http://www.mysmth.net·[FROM: 111.205.43.*]
修改:liushuoshu FROM 111.205.43.*
FROM 111.205.43.*- f(k+1)=f(k)+1 怎么来的？
【 在 here080 的大作中提到: 】
: 哈哈，一觉醒来得到一个第5题的很精妙的解法。
: 在第k步时考虑所有小于k的数的分布，定义他们之间的间隔的个数为f(k)
: 其中f(1) = 0, f(2) = 1
: ...................
--
FROM 111.199.188.* - 要不你再具体说下f的定义？感觉理解的不一样
【 在 here080 的大作中提到: 】
: 在一堆小小小小中间插入了一个“小”（k vs k+1)，而且这个“小”的两边都不是小
:
--
FROM 111.199.188.* - 懂了，赞！
【 在 here080 的大作中提到: 】
: 严格地说就是：
: f(k) = k - 小小相邻的个数
:
--
FROM 111.199.188.* - 说的通俗点
首先每个数都染成黑色，考察f(k)的时候，把1~k都染成白色，然后计算黑色有几“段”，不看每段的长短
比如先看f(1)，只有一段黑色，所以f(1)=1
当从f(k)推算f(k+1)的时候，有三种情况
1) k+1左右都大，那么左右都是黑的，把它染白后，相当于把一段黑色切断，f加1，所以f(k+1)=f(k)+1，交换左右这个操作不改变任何东西
2) k+1左右都小，那么左右都是白的，它这个点本来是一段长度为1的黑色，染白后没有了，f-1，所以f(k+1)=f(k)-1，交换左右这个操作不改变任何东西
3) k+1左右一大一小，这就证到题中的描述，不讨论
那么上面1)2)都会改变f的奇偶性，所以如果始终没有发生上面的3)，那么f(2021)和f(1)的奇偶性应该相同，而f(1)=1，所以f(2021)不能=0
但是由于每步都会染色，最后必然所有的都是白的，f(2021)必须=0，矛盾
【 在 spioner007 的大作中提到: 】
: 没懂
--
FROM 111.199.188.*