Научно-методически статии
ВЪРХУ ЗАДАЧА 3 ОТ МЕЖДУНАРОДНАТА ОЛИМПИАДА ПО МАТЕМАТИКА 2024 ГОДИНА
https://doi.org/10.53656/math2024-6-1-ont
Резюме. Статията е посветена на решаването на Задача 3 от Международната олимпиада по математика (МОМ) 2024. Задачата е с много проста формулировка и изглежда измамно лесна, но тя затрудни много от участниците, включително българските състезатели. Тук представяме по-различен модел на процеса, на езика на ориентираните графи, което опростява ключовите доказателства.
Ключови думи: безкрайна редица; периодична редица; ориентиран граф; безкраен път
1. Увод
В тази статия ще разгледаме Задача 3 от Международната олимпиада по математика (МОМ) през \(2024{ }^{1}\). Тя затрудни участниците, включително българските състезатели. Имаше само 8 пълни решения. Задачата е с много проста формулировка и изглежда измамно лесна. Дадени са краен брой естествени числа, наредени в редица. Започвате да добавяте числа в края на редицата, като всяко следващо е равно на броя на повторенията на предишното. Трябва да докажете, че има закономерност в този процес. Много бързо човек се ориентира какво се случва, достатъчни са няколко опита. Но е много трудно наблюденията да се докажат строго. Трудността идва от факта, че броят на повторенията на дадено число не присъства като обект в постановката. За да се получи това число, трябва се върнете от началото на редицата и да започнете да броите. С други думи, като разписваме редицата, ние алтернативно преминаваме от едно нейно локално свойство – последния член, към глобално свойство – броя на повторенията му в редицата досега. Това затруднява доказването на иначе лесните наблюдения.
Тук ще представим малко по-различен модел на процеса, на езика на ориентираните графи (Diestel 2017), като броят на повторенията ще бъде равен на броя на ребрата, входящи в даден връх, а самата редица се разглежда като един безкраен ориентиран пzm \(P\) по върховете на ориентирания граф. Развитието на \(P\) вече се определя само от негови локални свойства – последния връх и броя на входящите в него ребра.
2. Задача 3 от Международната олимпиада по математика 2024
Задача 3 (Австралия). Нека \(a_{1}, a_{2}, \ldots, a_{n}, \ldots\) е безкрайна редица от цели положителни числа и нека \(N\) е цяло положително число. Дадено е, че за всяко \(n \gt N\), числото \(a_{n}\) е равно на броя срещания на числото \(a_{n-1}\) в редицата \(a_{1}, a_{2}, \ldots, a_{n-1}\). Да се докаже, че поне една от редиците \(a_{1}, a_{3}, a_{5}, \ldots\) и \(a_{2}, a_{4}, a_{6}, \ldots\) е периодична от известно място нататък.
Забележка: Eдна безкрайна редица \(b_{1}, b_{2}, \ldots, b_{n}, \ldots\) е периодична от известно място нататък, с период \(p\), ако съществуват цели положителни числа \(p\) и \(M\), такива че \(b_{m+p}=b_{m}\) за всяко \(m \geq M\).
Решение. Ще интерпретираме задачата по начин, който да ни позволи по-лесно да визуализираме колко пъти се повтаря дадено число от редицата. Развитието на редицата представяме посредством ориентиран граф с върхове естествените числа, като добавяме още един фиктивен връх \(a_{0}\). Да означим \(I=\left\{a_{1}, a_{2}, \ldots, a_{N}\right\}\). Нека отначало множеството от върхове на построявания граф е \(a_{0} \cup I\). За всеки връх \(i \in I\), свързваме \(a_{0}\) с \(i\) с толкова на брой ориентирани ребра (\(a_{0}, i\) ), колкото пъти \(i\) се повтаря в \(a_{1}, a_{2}, \ldots, a_{N}\). Дотук сме си осигурили, че броят входящи ребра във всеки връх \(i \in I\) е равен на броя на повторенията на \(i\) в редицата \(a_{1}, a_{2}, \ldots, a_{N}\). Да означим този граф с \(G(0)\) и нека текущият връх бъде \(c(1)=a_{N}\).
За даден ориентиран граф \(G, \mathrm{c} \mathrm{deg}_{G}^{-}(v)\) означаваме броя на влизащите във върха \(v\) ребра – полустепен на входа за върха \(v\) в \(G\).
Оттук нататък процесът е следният. На всяка следваща стъпка \(t=1,2, \ldots\) преброяваме колко ребра влизат във върха \(c(t)\) в графа \(G(t-1)\), т.е. определяме \(d=\operatorname{deg}_{G(t-1)}^{-}(c(t))\), след което добавяме ориентирано ребро \((c(t), d)\) от върха \(c(t)\) към върха \(d\). Така получаваме графa \(G(t)\). Текущ връх става \(c(t+1)=d\) и повтаряме процедурата.
Двойките \((G(t), c(t))\) характеризират нашата редица. Да означим интересуващия ни граф с \(G=\lim _{t \rightarrow \infty} G(t)\). Можем да разглеждаме зададената редица като безкраен ориентиран \(n ъ m\) в така построения граф \(G\). Този път може да посети някои от върховете на \(G\) по няколко (възможно безкрайно много) пъти. Да означим този път с \(P\). Ще докажем твърдението на задачата в три стъпки.
Твърдение 1. Нека \(M=\max \left(a_{1}, a_{2}, \ldots, a_{N}\right)\). Във всеки връх на \(G\) със стойност, по-голяма от \(M\), влизат не повече от \(M\) ребра.
Доказателство. Да допуснем, че твърдението не е вярно, и нека \(t\) е първата стъпка, в която в редицата се появява връх \(m, m \in \mathbb{N}, m \gt M\), за който \(\operatorname{deg}_{G(t)}^{-}(m) \gt M\). Ясно е, че \(m \notin G(0)\), така че няма ориентирано ребро от \(a_{0}\) към \(m\). И така, в \(m\) влизат повече от \(M\) ребра в графа \(G(t)\). Нека това са ребра, излизащи от върховете \(i_{1}, i_{2}, \ldots, i_{s}, s \gt M\). Едно от числата, съответстващо на тези върхове, да го означим с \(m_{0}\), е по-голямо от \(M\). За да е построено реброто \(\left(m_{0}, m\right)\), във върха \(m_{0}\) влизат поне \(m \gt M\) ребра. Т.е. \(G(t)\) не е първият граф, в който се появява връх, по-голям от \(M\), в който влизат повече от \(M\) ребра – противоречие.
Твърдение 2. Съществува \(\ell \in \mathbb{N}\), така че пътят \(P\), определен от \(G\), алтернативно се движи между върхове в \(\{1,2, \ldots, \ell\}\) и върхове, които са по-големи като стойност от \(M\).
Доказателство. Нека отбележим, че пътят \(P\) минава през безкраен брой различни върхове на \(G\). Наистина, ако допуснем, че \(P\) преминава през краен брой върхове, то броят ребра, които влизат в един от тях, ще нараства до безкрайност, което означава, че от този връх ще излизат ребра към всички достатъчно големи естествени числа, противоречие. Съгласно Твърдение 1, когато \(P\) стигне до връх със стойност, по-голяма от \(M\), той се връща във връх със стойност не повече от \(M\). Това означава, че \(P\) влиза безброй много пъти в множеството от върхове със стойност, не по-голяма от \(M\). Следователно \(P\) минава безброй много пъти през поне един от тези върхове. Да забележим също, че ако \(P\) минава безброй много пъти през връх \(v_{k}, k \gt 1\), то \(P\) минава през \(v_{k-1}\) също безброй пъти. Наистина, нека в \(G\) има ребра \(\left(n_{1}, k\right),\left(n_{2}, k\right), \ldots\) Това означава, че в \(n_{i}, i=1,2, \ldots\) влизат поне \(k\) ребра. Значи в някой момент \(n_{i}\) е бил текущ връх с входящи \(k-1\) ребра, т.е. на следващата стъпка се появява ребро (\(n_{i}, k-1\) ). Следователно \(P\) минава безброй много пъти през \(k-1\).
Нека \(\ell\) е най-голямото естествено такова число, че \(P\) минава безкраен брой пъти през \(\ell\). От твърдение 1 имаме, че \(\ell \leq M\). Да означим \(L=\{1,2, \ldots, \ell\}\) и \(M=\{n \in \mathbb{N}, n \gt M\}\). Ребрата, които излизат от върховете \(\ell+1, \ell+2, \ldots, M\) са краен брой поради избора на \(\ell\). Ребрата, които свързват два върха от \(L\) също са краен брой. Следователно от някой момент \(T\) нататък \(P\) ще минава само през върхове от множеството \(L \cup M\) и няма да има два последователни върха от \(L\). Това означава, че в пгтя \(P\) алтернативно ще се редуват връх от \(L\) и връх от \(M\), защото след връх от \(M\) не може да следва пак връх от \(M\) поради Твърдение 1.□
Твърдение 2 показва, че върхът \(n\), за достатъчно големи \(n\), е свързан (изходящо и входящо) само с върхове от \(L\). Нека за всеки един момент \(t\) даот вър ознахчима \(n\) ребро с \(g_{n}(t)\) внай-голямото графа \(G(t)\). Забележ число (връх),ете, че к \(g_{n}(t+1)-g_{n}(t) \in\{0,1\}\)оето е край на изходящо , като \(g_{n}(t+1)=g_{n}(t)+1\) точно когато \(n\) е текущ връх в \(G(t+1)\).
От Твърдение 2 следва, че \(g_{n}(t)\), като функция на \(t\), расте неограничено за \(n=1,2, \ldots, \ell\), 2,...,ℓ, а \(g_{n}(t)\) при \(n \gt \ell\) е константа от някое \(t\) нататък. Да разгледаме наредената \(\ell\)-торка
(1)\[ S(t):=\left(g_{1}(t), g_{2}(t), \ldots, g_{\ell}(t)\right) \]
За по-кратко да означим наредената \(\ell\)-торка в (1) с \(S=\left(g_{1}, g_{2}, \ldots, g_{\ell}\right)\), като имаме предвид, че тези числа зависят от \(t\). Да наредим тази \(\ell\)-торка \(g_{i_{1}} \geq g_{i_{2}} \geq \cdots \geq g_{i_{\ell}}\). Забележете, че във всеки връх \(n\), за който е в сила \(g_{i_{2}} \lt n \leq g_{i_{1}}\), влиза само едно ребро – това, което излиза от \(i_{1}\). По същия начин, във върха \(n\) за \(g_{j+1} \lt n \leq g_{j}, j=1,2, \ldots, \ell-1\) влизат точно \(j\) ребра – тези, които излизат от върховете \(i_{1}, i_{2}, \ldots, i_{j}\).
Основната идея. Ако в два последователни момента \(t_{1}\) и \(t_{2}\), такива че \(T \lt t_{1} \lt t_{2}\), графите \(G\left(t_{1}\right)\) и \(G\left(t_{2}\right)\) имат един и същ текущ връх \(c\left(t_{1}\right)=c\left(t_{2}\right) \in L\), като \(S\left(t_{2}\right)=\left(g_{1}^{\prime}, g_{2}^{\prime}, \ldots, g_{\ell}^{\prime}\right)\) се получава, като транслираме \(S\left(t_{1}\right)=\left(g_{1}, g_{2}, \ldots, g_{\ell}\right)\), то от момента \(t_{1}\) нататък \(P\) влиза в \(L\) по периодичен начин. В първоначалната задача това означава, че \(a\left(t_{1}+2 i\right), i \in \mathbb{N}\) е периодична.
Доказателство. От казаното по-горе, входящите ребра към \(g_{i}\) и \(g_{i}^{\prime}, i=1,2, \ldots, \ell\) съответно в \(G\left(t_{1}\right)\) и \(G\left(t_{2}\right)\) са равни. Значи в съответните стъпки след \(t_{1}\) и \(t_{2}\) пътят \(P\) ще влиза в едни и същи върхове в \(L\). □
За да докажем, че има две повтарящи се отместени конфигурации \(S\left(t_{1}\right)\) и \(S\left(t_{2}\right)\), ни трябва и следното
Твърдение 3. \(\max _{1 \leq i \leq \ell}\left(g_{i}(t)\right)-\min _{1 \leq i \leq \ell}\left(g_{i}(t)\right) \leq C\) за някаква константа \(C \gt 0\).
Доказателство. Нека в момента \(T\) имаме \(S(T)=g_{i_{1}} \geq g_{i_{2}} \geq \cdots \geq g_{i_{\ell}}\), а в момента \(t\) имаме \(S(t)=g_{i_{1}}^{\prime} \geq g_{i_{2}}^{\prime} \geq \cdots \geq g_{i_{\ell}}^{\prime}\). Да фиксираме \(k, 1 \lt k \leq \ell\) и нека \(g_{i_{k}}^{\prime}-g_{i_{k-1}}^{\prime}=\Delta\). Ще докажем, че \(\Delta\) не може да става твърде голямо. Да оценим колко ребра излизат от върховете \(1,2, \ldots, \ell\). Броят ребра, влизащи в \(j \in[1 . . \ell]\) в графа \(G(t)\), е равен на броя ребра, влизащи в \(j \in[1 . . \ell]\) в графа \(G(T)\), плюс \(g_{i_{j}}^{\prime}-g_{i_{j}}\). Това е така, защото от всеки от върховете в \(M\), които са в интервала (\(g_{i_{j}}, g_{i_{j}}^{\prime}\) ), излиза точно едно ребро към \(j\) в графа \(G(t)-G(T)\). Значи
(2)\[ g_{j}^{\prime}=g_{j}+\left(g_{i_{j}}^{\prime}-g_{i_{j}}\right) \]
Нека \(A=g_{i_{1}}-g_{i_{\ell}}\). Забележете, че \(A\) е константа, независеща от \(t\). За кои да е \(s \in[1 . . k]\) и \(r \in[k+1 . . \ell]\) от (2) получаваме \[ g_{s}^{\prime}-g_{r}^{\prime} \geq \Delta-A \] Ако допуснем, че в даден момент \(t\) имаме \(\Delta \gt A\), то тогава \(g_{1}^{\prime}, g_{2}^{\prime}, \ldots, g_{k}^{\prime}\) са най-големите измежду числата във вектора \(S(t)\). Следователно от момента \(t\) нататък всяко ребро, което излиза от \(g_{1}^{\prime}, g_{2}^{\prime}, \ldots, g_{k}^{\prime}\), ще влиза в някой от върховете \(1,2, \ldots, k\) и всяко ребро, което излиза от тези върхове, ще влиза във връх от \(M\), по-голям от \(\min \left(g_{1}^{\prime}, g_{2}^{\prime}, \ldots, g_{k}^{\prime}\right)\). Значи, пбтят \(P\), след момента \(t\), ще влиза само във върховете от \(L\) измежду \(1,2, \ldots, k\), противоречие. Следователно \(\Delta \leq A\), което означава, че
\[ \max _{1 \leq i \leq \ell}\left(g_{i}(t)\right)-\min _{1 \leq i \leq \ell}\left(g_{i}(t)\right) \leq C=(\ell-1) A . \]
След като доказахме Твърдение 3, остава последната стъпка. За дадена \(\ell\)-торка \(g_{1}(t), g_{2}(t), \ldots, g_{\ell}(t)\) да означим
\[ d_{i}(t)=g_{i+1}(t)-g_{i}(t), i=1,2, \ldots, \ell-1 \] Имаме безкраен брой \(\ell\)-торки \(\left(d_{1}(t), d_{2}(t), \ldots, d_{\ell-1}(t), c(t)\right)\), където \(c(t)\) е текущият връх в \(L\) (за онези \(t\), за които текущият връх е в \(L\) ). Съгласно Твърдение 3 тези \(\ell\)-торки са ограничени от константа, следователно ще има два момента \(t_{1}\) и \(t_{2}\), в които ще се повторят. Както споменахме, това означава, че в съответните стъпки след \(t_{1}\) и \(t_{2}\) пътят \(P\) ще влиза в едни и същи върхове в \(L\). И така, след момента \(t_{1}\) начинът, по който \(P\) влиза в \(L\), ще се повтаря с период \(t_{2}-t_{1}\).
Като се върнем към първоначалната задача, окончателно установихме, че \(a\left(t_{1}+2 t\right), t \in \mathbb{N}\) е периодична.□
3. По-нататък по задачата
Би могло да се установи нещо повече за редицата \(a\left(t_{1}+2 t\right), t \in \mathbb{N}\) освен факта, че е периодична. А именно, тя е периодична с период \(\ell\), като повтарящите се числа са някаква пермутация на числата от 1 до \(\ell\). Това не беше част от условието – и без това задачата се оказа много трудна. Нека го докажем. За мултимножество \(S\) от краен брой реални числа (т.е. елементите на \(S\) не са непременно различни) и \(x \in \mathbb{R}\) да въведем означението
\[ u_{S}(x)=\#\{y \in S: y \geq x\} \] т.е. \(u_{S}(x)\) е броят на числата в \(S\) (с повторенията), които са по-големи или равни на \(x\). Нека \(G=G(t)\) е граф с текущ връх от множеството \(M\), а \(S\) е \(\ell\)-торката, дефинирана в (1). Означението по-горе го въведохме за по-кратък запис на факта:
(3)\[ d_{G}(m)=u_{S}(m), \forall m \in M \]
Лема. Нека \(S_{1}\) и \(S_{2}\) са двe мултимножества, като \(S_{2} \neq \emptyset\). Да означим \(S_{2}^{\prime}=\left\{x+1 \mid x \in S_{2}\right\}, S=S_{1} \cup S_{2}\) и \(S^{\prime}:=S_{1} \cup S_{2}^{\prime}\). Нека \(x \in S_{1}, y \in S_{2}^{\prime}\). Тогава
\[ u_{S}(x) \neq u_{S^{\prime}}(y) \]
Доказателството е тривиално.□ Да разгледаме сега редицата \(b(t)=a\left(t_{1}+2 t\right), t \in \mathbb{N}\), за която знаем, че е периодична. Нека \(s \in \mathbb{N}\) е такова, че \(b(s+1), b(s+2), \ldots, b(s+k)\) са различни числа и \(b(s+k+1)=b(s+1)\). Ще докажем, че \(b(s)\) е равно на някое от числата \(b(s+1), b(s+2), \ldots, b(s+k)\). Нека допуснем противното. Да разгледаме момента \(t:=s\) и съответния граф \(G(t)\), т.е. графът в момента, в който пътят \(P\) е излязъл от \(b(s)\) чрез реброто \(\left(b(s), g_{b(s)}(t)\right)\).
Да означим
\[ S=\left(g_{1}(t), g_{2}(t), \ldots, g_{\ell}(t)\right) ; S_{2}=\left(g_{b(s+1)}(t), g_{b(s+2)}(t), \ldots, g_{b(s+k)}(t)\right) \] и нека \(S_{1}=S \backslash S_{2}\). Поради допускането, \(g_{b(s)}(t) \in S_{1}\). Нека сега разгледаме момента \(t^{\prime}=s+k\) и съответния граф \(G\left(t^{\prime}\right)\), т.е. графът в момента, в който \(P\) излиза от \(b(s+k)\) чрез ориентираното ребро \(\left(b(s+k), g_{b(s+k)}\left(t^{\prime}\right)\right)\). Аналогично, да означим \[ S^{\prime}=\left(g_{1}\left(t^{\prime}\right), g_{2}\left(t^{\prime}\right), \ldots, g_{\ell}\left(t^{\prime}\right)\right) ; S_{2}^{\prime}=\left(g_{b(s+1)}\left(t^{\prime}\right), g_{b(s+2)}\left(t^{\prime}\right), \ldots, g_{b(s+k)}\left(t^{\prime}\right)\right) \] Тъй като \(b(s+i), i=1,2, \ldots, k\) са различни, ясно е, че
\[ g_{b(s+i)}\left(t^{\prime}\right)=g_{b(s+i)}(t)+1, i=1,2, \ldots, k \] Лесно се вижда, че \(S^{\prime}=S_{1} \cup S_{2}^{\prime}\). От \(b(s+1)=b(s+k+1)\) и ( (3) следва:
\[ u_{S}\left(g_{b(s)}(t)\right)=u_{S^{\prime}}\left(g_{b(s+k)}\left(t^{\prime}\right)\right) \] което е невъзможно съгласно Лема 1, противоречие. И така, \(b(s)\) е равно на някое от числата \(b(s+i), i=1,2, \ldots, k\).
Нека сега \(k\) е минималното число, за което съществува \(s \in \mathbb{N}\), такова, че \(b(s+1), b(s+2), \ldots, b(s+k)\) са различни числа и \(b(s+k+1)=b(s+1)\). Съгласно казаното, \(b(s)\) е равно на някое от числата \(b(s+i), i=1,2, \ldots, k\). Ако допуснем, че \(b(s)=b(s+i)\) за \(1 \leq i \lt k\), това ще противоречи на минималността на \(k\). Следователно \(b(s)=b(s+k)\).
Да забележим, че \(b(s), b(s+1), \ldots, b(s+k-1)\) също са \(k\) поредни различни члена на редицата (b) и \(b(s)=b(s+k)\). Същите аргументи показват, че \(b(s-1)=b(s+k-1)\). Продължавайки нататък, получаваме: \(b(s-i)=b(s-i+k)\) за \(i=0,1, \ldots, s-1\). Като вземем \(s\) достатъчно голямо, установяваме, че периодът на редицата (b) е \(k\). Тъй като всяко от числата в \([1 . . \ell]\) трябва да участва в периода, значи \(k=\ell\) и периодът на (b) е пермутация на числата в [1..ℓ].
4. Коментар по задачата и нейното оценяването на МОМ 2024 Схемата за оценяване на тази задача беше доста пестелива. Не се даваха точки за сравнително лесни наблюдения. Една точка се даваше за доказване, че има число, което се повтаря само краен брой пъти в редицата. Т.е. за малко по-слабо нещо от еквивалента на Твърдение 1, което в контекста на задачата означава, че всички достатъчно големи числа се повтарят само краен брой пъти.
Две точки се даваха за доказване на еквивалента на Твърдение 2, че от някое място нататък в редицата алтернативно се редуват числа, по-малки от \(\ell\), и числа, по-големи от \(M\). От тук нататък идеята за доказване периодичността на малките числа е рутинна. Обаче има една техническа пречка – доказването на Твърдение 3. Това според мен е най-трудната част от задачата. Едно по-различно доказателство на тази част може да намерите в (Grozev 2024). И така, ако си доказал Твърдение 2 и имаш две точки, знаеш, че има едни малки числа, от 1 до \(\ell\), които се повтарят безкраен брой пъти и други такива няма. Ако се фокусираме на честотата на срещания на всяко малко число към определен момент, имаме един набор от \(\ell\) големи числа, който се променя. За да получим периодичност на малките числа, ни трябва сходство между два набора големи числа. Сходството е възможно само ако разликата между най-голямото и най-малкото в набора големи числа е ограничена от константа. Т.е., ако техните относителни разлики не варират много. Мисля, че за това ниво състезатели, всеки, получил две точки, е знаел какво трябва да се направи след това. Но на пътя към пет допълнителни точки е стояло Твърдение 3 (неговият еквивалент).
В интерпретацията на тази статия, това твърдение сякаш е по-лесно. Човек вижда нагледно, че ако има голяма разлика между набор големи числа към даден момент, то има голяма разлика между броя входящи ребра, влизащи в първите няколко от малките числа, и тези, влизащи в останалите малки числа. Същото ще важи и за съответните изходящи ребра. Но тогава, крайните точки на ребрата, излизащи от тях в този момент, ще са изпреварили много останалите, което значи, че само първите няколко от малките числа ще се повтарят безкраен брой пъти.
NOTES
1. IMO 2024 Problems and solutions: https://www.imo2024.uk/solutions
REFERENCES
DIESTEL, R., 2017. Graph Theory. Springer. ISBN 978-3-662-53622-3.
GROZEV, D., 2024. A Point of View (Blog).
https://dgrozev.wordpress.com