第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比賽期，本月每月一講讓我們(men) 一起看一下今年IMO Day1的Problem1吧~

2022IMO Day1， Problem1-3 時間：4小時30分鍾

今年的第一天由一個(ge) 純組合題，一個(ge) 代數題和一個(ge) 組合數論綜合題構成，因此第二天應該會(hui) 有幾何5或者幾何6出現。

01、今年的這個(ge) 純組合第一題，它的難度應當低於(yu) USAMO的第2、5題高於(yu) 第1、4題，筆者將站在一個(ge) AMCer的視角和水平上去解決(jue) 這個(ge) 問題，給出足夠多的思路和細節，希望所有讀者都能夠讀懂它並對組合產(chan) 生興(xing) 趣。

首先，我們(men) 可以嚐試找一些不滿足條件的k:

Case1 n=4, k=2

取初始序列為(wei) AABBBBBA，很明顯用多少次符合題意的操作都無法讓前n(=4)個(ge) 字母變為(wei) 相同。從(cong) 這個(ge) Case當中其實我們(men) 可以類推或者總結，當k<n的時候，隻要讓第n個(ge) coin與(yu) 前n-1個(ge) 不同，前n-1個(ge) 全部相同，則前n個(ge) 的coin是不會(hui) 受操作影響的，更不會(hui) 相同。

有了這樣的啟發，我們(men) 應當看看k很大的時候會(hui) 出現什麽(me) 情況。

Case2 n=4, k=8

隻要交替就能矛盾：ABABABAB。

Case3  n=4, k=7

這種情況的初始列比較難找，但是你可以想象你隻要保證每次操作後扔進前4個(ge) 的東(dong) 西和原來的前4個(ge) 都會(hui) 有所不同即可，當然有循環是最好的，比如：

AABBAABB→BBAABBAA→AABBAABB …

Case4  n=4, k=6

這個(ge) Case需要大家盡可能多地嚐試，因為(wei) 它不論什麽(me) 初始情況，都會(hui) 經過若幹次操作後使得前n個(ge) 變成相同的。也就是說(4,6)是一組答案，進一步可以發現(4,5)和(4,4) 也是。

現在我們(men) 就要去想想這個(ge) n和k之間有什麽(me) 函數關(guan) 係，可以換個(ge) n=5看一下。

Case5 n=5, k=10，

ABABABABAB得到矛盾。

Case6 n=5, k=9

AABBAAABBB→BBBAABBAAA→AAABBBAABB→BBAAABBBAA →AABBAAABBB

Case7 n=5, k=8

經過嚐試所有的初始條件都會(hui) 把前5個(ge) 變成相同的。同時k=5,6,7也都同這個(ge) 情況。

總結規律，我們(men) 似乎發現當n≤k≤[(3/2)n]時，都是可以通過題目中的operation得到前n個(ge) 相同，因此，我們(men) 首先給頭尾兩(liang) 段k構造反例。

02、Solution：

Step I 

當k<n 時，命初始序列為(wei) ：AA…AB X…X,其中前n-1個(ge) 為(wei) A，第n個(ge) 為(wei) B,後麵任取即可。當 k＞[(3/2)n] 時，命初始序列為(wei) （n≥4）：A…AB…B… … A… AB …B when n is even

其中每一段A和B長度都為(wei) n/2。

當n為(wei) 奇數時，找一段A的個(ge) 數設置為(wei) n+1/2即可。

Step II

現在我們(men) 來證明，當n≤k≤[(3/2)n]時，任何初始情況都會(hui) 導致未來前n個(ge) 變為(wei) 相同的。由於(yu) 初始情況的不同有許多種，我們(men) 不能直接導出一個(ge) 初始→最終的關(guan) 係，因此唯一可以使用的技術就是遞降法，或者說，我們(men) 利用這些coin中chain的個(ge) 數m是不增的，把它達到最低的情況列出來，然後看看如果前n個(ge) 不相同，會(hui) 得到什麽(me) 矛盾。

首先m不增為(wei) 顯然，若前n個(ge) 永遠不全相同，則設m變為(wei) 其最小值後的情形為(wei) :…A…AB…B…BA…A……

並假設第k位為(wei) B。由於(yu) k≥n，第k位前麵的A肯定存在，但是由m已經在此時達到最小值，這一段B之後的A應當不存在。

故實際上這個(ge) 情況是：…A…AB…B…B,此時由於(yu) n≤k≤[(3/2)n]，故這段B至少有n-[(3/2)n]+1≥[n/2]+1個(ge) 。

這樣經過一次操作，它前麵的A被擠到了最後一段，也要有至少[n/2]+1個(ge) ，這是不可能的。

以上就是本月每月一講的內(nei) 容，IMO的純組合題的難度大家是不是有初步了解了呢~