Смотрите, утверждение такое: «Да, верно!» И я это сейчас докажу с помощью зародыша вероятностного метода. На самом деле, конечно, это решение придумал не я, это придумал Эрдеш еще в 1961 году – такой великий венгерский комбинаторщик, вероятностник, числовик, автор огромного количества задач и замечательных результатов, создатель всей, по большому счету, современной школы комбинаторики и теории графов, вот. Ну, про Эрдеша мы еще может где-нибудь поговорим, с какой-нибудь точки зрения. А почему это верно сейчас я объясню. Вот смотрите, давайте рассмотрим случайную, случайную раскраску X (хи) нашего множества из 30 элементов. Множество {1, 2, ..., 30}. Ну, что значит случайное? Если хотите, можно это прям вот так совсем на пальцах объяснять следующим образом: переберем все возможные раскраски, занумеруем их, то есть каждой присвоим свой порядковый номер, свой такой идентификатор, запишем этот номер на некоторую бумажечку, на карточку, все эти бумажечки с номерами сгрузим в огромную такую шапку, в такой мешок, там их очень тщательно перемешаем, очень тщательно, так, чтобы удовлетворить вот этому третьему свойству равной вероятности. Запустим теперь руку в эту шапку, закроем глаза, так, и вытащим одну карточку, на которой написан какой-то номер. Вот это вот будет случайная раскраска. Понятно, что пространство Ω элементарных исходов – это собственно и есть множество всех раскрасок. Множество всех раскрасок, ну там Χ1 и так далее. А сколько всего раскрасок? Понятно, сколько всего раскрасок: раскрасок, конечно, в 2 в 30-той степени. Мы просто каждому элементу, независимо от остальных, можем присвоить либо красный, либо синий цвет. Разумеется, последняя раскраска будет иметь номер 2 в 30-той степени. Ну, понимаете, шапка-то будет, конечно, колоссальная, то есть 2 в 30-той степени – это что-то запредельное по размеру. Ну да Бог с ней, с шапкой, идея совершенно ясна. И эти элементарные исходы подобраны таким образом, чтобы удовлетворять в аккурат вот этим трем свойствам. Конечно, ровно один из них произойдет, никаких других у нас не бывает, в шапке других карточек нету. И они равновероятны, потому что я старательно сказал, что карточки внутри шапки, вот эти вот раскраски они тщательно-тщательно перемешаны, что они равновероятны. И, соответственно, вероятность возникновения любой раскраски можно считать равной 1 поделить на 2 в 30-той степени. Теперь давайте сделаем следующее: вот у нас зафиксирована наша совокупность пятерок M1, ..., M15. Возьмем любое множество M с индексом i из этой совокупности, ну, скажем, M1, и сопоставим этому множеству событие A с индексом i. Событие, состоящее в том, что в случайной раскраске, в случайной раскраске множество Mi-тое одноцветно. Это такое, если угодно, вредоносное событие, нехорошее. Нам-то хотелось добиться того, чтобы построить раскраску, в которой все множества неодноцветны. А сейчас мы рассматриваем событие, состоящее в том, что случился облом, вот ровно на этом множестве случился облом – это множество одноцветное. Понятно, что это событие вполне возможно. Например, если случайно мы покрасили все элементы в красный цвет, то у нас не то, что вот это конкретное Mi-тое будет одноцветным, а просто каждое из этих множеств будет одноцветным. Бывают такие несчастья, да вот вытянули карточку, на которой написан номер раскраски, красящей все элементы в красный цвет. Тогда, конечно, это событие произойдет. Такая раскраска ему благоприятствует. Ну так чему равна вероятность события i-тая? Как ее посчитать? Надо, естественно, воспользоваться вот этим определением. Надо найти количество всех элементарных исходов, которые благоприятствуют нашему событию, то есть количество всех раскрасок, в которых данное множество Mi-тое одноцветно, и разделить на общее количество раскрасок, то на 2 в 30-той степени. Таким образом сходу понятно чему равен знаменатель – это 2 в 30-той степени, а числитель, повторяю – это количество раскрасок, в которых данное конкретное множество одноцветно. Ну я традиционно здесь рисую такую вот картину – лоханочка означает такое условное наше множество из 30 элементов, я его просто нарисовал в виде отрезка. В этом отрезке есть такая сарделечка условная, символизирующая множество Mi-тое. Ясное дело, длина этой сарделечки составляет 5, потом что в Mi-том у нас 5 элементов. Ну и давайте посчитаем, сколько есть раскрасок, элементов от 1 до 30, в которых вот это конкретное пятиэлементное множество целиком одного цвета. Есть всего два варианта как сделать его одноцветным – это либо покрасить все вот эти пять элементов в красный цвет, либо их же все покрасить в синий цвет. И для каждого из этих двух вариантов, пользуемся правилами умножения в комбинаторике, есть еще какое-то количество способов покрасить все остальные вершины, все остальные элементы. Ну сколько остальных элементов? 25. Двадцать пять. Значит у нас есть 2 в 25-той степени способов присвоить оставшимся элементам какие-либо цвета. Итого, получаем 2 в 26-той поделить на 2 в 30-той – это 1/16 – 1 поделить на 2 в 4-той степени. Вероятность события Ai-того вот такая. Теперь смотрите: вероятность объединения Ai-тых по i от 1 до 2 в 30 степени. Да почему же 2 в 30-той, какое же 2 в 30-той? Ai-тых у нас 15 – столько, сколько множеств, до 15, конечно. Вот вероятность такого объединения, согласно вот этому последнему седьмому утверждению, конечно же не превосходит суммы по i от 1 до 15 вероятности Ai-тых, каждая из которых вот она, она равна 1/16-той. Значит это строго меньше 1. 15/16-тых строго меньше 1. Давайте подумаем, а что это за событие объединение Ai-тых, в чем оно состоит? Из каких раскрасок? Ai-тое состоит из тех раскрасок, у которых, напоминаю, Mi-тое одного цвета. Скажем, A1-е – это раскраски, в которых M1-е целиком одного цвета, A2-е – это раскраски, в которых M2-е целиком одного цвета. То есть, вот это объединение – это что-либо M1-е одноцветно, либо M2-е одноцветно, либо и так далее, либо M15-е одноцветно. Существует одноцветное множество – вот это что за событие. Событие, состоящее в том, что в случайной раскраске найдется одноцветное множество среди наших пятнадцати, которые мы изначально зафиксировали. Отлично. Тогда пользуемся вот этим вот соотношением из пункта 6. Вероятность отрицания этого события по i от 1 до 15 Ai-тое, мы берем все вот это с чертой, она, конечно, больше нуля. Ну, правильно же? Само событие имеет вероятность строго меньшую 1, а вероятность его отрицания, стало быть, строго больше нуля. 1 минус число, которое меньше 1 положительно. Так, в чем состоит отрицание? Здесь мы говорим, что существует одноцветное множество, а здесь мы говорим, что нет ни одного одноцветного множества, нет ни одного одноцветного множества. Можно найти раскраску элементов множества, при которой все множества неодноцветны. Нет ни одного одноцветного множества, все множества неодноцветны. Нет ни одного одноцветного, значит все неодноцветны. И это происходит с положительной вероятностью. Смотрим, наконец, на какое свойство? А вот на это свойство, точно. Смотрите, вероятность A равняется нулю в нашем классическом определении, тогда и только тогда, когда A – это пустое множество. То есть можно прочитать по-другому: если вероятность A строго положительна, то A – не пустое множество. Существуют элементарные исходы, которые этому событию A благоприятствуют. В данном случае это оначает, что существуют раскраски, которые благоприятствуют реализации вот этого события. То есть где-то в нашей шапке действительно есть карточки, отвечающие раскраскам, в которых все множества Mi-тые неодноцветны. И мы доказали наше утверждение. Вы видите, мы действительно по делу воспользовались и этим пунктом, и этим пунктом, и вот этим пунктом. Такая вот замечательная красивая иллюстрация того, как можно использовать, если угодно, на практике в каких-то конкретных комбинаторных задачах методы теории вероятности. Еще и еще раз повторяю, что да, все это вот то, что я сейчас рассказывал можно выразить на количественном языке, но это ж самая простая модель. Как только мы с вами начнем изучать более сложные модели, мы увидим, что ситуация бывает очень и очень непростой. И чисто комбинаторно записать то, что удобно записать на вероятностном языке можно конечно, но гораздо сложнее и совершенно не понятно зачем. А мы научимся вероятностному языку и будем с ним благополучно работать.
