Вероятностные доказательства

11

Вероятностные доказательства

А.ШЕНЬ

Неравенства и оценки Начнем с совсем простой задачи. 1. На доске написаны 10 чисел. Сумма любых двух из них не меньше 5. Докажите, что сумма всех чисел не меньше 25. ⊳ Тут даже и доказывать-то особо нечего: разобьем числа на пять пар. В каждой паре сумма не меньше 5, всего получается 25. ⊲

Теперь немного более сложная задача. 2. На доске написаны 9 чисел. Сумма любых двух из них не меньше 5. Докажите, что сумма всех чисел не меньше 22,5. (Если все числа равны 2,5, то и получится 22,5.) ⊳ Рассуждая аналогично предыдущей задаче, можно выбрать четыре пары, и одно число останется. В каждой паре сумма не меньше 5, всего 20. Если бы мы знали, что оставшееся без пары число не меньше 2,5, то мы получили бы требуемое. Но гарантировать это мы не можем. Скажем, если одно из чисел равно нулю, а остальные равны 5, то сумма любых двух будет не меньше 5 (а именно, 5 или 10). При этом непарным может оказаться ноль. Наверное, вы уже сообразили, как завершить рассуждение. Разбиение на пары в наших руках, и мы можем оставить непарным любое из чисел. В любой паре хотя бы одно из чисел равно 2,5 или больше. Нам

в каждой из которых сумма не меньше 5. Всего получается как минимум 3 ◊ 5 + ( 5 3 ) = 50 3. ⊲

В двух предыдущих задачах оставалось одно число. А что будет, если останется два? 4. На доске написаны 11 чисел. Сумма любых трех из них не меньше 5. Докажите, что сумма всех чисел не меньше 55/3. Можно решить эту задачу аналогично предыдущим (см. задачу 14 и указание к ней). Но мы приведем другое решение, которое обобщается на любые количества. ⊳ Обозначим наши числа $a_{1}$, … $, a_{11}$ и запишем их по кругу. Сумма любой тройки соседей не меньше 5 (по условию):

$a_{1} + a_{2} + a_{3} \ge 5,$

$a_{2} + a_{3} + a_{4} \ge 5,$

… $a_{9} + a_{10} + a_{11} \ge 5,$

$a_{10} + a_{11} + a_{1} \ge 5, a_{11} + a_{1} + a_{2} \ge 5.$

Сложим эти одиннадцать неравенств. Каждое число встречается три раза (входит в три тройки), поэтому получится

$3 ( a_{1} + a_{2} +^{…} + a_{11} ) \ge 55$, откуда и следует требуемое. ⊲

Вероятности и ожидания достаточно знать, что хотя бы одно из чисел таково – можно оставить непарным именно это число, и все получится. ⊲ Усложним задачу еще немного. 3. На доске написаны 10 чисел. Сумма любых трех из них не меньше 5. Докажите, что сумма всех чисел не меньше 50/3. ⊳ Используем тот же прием: в любой тройке чисел большее равно 5/3 или больше (иначе все три числа меньше 5/3, и сумма меньше 5). Возьмем одно из таких чисел (не меньших 5/3), останутся три тройки,

Сейчас мы рассмотрим другое решение последней задачи – на языке теории вероятностей. Пусть в ящике (или, как любят говорить в теории вероятностей, в урне) лежат 11 шаров, на которых написаны числа $a_{1}, a_{2}$, … $, a_{11}$. Мы вынимаем один из шаров не глядя, и нам дают столько рублей, сколько на нем написано. Сколько мы будем выигрывать в среднем за игру, если играть много раз? Мы имеем в виду, что каждый раз вынутый шар возвращают в урну и ее содержимое перемешивают. Несложно сообразить, что ответ тут –

13

ВЕРОЯТНОСТНЫЕ

образом. При большом количестве испытаний доля случаев, когда вершина A попадает в пятно (вероятность события «A черная») равна 1/10, поскольку вершина A равномерно распределена по всей сфере. По тем же причинам вершина B оказывается черной в 10% случаев, и то же самое можно сказать про любую из 8 вершин. Значит, остается как минимум 20% = 100% – 80% случаев, в которых все вершины белые (может быть больше за счет случаев, когда несколько вершин черные). Поэтому куб можно вписать требуемым способом. ⊲ На самом деле тут мы уже серьезно жульничаем и заметаем под ковер основную часть рассуждения: почему слова «случайно вписанный куб» имеют смысл и почему вершина равномерно распределена по сфере. Интуитивно это выглядит правдоподобно и действительно может быть строго обосновано (хотя я не знаю никакого решения этой задачи в рамках школьной программы).

Случайные раскраски

Рассмотрим произвольный граф – несколько точек (вершин), соединенных линиями (ребрами). Раскрасим вершины графа в два цвета (скажем, черный и белый). Ребро назовем разноцветным, если оно (как вы уже догадались) соединяет вершины разных цветов. Количество разноцветных ребер зависит от раскраски. Если мы хотим сделать это число минимальным, нет ничего проще – достаточно покрасить все вершины в один и тот же цвет. А что будет, если мы хотим сделать его максимальным (для данного графа)? Ответ зависит от графа, но оказывается, что всегда можно гарантировать как минимум половину разноцветных ребер. 8. Докажите, что в произвольном графе можно раскрасить вершины в два цвета таким образом, чтобы как минимум половина ребер оказались разноцветными. ⊳ Будем раскрашивать вершины случайным образом (для графа с n вершинами возможно $2^{n}$ раскрасок, и мы считаем все их равновероятными). Для каждой раскраски посчитаем, сколько ребер окажутся разноцветными. Это, как говорят, «случайная величина» – она зависит от выбора раскраски. Каково ее математическое ожидание (среднее значение при большом числе испытаний)? Другими словами, пусть в каждой вершине графа бросают монету (независимо от других вершин, так что все комбинации равновероятны), а на каждом ребре дежурит игрок, который получает рубль, если ребро окажется разноцветным (монеты в его концах выпадут по-разному). Сколько в среднем будут зарабатывать игроки за игру? Каждый игрок в среднем выигрывает в половине игр (есть четыре варианта комбинации цветов на концах ребра, и в двух из них оно разноцветное). Значит, каждый игрок в среднем выигрывает полтинник за игру, а вся команда в среднем выигрывает V/2 рублей, где V – число ребер.

ДОКАЗАТЕЛЬСТВА

Отсюда очевидно следует, что есть раскраски, когда не менее половины ребер разноцветные (иначе бы в каждой игре команда выигрывала меньше V/2, и среднее тоже было бы меньше V/2). ⊲ На самом деле это утверждение имеет простое конструктивное доказательство (см. задачу 19).

Случайные проекции

В этом разделе мы применим вероятностные соображения для решения такой задачи. 9. На плоскости нарисована выпуклая фигура, ограниченная кривой длины L. Докажите, что ее диаметр, т.е. максимальное расстояние между двумя ее точками, не меньше $L \pi$. Появление здесь числа $\pi$ не случайно: неравенство задачи обращается в равенство для случая окружности диаметра $D = L \pi$. ⊳ Мы докажем более сильное утверждение: средняя длина проекции нашей фигуры на случайное направление равна $L \pi$. (Мы проводим прямую в случайно выбранном направлении, и потом из каждой точки фигуры опускаем перпендикуляр на эту прямую. Получается отрезок – проекция фигуры на прямую.) Из этого утверждения следует, что найдется направление, проекция на которое имеет длину не меньше $L \pi$ (среднее значение не может быть больше всех). А тогда и точки фигуры, которые попадают в концы проекции, находятся на таком же или большем расстоянии (наклонная длиннее перпендикуляра). Как же доказать обещанное? Рассмотрим кривую, ограничивающую фигуру. Проекция фигуры – это все равно что проекция ее границы. Разобьем эту кривую на множество очень маленьких частей – настолько маленьких, что каждую из них можно считать отрезком. Пусть все эти отрезки будут равной длины. Проекция всей границы складывается из проекций этих отрезков. Точнее, удвоенная проекция всей границы равна сумме проекций отрезков (так как они покрывают ее два раза – туда и обратно). Это верно для любого направления проектирования – значит, и удвоенная средняя длина проекции фигуры равна сумме средних длин проекций каждого из отрезков, составляющих ее границу. Но отрезки эти равной длины, и потому средние длины их проекций одинаковы (поскольку мы проектируем на случайное направление, то направление самого отрезка роли не играет). Значит, средняя длина проекции

14

КВАНТ 2009/№6

кривой зависит только от числа этих отрезков, т.е. пропорциональна длине кривой, и коэффициент пропорциональности можно вычислять на примере окружности. ⊲

Две коробки

10. В московском метро можно провозить коробки, у которых сумма измерений (длины, ширины и высоты) не превосходит некоторой границы. Возникает вопрос: можно ли перехитрить правила, поместив одну коробку внутрь другой? Другими словами, пусть один прямоугольный параллелепипед целиком содержится внутри другого. Может ли сумма измерений внутреннего быть больше суммы измерений внешнего? ⊳ Оказывается, что нет, но доказать это не так просто. Есть несколько красивых доказательств, и одно из них использует вероятностные соображения (примерно такие же, как в предыдущем разделе). Будем проектировать коробку на прямую случайно выбранного направления (в пространстве). Из картинки видно, что проекция коробки складывается из проекции трех отрезков, идущих по ее высоте, длине и ширине. Следовательно, средняя длина проекции (математическое ожидание) равно сумме средних длин проекций этих отрезков. А средняя длина проекции отрезка пропорциональна его собственной длине (с каким-то коэффициентом, нам сейчас не важно – с каким). Поэтому средняя длина проекции коробки пропорциональна сумме ее измерений. Теперь представим себе две коробки, одну внутри другой. На какую прямую их ни проектируй, проекция внутренней коробки всегда находится внутри проекции внешней и потому имеет меньшую или равную длину. Значит, и средние длины проекций находятся в том же соотношении, а они пропорциональны сумме измерений. ⊲

Случайные блуждания

11. На листке из тетрадки в клеточку нарисован лабиринт и в нем робот, который по командам «вверх», «вниз», «влево» и «вправо» ходит из клетки в клетку. Стены лабиринта идут по сторонам клеток, выхода из лабиринта нет. Если, начав двигаться по команде, робот упирается в стену, то он остается на месте. Мы не знаем, какой лабиринт нарисован, но знаем размер листка, измеренный в клеточках. Докажите, что можно составить последовательность команд, которая гарантирует, что робот побывает во всех клетках доступной ему части лабиринта. ⊳ Сразу же признаемся, что не только наше рассуждение будет чистым доказательством существования (без предъявления способа построения такой последовательности), но и длина такой последовательности будет астрономической. Будем давать роботу случайные команды и смотреть,

с какой вероятностью он обойдет лабиринт. Пусть в лабиринте есть замкнутый обход из не более чем N шагов. Тогда при любом начальном положении робота есть некоторая вероятность, что при подаче ему N случайных команд он пойдет как раз по этому пути и обойдет лабиринт. Она не меньше $4^{-} N$, а вероятность

(

) не обойти лабиринт не больше $1 - 4^{-} N$. Процесс можно повторять: если мы дадим 2N случайных команд, то вероятность не обойти лабиринт не больше

$( 1 - 4 )$ (неудача на первом этапе происходит в доле $( 1 - 4 )$ случаев или меньше, и в каждом из них

$- N^{2}$

$- N$ вероятность сокращается во столько же раз за счет второго этапа). Вообще, после Nk случайных команд вероятность неудачи (в данном лабиринте с данным начальным

(

) k положением) не больше $1 - 4^{-} N$. Хотя основание степени и близко к единице, но все равно это число можно сделать сколь угодно малым, увеличивая k. Заметим, что для всех лабиринтов на доске данного размера можно выбрать одно общее N.

(

) k

После этого возьмем k таким, чтобы $1 - 4^{-} N$ стало меньше 1/M, где M – число разных способов нарисовать лабиринт и робота внутри него (на листке бумаги данного размера их конечное число). Тогда для каждого из M вариантов расположения вероятность неудачи меньше 1/M, и потому с положительной вероятностью последовательность команд длины Nk окажется удачной для всех вариантов. Значит, такая удачная последовательность существует, что и требовалось доказать. ⊲

Несравнимые множества

В этом разделе мы предполагаем знакомство с элементами комбинаторики (множества, подмножества, число сочетаний). 12. Пусть A – множество из 2n элементов. Мы хотим выбрать несколько подмножеств множества A, причем требуется, чтобы они были несравнимы: ни одно из них не должно быть подмножеством другого. Какое максимальное число подмножеств можно выбрать? ⊳ Заметим, что требование выполняется, если все выбранные подмножества одного размера (и разные). Чтобы их число было максимальным, надо взять размер n, поскольку число сочетаний $C_{2} kn$ при данном n

25

ИНФОРМАЦИЯ

логическому анализу, результаты размышлений сверить с фактами или с аналогами из других концепций. Самостоятельное мышление – это не только понимание сути и основ теории и сферы ее применимости, умение выводить в ее рамках следствия для частных случаев и т.п. Необходимо еще понимать, что всякая теория имеет альтернативы, допускать эти альтернативы, быть готовым в любой момент отказаться от привычных концепций, если новые факты укладываются в их рамки «со скрипом» (тем более, когда выходят за эти рамки). Разумеется, существуют понятия, в основательности которых трудно усомниться. Например, окружающая нас реальность со всеми происходящими в ней процессами сплошь и рядом демонстрирует незыблемость и всеобщность следующих трех свойств: экономичность, симметричность и относительность (два последних в какой-то мере являются частными случаями первого). Возможно, этот список не является исчерпывающим и нуждается в дополнении (в будущем, скорее всего, так и случится). Но как бы то ни было, можно перечислить ряд положений, которые нельзя включать в этот список всеобщих понятий несмотря на то, что они считаются фундаментальными. Например, нельзя принять на веру, что электрон на земле и электрон на расстояниях в миллиарды световых лет от нее имеют в точности одну и ту же массу покоя. Трудно считать незыблемыми физическими константами такие безразмерные величины, как, например, постоянная тонкой атомной структуры, отношения масс элементарных частиц и т.п. Еще Эйнштейн сомневался в их, так сказать, случайном характере. Или это суть математические константы (т.е. выводятся в рамках какой-то неизвестной нам теории), или они не являются константами (т.е. меняются во времени и (или) в пространстве). Трехмерность окружающего нас пространства также является одним из постулатов современной теории, но пока нет оснований считать его незыблемым. Завершим эти примеры таким утверждением: возможность чего-либо невозможно опровергнуть! Иными словами, нельзя на практике доказать, что нечто невозможно. Это один из атрибутов бесконечности, демонстрирующий ограниченность логики. Объявляя наш конкурс, мы преднамеренно не конкретизируем задания для его участников. Содержательность ответа, как известно, зависит от качества вопроса. Как говорят, хороший вопрос – это половина ответа. Поэтому оцениваться будет и постановка проблемы тоже. Более того, решение может быть не самым удачным или даже неправильным, но это компенсируется качеством и актуальностью постановки вопроса. Помните, что вопросысигналы, поступающие из окружающего мира (факты, явления и т.п.), – это первооснова, сырье, которое еще предстоит в процессе изучения переработать, превратить в задачу. А затем уже надо анализировать четко поставленную задачу, определять круг описываемых явлений, область изменения и точность задания параметров, для которых решение будет корректно, и т.д. Мы специально не ограничиваем участников конкурса в выборе и формулировании вопросов. Пусть это будет что угодно, лишь бы оно имело определенный смысл. В современной науке и развивающихся технологиях есть множество проблем. В частности, это известные расходимости в квантовой теории, корректное определение тензора энергии-импульса в общей теории относительности, парадоксы в теории множеств, саморазвивающиеся компьютерные программы (включение в них случайных

выборов, учет опыта ошибок и т.п.). Да и в обыденной жизни найдется многое, что можно попытаться формализовать на языке математики (например, обнаружив определенное подобие, попробовать применить законы газовой динамики для … анализа движения машин на автостраде). Можно поставить задачу из серии «что было бы, если бы …» Или придумать новый вид взаимодействия. Или выяснить, какова была бы реальность, если бы, например, постоянная Планка оказалась заметно больше (или меньше) той, которая нам известна. Не так уж гипотетична задача, в которой какие-либо мировые константы можно было бы считать нестационарными. Например, красное смещение можно объяснить не только разбеганием галактик, но и тем, что со временем меняются масса электрона или постоянная Планка. Итак, мы не ждем от вас открытий. Нас особенно не интересует и ваша эрудиция, поэтому не бойтесь прослыть невежественными. Скорее всего, то, что мы от вас ждем (а вы нам пришлете), не принял бы ни один серьезный научный журнал. Наверное, серьезные ученые скорее всего отправляют подобное «творчество» в корзину, так же как следователь отбрасывает не оправдавшие себя версии. Но кто знает, может когда-нибудь среди такой «отработки» найдется то, что раньше упустили. Например, кто-то, роясь в этой общей корзине, наткнется на необычные идеи, которые послужат толчком для новых открытий. Но даже если все будет не так, мы надеемся достичь своей главной цели: помочь реализовать себя людям, способным к самостоятельному нестандартному мышлению и поиску. Так рождаются инновации. Сомневайтесь! Опровергайте! Предлагайте!

Условия проведения конкурса

Каждый участник представляет на рассмотрение жюри свой проект, содержащий сформулированную задачу и ее решение. (В отдельных случаях жюри готово рассматривать задачи с незавершенными решениями.) Общий объем отчета по проекту должен быть не более 10 машинописных страниц, при этом все громоздкие вычисления должны быть вынесены в приложения, которые являются составной частью отчета. Распечатанный вариант отчета (1 экз.) нужно прислать по почте в редакцию журнала «Квант» по адресу: 119296 Москва, Ленинский проспект, д. 64-А, а электронный отчет отдельным файлом нужно послать на электронный адрес редакции: admin@kvant.info. Титульный лист отчета должен содержать следующую информацию о конкурсанте: фамилия, имя, отчество; почтовый адрес, электронный адрес, телефон; данные об образовании, о наличии научной степени (если таковая имеется). Срок приема заявок на участие в конкурсе – до 15 апреля 2010 года. Итоги конкурса будут подведены в конце мая 2010 года. Работы, с согласия их авторов и заслуживающие общего внимания по мнению жюри, будут размещаться на специальном сайте фонда «Новая мысль» с указанием тех работ, которые отмечены премиями. Журнал «Квант», независимо от результатов участия работы в конкурсе, может (по согласованию с автором) опубликовать некоторые работы, подходящие по формату и идеологии журнала.