第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吧~

每月一讲:IMO正式开赛!从AMC视角挑战Day1纯组合题目!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个都会有所不同即可,当然有循环是最好的,比如:

AABBAABBBBAABBAA→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的纯组合题的难度大家是不是有初步了解了呢~

上一篇

NHD美国国家历史日竞赛National History Day介绍

下一篇

大学生转专业需要达到哪些要求?

你也可能喜欢

评论已经被关闭。

插入图片
商务合作 商务合作
商务合作
在线咨询 在线咨询
在线咨询
返回顶部