Драгомир Грозев

Institute of Mathematics and Informatics
Bulgarian Academy of Sciences
Sofia Bulgaria
ORCiD: 0009-0004-6365-2388
E-mail: drago.grozev@gmail.com

Станислав Харизанов

Institute of Mathematics and Informatics
Bulgarian Academy of Sciences
Sofia Bulgaria
ORCiD: 0000-0002-7109-7247
E-mail: sharizanov@gmail.com

https://doi.org/10.53656/math2025-3-1-mss

Резюме. Показани са приложения на вероятностния метод в комбинаторни задачи. В повечето източници конструирането на вероятностно пространство е естествено и тривиално и като следствие се доказва съществуване на определени обекти. Акцентът тук е върху конструиране на подходящо вероятностно пространство. В една от задачите процесът е дори обратен – вероятностни свойства на обекти ни водят до построяване на пример за вероятностно пространство – конструкция, която всъщност се търси. Разгледани са три приложения на метода – две задачи от тазгодишни български състезания: областен кръг НОМ 2025, задача 10.3 и НЗМС 2025, задача 10.3, която е обобщена, както и задача 5 от МОМ 2023. На авторите не е известно решение на последната, използващо такъв подход.

Ключови думи: комбинаторика; вероятностен метод; вероятностно пространство; олимпиадни задачи; Национална олимпиада по математика; Международна олимпиада по математика

1. Въведение

В тази статия прилагаме така известния „вероятностен подход“ за решаването на няколко комбинаторни задачи от престижни състезания. Този метод започва системно да се прилага от Пол Ердьош в средата на миналия век (Erdös 1961; Erdös 1973). Става популярен, тъй като с помощта на методи от теория на вероятностите лесно са били решени някои отворени по онова време проблеми. Така например е получена добра долна граница на числото на Рамзи \(R(k, k) \gt 2^{k / 2-1}\), представена от Ердьош в (Erdös 1947).

Основните методи, използвани при прилагане на вероятностния подход в комбинаторни задачи, са два.

• Ако вероятността дадена конфигурация да се случи, е положителна, то има ситуация, в която конфигурацията е налице.

• Ако математическото очакване на случайната величина \(X\) е \(m\), то \(X\) приема както поне една стойност, по-голяма или равна на \(m\), така и поне една стойност, по-малка или равна на \(m\).

Тези два подхода могат да се прилагат, когато искаме да докажем съществуване на обект с определени свойства. При първия подход, ако успеем да интерпретираме комбинаторната ситуация като вероятностно пространство, в което появяването на обекта има положителна вероятност, то това означава, че такъв съществува. При втория подход свойството на обекта е реална величина, която може да бъде измерена. Ако лесно може да намерим ”усреднената” стойност \(m\) на тази величина (математическото очакване), то това доказва съществуване на обекти, за които тази стойност е по-голяма или равна на \(m\), както и такива, за които стойността е по-малка или равна на \(m\).

Има и по-сложни техники, но тези два стохастични подхода са масово използвани. Основното им предимство е неявното конструиране на примери и контрапримери, за разлика от детерминистичните подходи, което често води до по-кратки и елегантни решения на комбинаторните задачи.

За по-обстойно запознаване с прилагането на вероятностния метод в oлимпиадни комбинаторни задачи, бихме препоръчали (Chen, Evan 2014) и (Loh, Po-Shen 2010). За по-напреднали читатели книгата (Alon, N,. Spencer J. 2008) е едно задълбочено изследване.

Тази статия е предназначена за ученици, които се занимават активно с олимпиадна математика, както и за учители, които водят школи с тази насоченост, защото ще им донесе нов опит. Считаме, че това ще е интересно и на всички, които обичат математика.

Структурата на текста е, както следва. В раздел 2 започваме с някои основни понятия от теория на вероятностите, представяйки накратко необходимата теория. Като илюстрации, в раздел 3 са решени две задачи, давани на национални български състезания през тази година – задача 10.3 от Националното зимно математическо състезание (НЗМС) и задача 10.3. от областния кръг на Националната олимпиада по математика (НОМ), а в раздел 4 е решена задача 5 от Международната олимпиада по математика (МОМ) през 2023.

2. Дефиниции и свойства

За пълнота, тук изброяваме накратко основните понятия, които ще ползваме във втората част на статията. Изчерпателно изложение на темата може да се намери във (Feller 1991).

Дефиниция. Крайно вероятностно пространство е двойката (\(\Omega, P\) където \(\Omega=\cup_{i=1}^{n}\left\{\omega_{i}\right\}\) е множество от краен брой обекти \(\omega_{i}, 1 \leq i \leq n\) наричани елементарни събития, а \(P: \Omega \rightarrow[0,1]\) се нарича вероятностна мярка, за която \(\sum_{i=1}^{n} P\left(\omega_{i}\right)=1\).

Гледаме на \(P(\omega), \omega \in \Omega\) като вероятността да се случи елементарното събитие \(\omega\).

Всяко подмножество \(A\) на \(\Omega\) наричаме събитие. Вероятността да се случи събитието \(A\), е равна на сумата на вероятностите на елементарните събития, от които се състои \(A\), т.е. \(P(A)=\sum_{\omega \in A} P(\omega)\).

Две събития \(A\) и \(B\) се наричат независими, когато

\[ P(A \cap B)=P(A) \cdot P(B) . \] Вероятността да се случи събитието \(B\), при условие че вече се е случило събитието \(A\), наричаме условна вероятност и бележим с \(P(B \mid A)\).

В сила е

\[ P(B \mid A)=\tfrac{P(A \cap B)}{P(A)} \]

Дефиниция. Нека е дадено крайно вероятностно пространство (\(\Omega, P\) ). Функцията \(X: \Omega \rightarrow \mathbb{R}\) наричаме случайна величина.

В дискретния случай вероятността случайната величина \(X\) да приема определена стойност \(x \in \mathbb{R}\), е равна на

\[ P(X=x)=P(\{\omega: \omega \in \Omega, X(\omega)=x\}) . \]

Да отбележим, че \(X\) приема само краен брой стойности, тъй като елементарните събития в \(\Omega\) са краен брой.

Забележка. Тъй като тук разглеждаме само комбинаторни конфигурации от краен брой обекти, съответните вероятностни пространства са крайни и горната дефиниция напълно ни удовлетворява. В общия случай, възможните събития не са всичките подмножества на \(\Omega\), а само част от тях. Тази фамилия \(\mathcal{F}\) от подмножества на \(\Omega\) трябва да е затворена по отношение на вземане на допълнение на множество в \(\mathcal{F}\), както и по отношение на обединение на изброим брой елементи на \(\mathcal{F}\). Такава фамилия се нарича \(\sigma\) алгебра, а множествата в нея се наричат измерими. Вероятностната мярка е дефинирана само върху измеримите множества. Случайната величина в този случай не е каква да е функция \(X: \Omega \rightarrow \mathbb{R}\), а трябва да е измерима функция, т.е. \(X^{-1}((a, b)) \in \mathcal{F}\) за всеки отворен интервал \((a, b)\).

Сума и произведение на две случайни величини \(X, Y\), дефинирани в едно и също вероятностно пространство, са случайните величини \(X+Y\) и \(X \cdot Y\), дефинирани по естествен начин като

\[ \begin{aligned} (X+Y)(\omega) & :=X(\omega)+Y(\omega), & & \forall \omega \in \Omega, \\ (X \cdot Y)(\omega) & :=X(\omega) \cdot Y(\omega), & & \forall \omega \in \Omega . \end{aligned} \] Умножение на случайна величина \(X\) с реално число \(a \in \mathbb{R}\) се дефинира като \((a X)(\omega):=a X(\omega)\).

Дефиниция. Нека е дадена случайната величина \(X\), която приема стойности от множеството \(\left\{x_{1}, x_{2}, \ldots, x_{m}\right\}\). Математическо очакване на \(X\), означавано с \(\mathbb{E}[X]\), се дефинира по следния начин

\[ \mathbb{E}[X]:=\sum_{j=1}^{n} x_{j} P\left(X=x_{j}\right) \]

Пример. Хвърляме зар. В този случай \(\Omega\) се състои от обединението на 6 елементарни събития, а именно: възможните резултати от хвърлянето. Вероятностната мярка \(P\) приема стойност \(1 / 6\) за всяко от тях. Нека случайната величина \(X\) е равна на броя точки, които се падат. Множеството от стойности, които \(X\) приема, е \(\{1,2, \ldots, 6\}\). Вероятността \(X\) ді приеме стойност \(j, 1 \leq j \leq 6\), е \(1 / 6\). Следователно

\[ \mathbb{E}[X]=\sum_{j=1}^{6} j P(X=j)=\sum_{j=1}^{6} j \tfrac{1}{6}=\tfrac{7}{2} \]

Забележете, че ако \(\mathbb{E}(X)=m\), то \(X\) приема стойности, по-големи или равни на \(m\), както и по-малки или равни на \(m\). Това наблюдение има голямо приложение, както ще видим.

Свойство 1. (Линейност на очакването) Нека \(X_{1}, X_{2}, \ldots, X_{n}\) са случайни величини \(u a_{1}, a_{2}, \ldots a_{n} \in \mathbb{R}\). Изпълнено \(e\)

\[ \mathbb{E}\left[a_{1} X_{1}+a_{2} X_{2}+\cdots+a_{n} X_{n}\right]=a_{1} \mathbb{E}\left[X_{1}\right]+\cdots+a_{n} \mathbb{E}\left[X_{n}\right] \]

3. Приложения в национални състезания

Задача 3.1 (Областен кръг НОМ 2025, 10.3). Аделина и Борис играят турнир от \(k\) мача по тенис на маса, където \(k\) е естествено число. Всеки мач се състои от по 2025 гейма, номерирани \(1,2, \ldots, 2025\). Във всеки гейм има победител. За всеки мач има картонче, на едната страна на което се записват номерата на геймовете, спечелени от Аделина, а на другата – спечелените от Борис. Да се намери най-малкото \(k\) за което е сигурно, че в края на турнира всички \(k\) картончета могат да се поставят на масата така, че всяко от числата \(1,2, \ldots, 2025\) д присъства върху лицевата страна на поне едно картонче.

Решение. Да заменим в условието 2025 с \(n\) и нека \(X=\{1,2, \ldots, n\}\) Имаме \(k\) картончета и на едната страна на \(i\)-тото от тях е записано множество \(A_{i} \subseteq X\), а на другата му страна – множеството \(X \backslash A_{i}\). Искаме така да обърнем картончетата, че обединението на множествата на лицевата им страна да е \(X\). Нека \(K\) е най-малкото \(k \in \mathbb{N}\), за което това винаги може да се направи. Ще докажем, че \(K=\left\lfloor\log _{2} n\right\rfloor+1\).

Първо ще покажем, че \(K \leq\left\lfloor\log _{2} n\right\rfloor+1\). Нека вземем \(k \in \mathbb{N}\) такова, че \(2^{k} \gt n\). Нека обърнем всяко картонче на една от двете му страни с вероятност \(\tfrac{1}{2}\) (независимо едно от друго). За всяко \(i=1,2, \ldots, n\) да означим с \(\theta_{i}\) случайната величина, която е 0, когато числото \(i\) се среща на някое картонче, и 1, ако не се среща на никое. Тогава \(\mathbf{P}\left(\theta_{i}=1\right)=2^{-k}\), така че за математическото очакване на \(\theta_{i}\) имаме \(\mathbb{E}\left[\theta_{i}\right]=2^{-k}\).

Нека \(\theta=\sum_{i=1}^{n} \theta_{i}\). От Свойство 1, следва че

\[ \mathbb{E}[\theta]=\sum_{i=1}^{n} \mathbb{E}\left[\theta_{i}\right]=\tfrac{n}{2^{k}} \lt 1 \]

Тъй като \(\theta\) приема само цели неотрицателни стойности, значи има събитие (разположение на картончетата), за което \(\theta=0\). При това разположение всяко число от \(X\) се среща на лицeватата страна на някое картонче. Следователно \(K \leq\left\lfloor\log _{2} n\right\rfloor+1\).

Нека сега покажем, че в случай, когато \(2^{k} \leq n\), съществуват множества \(A_{i} \subset X\), така че \(B_{1} \cup B_{2} \cup \cdots \cup B_{k} \neq X\) за всеки избор на \(B_{i}\) да бъде или \(A_{i}\) или \(X \backslash A_{i}, i=1,2, \ldots, n\). Това е еквивалентно на

(1)\[ B_{1} \cap B_{2} \cap \cdots \cap B_{k} \neq \emptyset \]

за всеки такъв избор на \(B_{i}\). Достатъчно е да докажем, че такива множества \(A_{i}\) съществуват в случая \(n=2^{k}\). Наистина, множествата \(A_{i}\), които вършат работа за \(n=2^{k}\), ще свършат работа и при \(n \gt 2^{k}\), тъй като (1) ще продължава да е в сила.

Да разгледаме множеството от елементарни събития

\[ \Omega:=\left\{\left(b_{1}, b_{2}, \ldots, b_{k}\right): b_{i} \in\{0,1\}, 1 \leq i \leq k\right\} \] и нека всеки елемент има равна вероятност. Нека разгледаме събитията \(A_{i}:=\left\{b=\left(b_{1}, b_{2}, \ldots, b_{k}\right) \in \Omega: b_{i}=1\right\}\). Очевидно \(\mathbf{P}\left(A_{i}\right)=\mathbf{P}\left(\overline{A_{i}}\right)=1 / 2\) и \(A_{i}, i=1,2, \ldots, k\) са независими. Да вземем събития \(B_{i}\), където за всяко \(i=1,2, \ldots, n, B_{i}\) е или \(A_{i}\), 2,...,n, Bi е или \(\overline{A_{i}}\). От казаното следва

\[ \mathbf{P}\left(B_{1} \cap B_{2} \cap \cdots \cap B_{k}\right)=\mathbf{P}\left(B_{1}\right) \mathbf{P}\left(B_{2}\right) \cdots \mathbf{P}\left(B_{k}\right)=2^{-k} \neq 0 \] Това доказва (1), откъдето \(K \gt \left\lfloor\log _{2} n\right\rfloor\).

Има разнообразни подходи за доказателството на \(K \leq\left\lfloor\log _{2} n\right\rfloor+1\). Най-ефективният сред тях е навярно използването на лаком (greedy) алгоритъм, където обръщаме карта след карта така, че на всяка стъпка поне половината от липсващите до момента числа да са откъм лицевата страна на последната обърната карта. Също така, има и конструктивен подход \({ }^{1}\) при който в явен вид се дава работещо поставяне на база множествата, изписани от двете страни на картите. Лакомият подход не дава ясни идеи как да се реши \(K \gt \left\lfloor\log _{2} n\right\rfloor\), докато представеното по-горе решение, както и конструктивният подход помагат за атакуването и на долната граница. И в двата случая извеждането на долната граница \(\boldsymbol{\epsilon}\) чрез допускане на противното, като при конструктивния подход за всяко поставяне явно се извежда номер, който няма да присъства върху лицевата страна на нито една от картите, докато при вероятностния подход това липсва. Последното прави вероятностния подход по-интуитивен, тъй като благодарение на него директно решаваме поставената задача, без да е необходимо да разширяваме фокуса на изследванията и да анализираме допълнителни причинно-следствени връзки от условието.

Да разгледаме още една задача от тази година, която илюстрира ползите от теорията на вероятностите при решаване на олимпийски задачи.

Задача 3.2 (НЗМС 2025, 10.3). Във връзка с формирането на редовно правителство, Президентът поканил всичките 240 депутати на три отделни консултации, като всеки депутат участвал в точно една консултация и на всяка от консултациите присъствал поне един депутат.

Предстои да се проведат разговори между двойки депутати за обсъждане на консултациите. Възможно ли е те да се проведат така, че да съществува цяло неотрицателно число \(k\) такова, че за всеки двама депутати, участвали в различни консултации, да има точно \(k\) депута ти, участвали в останалата консултация, с които всеки от двамата да разговаря, \(u\) точно \(k\) депутати, участвали в останалата консултация, с които никой от двамата да не разговаря?

Да се намерят всички възможни стойности на \(k\).

Ето същата задача, но формулирана с езика на теория на графите.

Задача 3.3 Даден е триделен граф \(G\left(A_{1}, A_{2}, A_{3}\right)\), за който е изпълнено условието \(\left|A_{1} \cup A_{2} \cup A_{3}\right|=240\). За всяка пермутация (\(i_{1}, i_{2}, i_{3}\) ) на числата \((1,2,3)\) и всеки два върха \(x \in A_{i_{1}}, y \in A_{i_{2}}\) е известно, че има точно \(k\) върха в \(A_{i_{3}}\), които са едновременно свързани с \(x\) и \(y\), и точно \(k\) върха в \(A_{i_{3}}\), които едновременно не са свързани с \(x\) и \(y\). Да се намерят всички възможни стойности на \(k\).

Това, което трябва да направим, е да ограничим стойностите на \(k\), за които такъв граф би могъл да съществува, след което да посочим пример, т.е. направим конструкция на граф, удовлетворяващ всички изисквания, посочени в условието. За първата част теория на вероятностите не е нужна, но ще видим, че за примера тя значително улеснява мотивацията какво да търсим.

Нека оцветим всички ребра на \(G\) в червено, след което да прекараме всички останали ребра и да ги оцветим в синьо. Според условието, както и да изберем два върха от два различни дяла, вероятността връх от третия дял да е свързан с червени ребра с първите два върха, е равна на вероятността да е свързан със сини ребра с всеки от тях. Да изберем за вероятностно пространство всевъзможните тройки върхове \(\left(a_{1}, a_{2}, a_{3}\right), a_{i} \in A_{i}, 1 \leq i \leq 3\), като всяка такава тройка има еднаква вероятност да бъде избрана. Да оценим сега вероятността избрана тройка \(\Delta:=\left(a_{1}, a_{2}, a_{3}\right)\) да е едноцветен триъгълник. Имаме

\[ \begin{aligned} & \mathbf{P}(\Delta \text { е едноцветен })= \\ & =\mathbf{P}\left(a_{1} a_{2} \text { е червен }\right) \mathbf{P}\left(a_{1} a_{3}, a_{2} a_{3} \text { са червени } \mid a_{1} a_{2} \text { е червен }\right) \\ & \quad+\mathbf{P}\left(a_{1} a_{2} \text { е син }\right) \mathbf{P}\left(a_{1} a_{3}, a_{2} a_{3} \text { са сини } \mid a_{1} a_{2} \text { е син }\right) \\ & =\mathbf{P}\left(a_{1} a_{2} \text { е червен }\right) \tfrac{k}{\left|A_{3}\right|}+\mathbf{P}\left(a_{1} a_{2} \text { е син }\right) \tfrac{k}{\left|A_{3}\right|}=\tfrac{k}{\left|A_{3}\right|} \end{aligned} \]

По същия начин се получава, че

\[ \mathbf{P}(\Delta \text { е едноцветен })=\tfrac{k}{\left|A_{1}\right|}=\tfrac{k}{\left|A_{2}\right|}, \]

откъдето следва, че \(\left|A_{1}\right|=\left|A_{2}\right|=\left|A_{3}\right|=80\). Да означим \(p:=k /\left|A_{1}\right|\). Тогава вероятността \(\Delta\) да е едноцветен триъгълник, е равна на \(p\), а вероятността да не е едноцветен, е равна на \(1-p\).

Нека сега оценим по друг начин вероятността триъгълникът \(\Delta\) да не е едноцветен. В този случай две от страните са оцветени в цвят, различен от третата страна. Тази „трета“ страна може да бъде всяка от страните \(a_{1} a_{2}, a_{1} a_{3}, a_{2} a_{3}\), като тези три събития са взаимно изключващи се. Вероятността двете ребра \(a_{1} a_{3}\) и \(a_{2} a_{3}\) да са оцветени в цвета, различен от цвета на \(a_{1} a_{2}\), е точно \(p\), така че вероятността триъгълникът \(\Delta\) да не е едноцветен, е равна на \(3 p\).

И така \(3 p=1-p\), което дава \(p=1 / 4\). Следователно \(k=20\).

Остава да дадем пример на граф, удовлетворяващ условията за \(k=20\). Да си представим, че съществува подходящо вероятностно пространство, в което, като вземем произволен триъгълник \(\Delta\), вероятността коя да е от страните да е оцветена в синьо, съответно червено, е равна на \(1 / 2\) и тези три събития са независими. Тогава вероятността две фиксирани страни на \(\Delta\) да са в даден цвят, е \(1 / 4\). Планът е следният:

1) построяваме такова вероятностно пространство;

2) правим го еквивалентно на пълен триделен граф с еднакъв брой върхове във всеки дял, на който ребрата са оцветени в два цвята, като всеки връх на \(\Delta\) се избира от съответния дял еднакво вероятно и независимо от другите.

Нека

\[ \Omega:=\left\{\Delta=\left(a_{1}, a_{2}, a_{3} ; c_{1}, c_{2}, c_{3}\right): a_{i} \in A_{i}, c_{i} \in\{0,1\}, i=1,2,3\right\} \] където (\(a_{1}, a_{2}, a_{3}\) ) интерпретираме като триъгълник, а \(c_{1}, c_{2}, c_{3}\)– като цветовете съответно на страните \(a_{2} a_{3}, a_{1} a_{3}\) и \(a_{1} a_{2}\) (0 – червено, 1 – синьо). На всеки елемент на \(\Omega\) присвояваме една и съща вероятност. Забележете, че \(c_{1}, c_{2}, c_{3}\) са обвързани със страните на триъгълника, а не с върховете му. За да ги обвържем с върховете, ще въведем ново множество от елементарни събития,

\[ \Omega^{\prime}:=\left\{\Delta=\left(a_{1}, a_{2}, a_{3} ; \varepsilon_{1}, \varepsilon_{2}, \varepsilon_{3}\right): a_{i} \in A_{i}, \varepsilon_{i} \in\{0,1\}, i=1,2,3\right\} . \] В този случай считаме, че \(a_{i} a_{j}\) е оцветен в червено, ако \(\varepsilon_{i}=\varepsilon_{j}\), и в синьо, ако \(\varepsilon_{i} \neq \varepsilon_{j}\). Горният запис може да бъде и във вида: \[ \Omega^{\prime}:=\left\{\Delta=\left(a_{1}, \varepsilon_{1} ; a_{2}, \varepsilon_{2} ; a_{3}, \varepsilon_{3}\right): a_{i} \in A_{i}, \varepsilon_{i} \in\{0,1\}, i=1,2,3\right\} \]

Това ни навежда на мисълта, че на елементите от \(\Omega^{\prime}\) може да гледаме като на двоични низове, единият бит на които е предназначен да определя цвета. Сега трябва да съобразим, че този бит за съответните елементи от \(A_{1}, A_{2}\) и \(A_{3}\) не може да бъде на една и съща позиция, защото тогава от \(\varepsilon_{1}=\varepsilon_{2}\) и \(\varepsilon_{2}=\varepsilon_{3}\) следва \(\varepsilon_{1}=\varepsilon_{3}\), т.е. ако \(a_{1} a_{2}\) и \(a_{2} a_{3}\) са от един и същи цвят, то и \(a_{1} a_{3}\) ще е в същия цвят и съответните събития няма да са независими.

Нека \(A:=\{(x, y, z): x, y, z \in\{0,1\}\}\) и \(A_{1}=A_{2}=A_{3}=A\). Два елемента \(a_{1}=\left(x_{1}, y_{1}, z_{1}\right) \in A_{1}\) и \(a_{2}=\left(x_{2}, y_{2}, z_{2}\right) \in A_{2}\) са свързани с червено ребро, ако \(z_{1}=z_{2}\), а в противен случай са свързани със синьо ребро. Аналогично, \(a_{1}=\left(x_{1}, y_{1}, z_{1}\right) \in A_{1}\) и \(a_{3}=\left(x_{3}, y_{3}, z_{3}\right) \in A_{3}\) са свързани с червено ребро само ако \(y_{1}=y_{3}\); и накрая \(a_{2}=\left(x_{2}, y_{2}, z_{2}\right) \in A_{2}\) и \(a_{3}=\left(x_{3}, y_{3}, z_{3}\right) \in A_{3}\) с. свързани с червено ребро само ако \(x_{2}=x_{3}\).

Избора на \(a_{i} \in A_{i}, i=1,2,3\) дефинираме да е равновероятен и независим. Да разгледаме така дефинираното вероятностно пространство. За произволна пермутация (\(i_{1}, i_{2}, i_{3}\) ) на (\(1,2,3\) ) и фиксирани \(a_{i_{1}} \in A_{i_{1}}\) \(a_{i_{2}} \in A_{i_{2}}\) нека с \(X_{i_{1}, i_{3}}\left(a_{i_{1}}, a_{i_{2}}\right)\) означим събитието реброто \(a_{i_{1}} a_{i_{3}}\) да е червено, a с \(X_{i_{2}, i_{3}}\left(a_{i_{1}}, a_{i_{2}}\right)\)– събитието реброто \(a_{i_{2}} a_{i_{3}}\) да е червено. Лесно се проверява, че всички тези събития са независими и с вероятност \(1 / 2\) Тогава пълният триделен граф \(G\left(A_{1}, A_{2}, A_{3}\right)\) с така дефинираното оцветяване изпълнява условието на задачата и \(\left|A_{i}\right|=8, i=1,2,3\). Ако всеки връх на този граф мултиплицираме по 10, ще получим търсения пример на граф с \(\left|A_{i}\right|=80, i=1,2,3\).

Коментар 1. Разгледаният вероятностен подход при конструирането на примера е приложим винаги когато броя депутати \(N\) се дели на 24. Официалното решение (виж Кортезов, И.) на задачата прилага конструкция, работеща в по-общия случай, когато \(N\) се дели на 12, и доказваща, че \(k=N / 12\) винаги се реализира. Така, предложеното в статията решение не покрива числата от вида \(N \equiv 12(\bmod 24)\), но е приложимо за конкретната стойност \(N=240\) в условието на задачата.

Коментар 2. Идеята за доказателството на първата част може да се разглежда, в известен смисъл, като дискретен вариант на следната класическа задача: Каква е вероятността да получим остроъгълен триъгълник, когато разположим по случаен начин три точки върху окръжност \(\Gamma\) ?

Наистина, лесно се съобразява, че вероятността триъгълникът да е правоъгълен, е равна на нула. Нека сега сме поставили три точки \(A, B, C\) върху Γ, така че \(\triangle A B C\) е остроъгълен.

Да построим диаметрално противоположните точки \(A^{\prime}, B^{\prime}, C^{\prime}\) съответно на \(A, B, C\). Триъгълниците \(A B C\) и \(A^{\prime} B C\) нямат общи вътрешни точки, а споделят единствено отсечката \(B C\). Тъй като \(\triangle A B C\) е остроъгълен, то центърът \(O\) на \(\Gamma\) не лежи върху \(B C\), а е вътрешна точка за него. Следователно точката \(O\) е извън \(\triangle A^{\prime} B C\) и той е тъпоъгълен. Аналогично, триъгълниците \(A B^{\prime} C\) и \(A B C^{\prime}\) също са тъпоъгълни. Конфигурацията \(\left\{A, B, C, A^{\prime}, B^{\prime}, C^{\prime}\right\}\) е еднозначно определена които и три две по две недиаметрално противоположни точки да изберем от нея (ако първоначално избраният \(\triangle A B C\) е тъпоъгълен, то първо взимаме диаметрално противоположната точка на върха при тъпия ъгъл и построяваме останалите два триъгълника спрямо получения остроъгълен такъв). Произволен триъгълник \(A B C\) участва в точно една от горните конфигурации. За всяка от конфигурациите е в сила отношението \(1: 3\) на остроъгълни към тъпоъгълни триъгълници. Следователно и в общия случай е вярно, че

\[ \begin{aligned} & \mathbf{P}(\triangle A B C \text { е остроъгълен }): \mathbf{P}(\triangle A B C \text { е тъпоъгълен })=1: 3 \quad \Longrightarrow \\ & \mathbf{P}(\triangle A B C \text { е остроъгълен })=\tfrac{1}{4}, \quad \mathbf{P}(\triangle A B C \text { е тъпоъгълен })=\tfrac{3}{4} . \end{aligned} \] Да се върнем към първата част на Задача 3.3. Да наречем едноцветните триъгълници остроъгълни, а разноцветните – тъпоъгълни, като тъпият ъгъл е между двете едноцветни ребра в триъгълника. За всяко ребро \(e_{i j}\) в \(G\) съществува биекция между множествата от върхове от третата компонента на графа, които \(e_{i j}\) вижда съответно под остър и тъп ъгъл. Съгласно по-горния резултат, можем да разбием всички триъгълници в \(G\) на непресичащи се конфигурации от по 4 триъгълника, три от които са разноцветни, а един – едноцветен. Наистина, нека разгледаме произволен едноцветен триъгълник \(a_{1} a_{2} a_{3}, a_{1} \in A_{1}, a_{2} \in A_{2}, a_{3} \in A_{3}\) и нека \(a_{1}^{\prime} \in A_{1}, a_{2}^{\prime} \in A_{2}\) и \(a_{3}^{\prime} \in A_{3}\) са съответните биективни образи на \(a_{1}\), \(a_{2}\) и \(a_{3}\) спрямо ребрата \(a_{2} a_{3}, a_{1} a_{3}\) и \(a_{1} a_{2}\). Аналогично на горното, конфигурацията \(\left\{a_{1}, a_{1}^{\prime}, a_{2}, a_{2}^{\prime}, a_{3}, a_{3}^{\prime}\right\}\) е еднозначно определена при произволен избор на три от върховете в нея, лежащи в трите различни компоненти на \(G\). Следователно \(k=20\).

Забележете, че решението на задачата от Коментар 2 е по-сложно и по-общо от това за Задача 3.3, но стъпва върху класически резултати, които, ако са известни на решаващия, ще му помогнат бързо да се ориентира и да сведе Задача 3.3 до познати конструкции.

3.1. Анализ на работещите в Задача 3.2 конфигурации

В конструирания в последния параграф на Задача 3.2 (или задача 3.3) пример за работеща конфигурация от всеки връх на графа излизат равен брой червени и сини ребра, т.е. ребрата, инцидентни с произволен връх, са балансирани. Интересен е въпросът дали има пример, в който това не е така. Както ще видим по-долу, това е невъзможно даже и при по-обща ситуация.

Да видим първо как да интерпретираме червените и сините ребра, така че това да позволява обобщаване. За всеки връх \(x \in A_{1}\) да означим \(f_{1,2}^{b}(x)\) и \(f_{1,2}^{r}(x)\) подмножествата от върхове на \(A_{2}\), които са съседи на \(x\) пь съответно сините и червените ребра. Ясно е, че \(f_{1,2}^{b}(x)=A_{2} \backslash f_{1,2}^{r}(x)\). П аналогичен начин, за произволна пермутация \(i_{1}, i_{2}, i_{3}\) на \(1,2,3\) може да дефинираме функциите \(f_{i_{1}, i_{2}}^{b}(x)\) и \(f_{i_{1}, i_{2}}^{r}(x)\), които на връх \(x \in A_{i_{1}}\) съпоставят подмножество в \(A_{i_{2}}\). Тези функции имат определени свойства, генерирани от условията на задача 3.3. Знаем също, че множествата \(A_{1}, A_{2}, A_{3}\) има равен брой елементи. Искаме да покажем, че \(m\left(f_{i_{1}, i_{2}}^{b}(x)\right)=m\left(f_{i_{1}, i_{2}}^{r}(x)\right)\) където с \(m(A)\) сме означили броя на елементите на крайното множество A. Да се абстрахираме от факта, че базовите множества са крайни. Ще докажем едно по-общо твърдение, което се отнася за измерими множества, като \(m(A)\) вече означава мярката на множеството \(A\).

Нека \(A_{1}, A_{2}, A_{3}\) са три копия на едно и също измеримо множество с мярка 1. Върху всяко от множества \(A_{i}\) има дефинирана сигма алгебра \(\mathcal{F}\left(A_{i}\right)\), за \(i=1,2,3\). Означаваме с \(\mu_{i}(A)\) мярката на \(A \in \mathcal{F}\left(A_{i}\right)\). Тъй като имаме копия на една и съща сигма алгебра и мярка върху нея, вместо \(\mu_{i}(\cdot)\) ще използваме просто означението \(\mu(\cdot)\), стига да не възникват недоразумения. Това ще ни избави от излишно усложняване на означенията.

Читателят, който не е запознат с теория на мярката, може или да пропусне параграф 3.1, или навсякъде по-долу да счита, че \(A_{i}\) са крайни множества с един и същ брой елементи \(m\) и \(\mu(A):=\#(A) / m\).

За всяко \(i_{1}, i_{2} \in\{1,2,3\}, i_{1} \neq i_{2}\) нека \(E_{i_{1}, i_{2}}^{b}\) и \(E_{i_{1}, i_{2}}^{r}\) бъдат измерими подмножества на \(A_{i_{1}} \times A_{i_{2}}\) (което е измеримо пространство с мярка, генерирана от мерките на \(A_{i_{1}}, A_{i_{2}}\) ). Множествата \(E_{i_{1}, i_{2}}^{r}, E_{i_{1}, i_{2}}^{b}\) са всъщност интерпретация на множествата от съответно червените и сините ребра, свързващи върхове от \(A_{i_{1}}\) и \(A_{i_{2}}\). За \(x \in A_{i_{1}}\) дефинираме множествата

\(f_{i_{1}, i_{2}}^{b}, f_{i_{1}, i_{2}}^{r} \subset A_{i_{2}}\) по следния начин:

\[ \begin{aligned} & f_{i_{1}, i_{2}}^{b}(x):=\left\{y \in A_{i_{2}} \mid(x, y) \in E_{i_{1}, i_{2}}^{b}\right\}, \forall x \in A_{i_{1}} . \\ & f_{i_{1}, i_{2}}^{r}(x):=\left\{y \in A_{i_{2}} \mid(x, y) \in E_{i_{1}, i_{2}}^{r}\right\}, \forall x \in A_{i_{1}} . \end{aligned} \]

Множествата \(f_{i_{1}, i_{2}}^{b}(x)\) и \(f_{i_{1}, i_{2}}^{r}(x)\) интерпретираме като подмножествата на върховете в \(A_{i_{2}}\), които са съседи на \(x \in A_{i_{1}}\) по съответно сините и червените ребра.

Забележете, че така дефинираните множества са измерими в \(A_{i_{2}}\), т.е.

\(f_{i_{1}, i_{2}}^{b}, f_{i_{1}, i_{2}}^{r}: A_{i_{1}} \rightarrow \mathcal{F}\left(A_{i_{2}}\right)\). Нека допуснем, че функциите \(f_{i_{1}, i_{2}}^{b}, f_{i_{1}, i_{2}}^{r}\) удовлетворяват свойствата: i) \(f_{i_{1}, i_{2}}^{b}(x)=A_{i_{2}} \backslash f_{i_{1}, i_{2}}^{r}(x), \forall x \in A_{i_{1}}\); ii) \(y \in f_{i_{1}, i_{2}}^{b}(x) \Longleftrightarrow x \in f_{i_{2}, i_{1}}^{b}(y) ; y \in f_{i_{1}, i_{2}}^{r}(x) \Longleftrightarrow x \in f_{i_{2}, i_{1}}^{r}(y)\); iii) \(\mu\left(f_{i_{1}, i_{3}}^{r}(x) \cap f_{i_{2}, i_{3}}^{r}(y)\right)=1 / 4, \quad \forall x \in A_{i_{1}}, \forall y \in A_{i_{2}}\); iv) \(\mu\left(f_{i_{1}, i_{3}}^{b}(x) \cap f_{i_{2}, i_{3}}^{b}(y)\right)=1 / 4, \quad \forall x \in A_{i_{1}}, \forall y \in A_{i_{2}}\).

Теорема 2. При горните условия следва, че за всяка пермутация

\(\left(i_{1}, i_{2}, i_{3}\right)\) на \((1,2,3)\) е в сила \(\mu\left(f_{i_{1}, i_{2}}^{r}(x)\right)=\mu\left(f_{i_{1}, i_{2}}^{b}(x)\right)=1 / 2 \quad \forall x \in A_{i_{1}}\).

Доказателство. Да допуснем противното. Като имаме предвид i), нека за определеност съществува \(x_{1} \in A_{1}\) такова, че

\[ \mu\left(f_{1,3}^{r}\left(x_{1}\right)\right)=\mu_{1} \gt 1 / 2 \]

Нека \(y \in A_{2}\). От i), iii) и iv) следва

\[ \begin{aligned} f_{2,3}^{b}(y) & =\left(f_{2,3}^{b}(y) \cap f_{1,3}^{r}\left(x_{1}\right)\right) \cup\left(f_{2,3}^{b}(y) \cap f_{1,3}^{b}\left(x_{1}\right)\right) \\ & \left.=\left(f_{1,3}^{r}\left(x_{1}\right)\right) \backslash\left(f_{2,3}^{r}(y) \cap f_{1,3}^{r}\left(x_{1}\right)\right)\right) \cup\left(f_{2,3}^{b}(y) \cap f_{1,3}^{b}\left(x_{1}\right)\right) \end{aligned} \]

От тук получаваме, че

(2)\[ \mu\left(f_{2,3}^{b}(y)\right)=\mu_{1}-\tfrac{1}{4}+\tfrac{1}{4}=\mu_{1} \gt \tfrac{1}{2}, \quad \forall y \in A_{2} \]

От (2) пък, със същия аргумент, но приложен обратно към \(f_{1,3}^{r}\),3, следва \(\mu\left(f_{1,3}^{r}(x)\right)=\mu_{1} \quad \forall x \in A_{1}\).

Съгласно теоремата на Фубини имаме:

\[ \mu\left(E_{1,3}^{r}\right)=\int_{A_{1}} \mu\left(f_{1,3}^{r}(x)\right) d \mu(x)=\mu_{1} \gt \tfrac{1}{2} \]

Тук индуцираните мерки в \(A_{i_{1}} \times A_{i_{2}}\) за простота отново бележим с \(\mu\). От ii) следва \(E_{1,3}^{r}=E_{3,1}^{r}\), което дава

\[ \tfrac{1}{2} \lt \mu_{1}=\mu\left(E_{3,1}^{r}\right)=\int_{A_{3}} \mu\left(f_{3,1}^{r}(z)\right) d \mu(z) \]

Следователно съществува \(z_{0} \in A_{3}\), за което \(\mu\left(f_{3,1}^{r}\left(z_{0}\right)\right) \geq \mu_{1}\), откъдето

(3)\[ \mu\left(f_{2,1}^{b}(y)\right) \geq \mu_{1} \gt \tfrac{1}{2}, \quad \forall y \in A_{2} . \]

Със същия аргумент, приложен за \(E_{2,3}^{b}\) и \(E_{3,2}^{b}\), получаваме

(4)\[ \mu\left(f_{1,2}^{r}(x)\right) \geq \mu_{1} \gt \tfrac{1}{2}, \quad \forall x \in A_{1} \]

От ii) имаме \(E_{1,2}^{b}=E_{2,1}^{b}\) и \(E_{1,2}^{r}=E_{2,1}^{r}\), а от i) следва \(E_{1,2}^{b} \cup E_{1,2}^{r}=A_{1} \times A_{2}\) т.e. \(\mu\left(E_{1,2}^{b}\right)+\mu\left(E_{1,2}^{r}\right)=1\).

От друга страна, от (3) и (4) получаваме \(\mu\left(E_{1,2}^{b}\right)=\mu\left(E_{2,1}^{b}\right) \gt 1 /2\) и \(\mu\left(E_{1,2}^{r}\right)=\mu\left(E_{2,1}^{r}\right) \gt 1 / 2\), което противоречи на факта, че \(\mu\left(E_{1,2}^{b}\right)+\)

\(\mu\left(E_{1,2}^{r}\right)=1\).

И така, доказахме, че всички работещи конфигурации са балансирани. Интересен е въпросът колко на брой са всички различни неизоморфни работещи конфигурации. Да отбележим, че представената в статията конфигурация за \(N=3 \cdot 4 \cdot 2=24\) е различна от тази в брошурата от НЗМС (виж [5]), тъй като при втората има сдвояване на двойки върхове във всяка от компонентите на триделния граф \(G\), докато при първата всеки връх от \(A_{1}\) има различно множество от съседи. Така основният въпрос е дали броят на конфигурациите монотонно расте с \(N=12 k\), дали може да се запише в явен вид като функция на \(k\) и дали тази функция е полиномиална, или експоненциална.

4. Приложение в международни състезания

Ще разгледаме задача 5 от Международната олимпиада по математика (МОМ 2023), за която, за разлика от предишните задачи, мотивацията да използваме вероятности, е по-голяма.

Задача (MOM 2023, зад. 5). Дадено е естествено число n. Японски триъгълник се състои от \(1+2+\cdots+n\) кргга, които са подредени във формата на равностранен трибгдлник, така че за всяко \(i=1,2, \ldots, n\) \(i\)-тият ред съдържа точно \(i\) кргга, точно един от които е очветен в червено. Нинджа-пбт в японски трибгълник ще наричаме редица от \(n\) кргга, която започва от пгрвия ред, последователно преминава от кргг кбл един от двата кргга, непосредствено под него, и завършва в последния ред. На фигурата по-долу е показан пример за японски трибгблник при \(n=6\), заедно с нинджа-пбт, сбдържащ, два червени кргга. В зависимост от \(n\) да се намери най-голямото \(k\), за което във всеки японски триггълник има нинджа-пбт, съдържащ, поне \(k\) червени кргаа.

Задачи от този тип предполагат следната аргументация:

1) намираме оценка отдолу за \(k\);

2) даваме пример, при който не можем да минем през по-голям брой червени кръгове.

В тази статия ще разгледаме само оценката отдолу, тъй като там се прилага вероятностният подход. Очакванията са отговорът да е от порядъка на \(k=\log _{2} n\). Както ще видим, търсената стойност е \(k=\left\lfloor\log _{2} n\right\rfloor+1\). Да разсъждаваме грубо и не съвсем строго. Да вземем един произволен нинджа-път \(p\). Вероятността той да уцели червената топка в \(i\)-тия ред, би следвало да е \(1 / i\), тъй като там има \(i\) топки и само една е червена (това, разбира се, е наивно разсъждение и не е вярно). Нека \(1_{i}\) е случайната величина, която приема стойност 1, ако пътят \(p\) минава през червената топка на \(i\)-тия ред, а в противен случай приема стойност 0. Такива случайни величини се наричат индикатори – те вдигат флаг 1, ако определено събитие се случва, и 0, ако не се случва. В сила е \(\mathbb{E}\left[1_{i}\right]=1 / i\) и като сумираме по \(i\), виждаме, че средният брой червени топки по пътя е \(\sum_{i=1}^{n} \tfrac{1}{i} \approx \ln n\). Нека „изправим“ тази идея. По-долу са дадени два опита за това. При първия получената оценка за \(k\) е по груба и не е точната, но пък

конструкцията е по-проста и виждаме как работи методът. При втория опит прецизираме нещата и получаваме точната оценка.

Първи опит. Нека вероятностното ни пространство се състои от всички възможни нинджа-пътища, като на всеки от тях ще съпоставим определена вероятност. Искаме така да направим това, че свойството по-долу да е изпълнено.

Свойство 1. Вероятността нинджа-път да мине през кой да е кръг на \(i\)-тия ред, е точно \(\tfrac{1}{i}\), без значение от положението на кръга в реда.

Да предположим, че това е осъществимо. Да означим с \(r_{1}, r_{2}, \ldots, r_{r}\) червените точки, като \(r_{i}\) е на \(i\)-тия ред. Нека \(1_{r_{i}}, i=1,2, \ldots, n\) е случайната величина, която приема стойност 1, ако нинджа-път минава през \(r_{i}\) и стойност 0 в противен случай. Тогава \(\mathbb{P}\left(1_{r_{i}}=1\right)=\tfrac{1}{i}, i=1,2, \ldots, n\) откъдето

\[ \mathbb{E}\left[1_{r_{i}}\right]=\tfrac{1}{i}, i=1,2, \ldots, n \]

Да разгледаме случайната величина \(N:=\sum_{i=1}^{n} 1_{r_{i}}\). Тя брои червените точки, през които минава случайно избран нинджа-път (под „случайно избран” разбираме избран в съгласие със съответното вероятностно пространство). Имаме \(\mathbb{E}[N]=\sum_{i=1}^{n} \tfrac{1}{i} \gt \ln n\). И така, математическото очакване на броя на уцелените червени точки от случаен нинджа-път е поне \(\ln n\). Следователно съществува път, минаващ през поне толкова червени точки.

Остава да конструираме вероятностно пространство, удовлетворяващо Свойство 1. Стартираме от горе надолу и на всеки разклон ще присвоим вероятност да поемем надолу-наляво или надолу-надясно. На първия разклон, под най-горната точка, двете вероятности са \(1 / 2\). Т.е. вероятността нинджа-път да мине през коя да е от двете точки на втория ред, е \(1 / 2\). Да предположим, че сме на \(j\)-тия ред и вероятността нинджа-път да уцели коя да е точка на него, е \(\tfrac{1}{j}\). Искаме да определим какви трябва да са вероятностите за разклоненията надолу, така че същото да е в сила и за \(j+1\)-тия ред. Правим това, както е показано на фиг. 2.

На \(i\)-тия разклон под \(j\)-тия ред определяме вероятността да вземем левия/десния път съответно да е \(\left(\tfrac{j+1-i}{j+1}\right)\) и \(\left(\tfrac{i}{j+1}\right), i=1,2, \ldots, j\). Лесно се пресмята, че вероятността да уцелим произволна точка на \(j+1\)вия ред, е \(\tfrac{1}{j+1}\). Продължаваме да правим това, докато не стигнем до последния ред.

Втори опит. Сега ще прецизираме оценката (Grozev, 2025), като построим по-точно вероятностно пространство и с негова помощ установим точната оценка отдолу: \(k \geq\left\lfloor\log _{2} n\right\rfloor+1\). Да означим \(m:=\left\lfloor\log _{2} n\right\rfloor\). Вероятностното пространство, което ще конструираме, ще зависи от положението на червените точки, за разлика от това, което построихме по-горе. И така, считаме, че конфигурацията на червените точки е фиксирана. Идеята пак е да разгледаме всички възможни нинджа-пътища, като на всеки от тях присвоим определена вероятност, така че следното свойство да е в сила.

Свойство 2. За \(i=0,1, \ldots, m-1\), вероятността да минем през червената точка на ред \(\ell\), където \(2^{i} \leq \ell \leq 2^{i+1}-1\), е точно \(2^{-i}\).

Да предположим, че имаме вероятностно пространство, удовлетворяващо горното свойство. Нека означим червените точки с \(r_{1}, r_{2}, \ldots, r_{n}\), като \(r_{\ell}\) се намира на \(\ell\)-тия ред. Да въведем случайната величина \(1_{r_{\ell}}\), \(\ell=1,2, \ldots, n\), 2,...,n, която има стойност 1, ако случайно избран път минава през \(r_{\ell}\), и 0 в противен случай. За тази индикаторна случайна величина имаме

\[ \mathbb{P}\left(1_{r_{\ell}}=1\right)=\tfrac{1}{2^{i}}, 2^{i} \leq \ell \leq 2^{i+1}-1, i=0,1, \ldots, m-1, \]

което дава

\[ \mathbb{E}\left[1_{r_{\ell}}\right]=\tfrac{1}{2^{i}}, \forall \ell, 2^{i} \leq \ell \leq 2^{i+1}-1, i=0,1, \ldots, m-1, m:=\left\lfloor\log _{2} n\right\rfloor . \]

Да разгледаме случайната величина \(N:=\sum_{\ell=1}^{n} 1_{r_{\ell}}\). Тя „брои“ червените точки, през които минава случайно избран път (в съответствие с вероятностното пространство, което удовлетворява Свойство 2). Получаваме

(5)\[ \begin{gathered} \mathbb{E}[N]=\sum_{i=0}^{m-1} \sum_{2^{i} \leq \ell \leq 2^{i+1}-1} \mathbb{E}\left[1_{r_{\ell}}\right]+\sum_{2^{m} \leq \ell \leq n} \mathbb{E}\left[1_{r_{\ell}}\right] \\ \mathbb{E}[N]=\sum_{i=0}^{m-1} 1+\sum_{2^{m} \leq \ell \leq n} \mathbb{E}\left[1_{r_{\ell}}\right] \gt m \end{gathered} \]

И така, очакваният брой червени точки, през които преминава избраният път, е по-голям от \(m=\left\lfloor\log _{2} n\right\rfloor\). Това означава, че съществува път който минава през поне \(\left\lfloor\log _{2} n\right\rfloor+1\) червени точки.

Нека сега видим как да конструираме вероятностно пространство, за което Свойство 2 е изпълнено.

На всяко разклонение на нинджа-път ще присвоим двойка вероятности \(\left(p_{1}, p_{2}\right), p_{1}+p_{2}=1\), p1 + p2 = 1, като \(p_{1}\) е вероятността да тръгнем надолу и наляво, а \(p_{2}\)– вероятността да поемем надолу и надясно. За всеки разклон ще изберем \(\left(p_{1}, p_{2}\right)\), така че \(\left(p_{1}, p_{2}\right) \in\{(0,1),(1,0),(1 / 2,1 / 2)\}\). Вероятностното пространство ще се състои от всички възможни нинджа-пътища, като вероятността да изберем определен път (теглото му), ще е равна на произведението на всички вероятности, асоциирани с разклоненията му. Еквивалентно, на всеки възел ще присвоим вероятност, равна на вероятността нинджа-път да мине през този възел.

Тези присвоявания ще направим в обратен ред – от долу нагоре, като използваме следната идея. Да предположим, че на точките на \(j+1\)-вия ред вече са присвоени някакви вероятности и даден възел има присвоена вероятност \(p\). Ние „пренасяме” нагоре тази вероятност или цялата нагоре вляво, или цялата нагоре вдясно, или \(p / 2\) наляво и \(p / 2\) надясно (фиг. 3).

По този начин, движейки се нагоре, подходящо ще присвоим на всички възли определени вероятности, така че да изпълним Свойство 2. Фигура 4 показва как работи това за \(n=8\). Така извършената процедура на фиг. 4 беше, за да постигнем следния ефект. Ако сега тръгнем от горе надолу, на всеки разклон има присвоени вероятности 0, 1 или \(1 / 2\) да продължим надолу-наляво или надолунадясно, които са подбрани така, че Свойство 2 да е в сила. Детайлите следват.

Да се фокусираме върху \(2^{i+1}-1\)-вия ред. Да присвоим на червената точка вероятност \(2^{-i}\) и на всички останали възли – вероятност \(2^{-i-1}\). Последователно ще определим вероятността на всеки възел нагоре, ред по ред, до \(2^{i}\)-тия ред да бъде или \(2^{-i}\), или \(2^{-i-1}\), така че на всеки червен възел да бъде присвоена вероятност \(2^{-i}\).

Да допуснем, че сме направили това за всички редове до \(j+1\)-вия включително, като на възлите му сме присвоили от ляво надясно вероятности \(p_{1}, p_{2}, \ldots, p_{j+1}\). Трябва да определим вероятностите \(q_{1}, q_{2}, \ldots, q_{j}\), които ще присвоим на \(j\)-тия ред. Нека червената точка в \(j\)-тия ред бъде на позиция \(k\). Да разгледаме поотделно възможностите за (\(p_{k}, p_{k+1}\) ).

Първи с случай : \(p_{k}=p_{k+1}=2^{-i-1}\). В този случай полагаме \(q_{k}=2^{-i}\), \(q_{s}=p_{s}, s=1,2, \ldots, k-1\) и \(q_{s}=p_{s+1}, s=k+1, \ldots, j\).

Втори случай: \(p_{k}=2^{-i}, p_{k+1}=2^{-i-1}\). При тази опция, в \(j+1\)-вия ред има друга точка с вероятност \(2^{-i-1}\), освен \(p_{k+1}\), защото \(\sum_{s=1}^{j+1} p_{s}=1\). Т.е., \(p_{s}=2^{-i-1}\) за някое \(s\), което е или по-малко от \(k\), или е по-голямо от \(k+1\).

Да разгледаме първо случая, когато съществува \(s \lt k\) с \(p_{s}=2^{-i-1}\). Тогава полагаме \(q_{k}=2^{-k}, q_{s}=p_{s+1}, s=k+1, \ldots, j\). Нека \(r\) да е най-големият индекс, по-малък от \(k\), за който \(p_{r}=2^{-i-1}\). Полагаме \(q_{s}=p_{s}, s=1,2, \ldots, r-1, q_{s}=2^{-i}, s=r, \ldots, k-1\).

Да разгледаме сега случая, когато \(p_{s}=2^{-i}, s=1,2, \ldots, k\). Нека \(r\) е най-малкият индекс, по-голям от \(k+1\), за който \(p_{r}=2^{-i-1}\). Тоест, \(p_{s}=2^{-i}, s=k+2, k+3, \ldots, r-1\). Сега полагаме \(q_{s}=p_{s}, s=1,2, \ldots, k\), \(q_{s}=2^{-i}, s=k+1, \ldots, r-1\) и \(q_{s}=p_{s+1}, s=r, \ldots, j\).

Трети и четвърти случай: случаите (\(p_{k}=2^{-i-1}, \quad p_{k+1}=2^{-i}\) ) и (\(p_{k}=\) \(p_{k+1}=2^{-i}\) ) са подобни.

Следвайки този план, стигаме до \(2^{i}\)-тия ред, всеки възел на който ще бъде с присвоена вероятност \(2^{-i}\). Забележете, че с конструкцията, която правим, ако се движим надолу по някой нинджа-път, вероятността на всеки разклон да хванем долния ляв, респективно долния десен път, е 1, 0 или \(1 / 2\). Конструкцията също гарантира, че така определеното вероятностно пространство удовлетворява Свойство \(2 . \square\)

5. Заключение и бъдеща работа

В тази статия бе илюстрирана ползата от прилагането на вероятностния подход при решаването на състезателни задачи. Бяха разгледани три задачи от национални и международни ученически олимпиади по математиката. Макар предложените решения да не са най-елегантните и най-кратките като запис, те демонстрират основното качество на подхода, а именно – директното атакуване на задачите при правилно дефиниране на подходящо дискретно вероятностно пространство. Бе показано, че подходът работи не само за доказателство, че съществува работеща конструкция, но дори и за нейното експлицитно намиране.

Бе формулиран и отворен въпрос относно броя на неизоморфните различни конфигурации, удовлетворяващи Задача 3.2. Бъдещата работа на авторите е да изследват дали при различен избор на вероятностното пространство получените конфигурации ще са различни, както и каква е връзката между броя депутати \(N\) и броя на различните конфигурации.

БЕЛЕЖКИ

1. НОМ 2025, Областен кръг (Брошура МОН):

https://dgrozev.wordpress.com/2025_bgr_nmo_regional/

ЛИТЕРАТУРА

КОРТЕЗОВ, И., ДЕЛЧЕВ, К., МАРИНОВ, М., Национално зимно математическо състезание 2025, Математика, бр. 1/2025, стр. 20 38

REFERENCES

ALON, N., SPENCER, J., 2008. The Probabilistic Method, 3-rd edition, John Wiley & Sons, Inc.

CHEN, E., 2014. Expected Uses of Probability https://web.evanchen.cc/handouts/ProbabilisticMethod/ProbabilisticMethod.pdf

ERDÖS, P., 1947. Some remarks on the theory of graphs. Bulletin of the Amer. Math. Soc., no. 53, pp. 292 – 294.

ERDÖS, P., 1961. Graph theory and probability II. Canadian J. Math., no. 13, pp. 346 – 352.

ERDÖS, P., 1973. The Art of Counting: Selected writings. J. Spencer (edt.), Mathematicians of our Time, vol. 5, xxiii p. 742. The MIT Cambridge, Mass.-London.

FELLER, W., 1991. An Introduction to Probability Theory and Its Applic 3-rd edition, vol. 1. Wiley. ISBN: 978-0-471-25708-0

GROZEV D., 2025. IMO 2023 Problem 5 Revisited https://dgrozev.wordpress.com/2025/02/25/imo-2023-problem-5-revisited/

KORTEZOV, I., DELCHEV, K., MARINOV, M., 2025 National Winter Mathematical Competition, Matematika, 1/2025, pp. 20-38 (In Bulgarian)

LOH, PO-SHEN 2010. The Probabilistic Method https://www.math.cmu.edu/ ploh/docs/math/mop2010/prob-comb-soln.pdf