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

2025/3, стр. 237 - 256

МОДЕЛИ НА ВЕРОЯТНОСТНИ ПРОСТРАНСТВА В ОЛИМПИАДНИ ЗАДАЧИ

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

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

1. Въведение

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

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

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

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

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

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

За по-обстойно запознаване с прилагането на вероятностния метод в 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).

Дефиниция. Крайно вероятностно пространство е двойката ( където е множество от краен брой обекти наричани елементарни събития, а се нарича вероятностна мярка, за която .

Гледаме на като вероятността да се случи елементарното събитие .

Всяко подмножество на наричаме събитие. Вероятността да се случи събитието , е равна на сумата на вероятностите на елементарните събития, от които се състои , т.е. .

Две събития и се наричат независими, когато

Вероятността да се случи събитието , при условие че вече се е случило събитието , наричаме условна вероятност и бележим с .

В сила е

Дефиниция. Нека е дадено крайно вероятностно пространство ( ). Функцията наричаме случайна величина.

В дискретния случай вероятността случайната величина да приема определена стойност , е равна на

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

Забележка. Тъй като тук разглеждаме само комбинаторни конфигурации от краен брой обекти, съответните вероятностни пространства са крайни и горната дефиниция напълно ни удовлетворява. В общия случай, възможните събития не са всичките подмножества на , а само част от тях. Тази фамилия от подмножества на трябва да е затворена по отношение на вземане на допълнение на множество в , както и по отношение на обединение на изброим брой елементи на . Такава фамилия се нарича алгебра, а множествата в нея се наричат измерими. Вероятностната мярка е дефинирана само върху измеримите множества. Случайната величина в този случай не е каква да е функция , а трябва да е измерима функция, т.е. за всеки отворен интервал .

Сума и произведение на две случайни величини , дефинирани в едно и също вероятностно пространство, са случайните величини и , дефинирани по естествен начин като

Умножение на случайна величина с реално число се дефинира като .

Дефиниция. Нека е дадена случайната величина , която приема стойности от множеството . Математическо очакване на , означавано с , се дефинира по следния начин

Пример. Хвърляме зар. В този случай се състои от обединението на 6 елементарни събития, а именно: възможните резултати от хвърлянето. Вероятностната мярка приема стойност за всяко от тях. Нека случайната величина е равна на броя точки, които се падат. Множеството от стойности, които приема, е . Вероятността ді приеме стойност , е . Следователно

Забележете, че ако , то приема стойности, по-големи или равни на , както и по-малки или равни на . Това наблюдение има голямо приложение, както ще видим.

Свойство 1. (Линейност на очакването) Нека са случайни величини . Изпълнено

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

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

Решение. Да заменим в условието 2025 с и нека Имаме картончета и на едната страна на -тото от тях е записано множество , а на другата му страна – множеството . Искаме така да обърнем картончетата, че обединението на множествата на лицевата им страна да е . Нека е най-малкото , за което това винаги може да се направи. Ще докажем, че .

Първо ще покажем, че . Нека вземем такова, че . Нека обърнем всяко картонче на една от двете му страни с вероятност (независимо едно от друго). За всяко да означим с случайната величина, която е 0, когато числото се среща на някое картонче, и 1, ако не се среща на никое. Тогава , така че за математическото очакване на имаме .

Нека . От Свойство 1, следва че

Тъй като приема само цели неотрицателни стойности, значи има събитие (разположение на картончетата), за което . При това разположение всяко число от се среща на лицeватата страна на някое картонче. Следователно .

Нека сега покажем, че в случай, когато , съществуват множества , така че за всеки избор на да бъде или или . Това е еквивалентно на

(1)

за всеки такъв избор на . Достатъчно е да докажем, че такива множества съществуват в случая . Наистина, множествата , които вършат работа за , ще свършат работа и при , тъй като (1) ще продължава да е в сила.

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

и нека всеки елемент има равна вероятност. Нека разгледаме събитията . Очевидно и са независими. Да вземем събития , където за всяко е или , 2,...,n, Bi е или . От казаното следва

Това доказва (1), откъдето .

Има разнообразни подходи за доказателството на . Най-ефективният сред тях е навярно използването на лаком (greedy) алгоритъм, където обръщаме карта след карта така, че на всяка стъпка поне половината от липсващите до момента числа да са откъм лицевата страна на последната обърната карта. Също така, има и конструктивен подход при който в явен вид се дава работещо поставяне на база множествата, изписани от двете страни на картите. Лакомият подход не дава ясни идеи как да се реши , докато представеното по-горе решение, както и конструктивният подход помагат за атакуването и на долната граница. И в двата случая извеждането на долната граница чрез допускане на противното, като при конструктивния подход за всяко поставяне явно се извежда номер, който няма да присъства върху лицевата страна на нито една от картите, докато при вероятностния подход това липсва. Последното прави вероятностния подход по-интуитивен, тъй като благодарение на него директно решаваме поставената задача, без да е необходимо да разширяваме фокуса на изследванията и да анализираме допълнителни причинно-следствени връзки от условието.

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

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

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

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

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

Задача 3.3 Даден е триделен граф , за който е изпълнено условието . За всяка пермутация ( ) на числата и всеки два върха е известно, че има точно върха в , които са едновременно свързани с и , и точно върха в , които едновременно не са свързани с и . Да се намерят всички възможни стойности на .

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

Нека оцветим всички ребра на в червено, след което да прекараме всички останали ребра и да ги оцветим в синьо. Според условието, както и да изберем два върха от два различни дяла, вероятността връх от третия дял да е свързан с червени ребра с първите два върха, е равна на вероятността да е свързан със сини ребра с всеки от тях. Да изберем за вероятностно пространство всевъзможните тройки върхове , като всяка такава тройка има еднаква вероятност да бъде избрана. Да оценим сега вероятността избрана тройка да е едноцветен триъгълник. Имаме

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

откъдето следва, че . Да означим . Тогава вероятността да е едноцветен триъгълник, е равна на , а вероятността да не е едноцветен, е равна на .

Нека сега оценим по друг начин вероятността триъгълникът да не е едноцветен. В този случай две от страните са оцветени в цвят, различен от третата страна. Тази „трета“ страна може да бъде всяка от страните , като тези три събития са взаимно изключващи се. Вероятността двете ребра и да са оцветени в цвета, различен от цвета на , е точно , така че вероятността триъгълникът да не е едноцветен, е равна на .

И така , което дава . Следователно .

Остава да дадем пример на граф, удовлетворяващ условията за . Да си представим, че съществува подходящо вероятностно пространство, в което, като вземем произволен триъгълник , вероятността коя да е от страните да е оцветена в синьо, съответно червено, е равна на и тези три събития са независими. Тогава вероятността две фиксирани страни на да са в даден цвят, е . Планът е следният:

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

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

Нека

където ( ) интерпретираме като триъгълник, а – като цветовете съответно на страните и (0 – червено, 1 – синьо). На всеки елемент на присвояваме една и съща вероятност. Забележете, че са обвързани със страните на триъгълника, а не с върховете му. За да ги обвържем с върховете, ще въведем ново множество от елементарни събития,

В този случай считаме, че е оцветен в червено, ако , и в синьо, ако . Горният запис може да бъде и във вида:

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

Нека и . Два елемента и са свързани с червено ребро, ако , а в противен случай са свързани със синьо ребро. Аналогично, и са свързани с червено ребро само ако ; и накрая и с. свързани с червено ребро само ако .

Избора на дефинираме да е равновероятен и независим. Да разгледаме така дефинираното вероятностно пространство. За произволна пермутация ( ) на ( ) и фиксирани нека с означим събитието реброто да е червено, a с – събитието реброто да е червено. Лесно се проверява, че всички тези събития са независими и с вероятност Тогава пълният триделен граф с така дефинираното оцветяване изпълнява условието на задачата и . Ако всеки връх на този граф мултиплицираме по 10, ще получим търсения пример на граф с .

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

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

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

Да построим диаметрално противоположните точки съответно на . Триъгълниците и нямат общи вътрешни точки, а споделят единствено отсечката . Тъй като е остроъгълен, то центърът на не лежи върху , а е вътрешна точка за него. Следователно точката е извън и той е тъпоъгълен. Аналогично, триъгълниците и също са тъпоъгълни. Конфигурацията е еднозначно определена които и три две по две недиаметрално противоположни точки да изберем от нея (ако първоначално избраният е тъпоъгълен, то първо взимаме диаметрално противоположната точка на върха при тъпия ъгъл и построяваме останалите два триъгълника спрямо получения остроъгълен такъв). Произволен триъгълник участва в точно една от горните конфигурации. За всяка от конфигурациите е в сила отношението на остроъгълни към тъпоъгълни триъгълници. Следователно и в общия случай е вярно, че

Да се върнем към първата част на Задача 3.3. Да наречем едноцветните триъгълници остроъгълни, а разноцветните – тъпоъгълни, като тъпият ъгъл е между двете едноцветни ребра в триъгълника. За всяко ребро в съществува биекция между множествата от върхове от третата компонента на графа, които вижда съответно под остър и тъп ъгъл. Съгласно по-горния резултат, можем да разбием всички триъгълници в на непресичащи се конфигурации от по 4 триъгълника, три от които са разноцветни, а един – едноцветен. Наистина, нека разгледаме произволен едноцветен триъгълник и нека и са съответните биективни образи на , и спрямо ребрата и . Аналогично на горното, конфигурацията е еднозначно определена при произволен избор на три от върховете в нея, лежащи в трите различни компоненти на . Следователно .