Ну что, давайте доказывать! Доказывать, как я уже не раз повторил, будем с помощью схемы испытаний Бернулли, причем двухкратно примененной. Сейчас я объясню, что это значит. Давайте, прежде всего, давайте, прежде всего, введем обозначение. Давайте x(n), это у нас будет одна вторая на корень кубический из n на логарифм n. Просто введем такое обозначение. Вот этот вот кусочек, вот этот сомножитель мы обозначим x(n). Так нам хочется. Ну, и естественно, в терминах этого обозначения, m давайте считать просто равным. Если мы докажем для m равного вот этой величине, то конечно, мы докажем и для любого m меньшего. Поэтому давайте считать, что m равняется x умножить на два в степени n-1 при меньшем количестве, такая раскраска тем более будет существовать, коль скоро она существует при таком. Это то понятно. Вот. Ну, и давайте зафиксируем, зафиксируем какие-то множества совершенно произвольные, M1, …, Mm, каждое из которых, естественно, состоит из n-элементов. Ну, и давайте еще до кучи как-нибудь обозначим элементы объединения. То есть возьмем объединение этих множеств. Да что ж ты срываешься, M1, …, Mm и обозначим его элементы как-нибудь вот так: 1, 2 и так далее v. Вот это просто обозначение: 1, 2, ..., v — это элементы объединения наших множеств, которые мы как-то там, вот как нам захотелось, так и зафиксировали — совершенно произвольным образом. Так вот наша цель доказать, что существует такая раскраска вот этих вот самых элементов: от единицы до v, в два цвета: в красный и синий, при которой каждое из наших множеств M1, …, Mm содержит как элементы красного, так и элементы синего цветов. Вот такой вот интересный результат. Давайте выбирать случайную раскраску! Значит, будем выбирать случайную раскраску. Будем брать случайную раскраску. Разумеется, слушатели меня спросят, но ёлки-палки, вы же и в прошлый раз выбирали случайную раскраску. Что нового-то случилось? А-а-а, так вопрос в том, как ее выбирать. Что значит взять случайную раскраску? Если применяя классическую вероятность, мы просто перечислили, пересчитали все возможные раскраски этого множества. Их, очевидно, 2 в степени v штук. И из этого множества раскрасок, каковых 2 в степени v, выбрали одну случайную. Что называется из мешка вытащили. То есть с вероятностью 1 поделить на 2 в степени v. То теперь мы будем действовать немножко иначе. А именно, мы сделаем двухэтапную случайную раскраску. Давайте, этап 1. На первом этапе, внимание, товарищи, вот тут надо вникнуть. На первом этапе, на первом этапе, мы в принципе сделаем ровно то, что я только что сказал, то есть по-большому счету, перечислим все раскраски и выберем из них одну случайную. Но только вместо того, чтобы сделать так, мы это сделаем в терминах схемы испытаний Бернулли. А именно, мы возьмем монетку, у которой вероятность решки в точности равна одной второй. Если вы помните, я сегодня уже с вами рассуждал на тему о том, что если p равняется одной второй, то вот это тот самый единственный специальный случай, когда схема испытаний Бернулли превращается просто в классическую вероятность, в самую обыкновенную классическую вероятность. Ну, вот мне сейчас так удобнее рассуждать. И, что я сделаю с этой монеткой? Я буду ее бросать и если в очередном бросании, монетка выпадает решкой кверху, что происходит с вероятностью одна вторая, то я крашу этот очередной элемент в красный цвет, а если она выпадает кверху орлом, то я крашу очередной элемент в синий цвет. Орел или решка, красный или синий. Естественно, я на выходе получаю случайную раскраску, ту самую, которая в итоге давала оценку просто 2 в степени (n-1) и никакого корня кубического из n поделить на логарифм n не давало. Ну, вот сейчас мы будем что-то с этим делать. Ну, давайте, значит, я все-таки это запишу. С вероятностью p = 1/2 каждый элемент, каждый элемент независимо ото всех остальных, ото всех остальных, красный и с той же самой вероятностью p = 1/2, он синий. Вроде бы ничего нового не сделали. Но вот сейчас сделаем новое. Ну, подумаешь, переписали классическую схему в терминах схемы испытаний Бернулли — это явно не ново, а вот сейчас сделаем новое. Смотрите, ну, вот это очень простая схема, она как-то совершенно не использует специфику наших множеств, не пытается к ней привязаться. Она просто тупо, последовательно красит элементы с вероятностью одна вторая, то ли в красный, то ли в синий цвет. Ну, естественно, на выходе получается очень простой результат. Но согласитесь, что когда мы провернули уже всю эту схему и у нас на выходе возникла некоторая раскраска, то за счет чего, она могла бы оказаться плохой? Ну конечно, за счет того, что в результате этой раскраски некоторые из наших множеств в итоге, все-таки оказались одноцветными. То есть да, мы тупо с вероятностью одна вторая красили и в итоге получили, что часть множеств целиком покрашена в красный или целиком покрашена в синий цвет. Конечно, если это произошло, то все, неприятность и мы не победили, мы не доказали существование нужной нам раскраски. Поэтому давайте сделаем так. Определим некое множество D, которое состоит из элементов, принадлежащих одноцветным множествам. Что-то, давайте так, множество всех элементов множества: 1, 2, ..., v. Множество всех элементов из вот этого множества, которые в результате этапа 1, оказались принадлежащими одноцветным множествам Mi-тые, которые в результате этапа 1, оказались принадлежащими одноцветным множествам Mi-тое. Это такие вредоносные, если хотите, опасные элементы, они для нас плохи, они принадлежат тем множествам, которые вредят гармонии, так сказать. Мир не гармонично устроен. Мы запустили вот эту вот раскраску и некоторые множества оказались одноцветными, но ясно, что элементы этих одноцветных множеств — это пакость. Их надо как-то поправить. Их надо перекрасить, поменять их цвета. Тогда, возможно, гармония все-таки наступит. То есть надо что-то сделать вот с этим пакостным множеством D и вот это что-то делается на этапе с номером 2.