第63届IMO竞赛Day1 Problem1题目解答

北京时间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<n的时候，只要让第n个coin与前n-1个不同，前n-1个全部相同，则前n个的coin是不会受操作影响的，更不会相同。

有了这样的启发，我们应当看看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<n 时，命初始序列为：AA…AB X…X,其中前n-1个为A，第n个为B,后面任取即可。当 k＞[(3/2)n] 时，命初始序列为（n≥4）：A…AB…B… … A… AB …B when n is even

其中每一段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的纯组合题的难度大家是不是有初步了解了呢~