北京时间2022年7月10日晚9点，第63届国际数学奥林匹克（IMO）在挪威正式开幕！
IMO2022赛程
| 日期 | 时间 | 内容 |
|---|---|---|
| 7.10 | 21:00 | 开幕式 |
| 7.11 | 比赛第一天DAY1 | |
| 7.12 | 比赛第二天DAY2 | |
| 7.15 | 21:30 | 闭幕式 |
正值IMO比赛期，本月每月一讲让我们一起看一下今年IMO Day1的Problem1吧~
2022IMO Day1， Problem1-3 时间：4小时30分钟
今年的第一天由一个纯组合题，一个代数题和一个组合数论综合题构成，因此第二天应该会有几何5或者几何6出现。
01、今年的这个纯组合第一题，它的难度应当低于USAMO的第2、5题高于第1、4题，笔者将站在一个AMCer的视角和水平上去解决这个问题，给出足够多的思路和细节，希望所有读者都能够读懂它并对组合产生兴趣。
首先，我们可以尝试找一些不满足条件的k:
Case1 n=4, k=2
取初始序列为AABBBBBA，很明显用多少次符合题意的操作都无法让前n(=4)个字母变为相同。从这个Case当中其实我们可以类推或者总结，当k
有了这样的启发，我们应当看看k很大的时候会出现什么情况。
Case2 n=4, k=8
只要交替就能矛盾：ABABABAB。
Case3 n=4, k=7
这种情况的初始列比较难找，但是你可以想象你只要保证每次操作后扔进前4个的东西和原来的前4个都会有所不同即可，当然有循环是最好的，比如：
AABBAABB→BBAABBAA→AABBAABB …
Case4 n=4, k=6
这个Case需要大家尽可能多地尝试，因为它不论什么初始情况，都会经过若干次操作后使得前n个变成相同的。也就是说(4,6)是一组答案，进一步可以发现(4,5)和(4,4) 也是。
现在我们就要去想想这个n和k之间有什么函数关系，可以换个n=5看一下。
Case5 n=5, k=10，
ABABABABAB得到矛盾。
Case6 n=5, k=9
AABBAAABBB→BBBAABBAAA→AAABBBAABB→BBAAABBBAA →AABBAAABBB
Case7 n=5, k=8
经过尝试所有的初始条件都会把前5个变成相同的。同时k=5,6,7也都同这个情况。
总结规律，我们似乎发现当n≤k≤[(3/2)n]时，都是可以通过题目中的operation得到前n个相同，因此，我们首先给头尾两段k构造反例。
02、Solution：
Step I
当k
其中每一段A和B长度都为n/2。
当n为奇数时，找一段A的个数设置为n+1/2即可。
Step II
现在我们来证明，当n≤k≤[(3/2)n]时，任何初始情况都会导致未来前n个变为相同的。由于初始情况的不同有许多种，我们不能直接导出一个初始→最终的关系，因此唯一可以使用的技术就是递降法，或者说，我们利用这些coin中chain的个数m是不增的，把它达到最低的情况列出来，然后看看如果前n个不相同，会得到什么矛盾。
首先m不增为显然，若前n个永远不全相同，则设m变为其最小值后的情形为:…A…AB…B…BA…A……
并假设第k位为B。由于k≥n，第k位前面的A肯定存在，但是由m已经在此时达到最小值，这一段B之后的A应当不存在。
故实际上这个情况是：…A…AB…B…B,此时由于n≤k≤[(3/2)n]，故这段B至少有n-[(3/2)n]+1≥[n/2]+1个。
这样经过一次操作，它前面的A被挤到了最后一段，也要有至少[n/2]+1个，这是不可能的。
以上就是本月每月一讲的内容，IMO的纯组合题的难度大家是不是有初步了解了呢~
【竞赛报名/项目咨询请加微信：mollywei007】
