Wake of Gods Forum | Форум Во Имя Богов

Потому что гладиолус проводник не джентельмен

§ 4. О ленивых мудрецах

Три дамы А, В и С сидят в купе железнодорожного вагона
с испачканными лицами и все три смеются.
Внезапно А соображает: почему В не понимает,
что С смеется над ней? — О, боже! Они смеются надо мной.
Дж. Литлвуд. Математическая смесь

Едут в вагоне поезда N мудрецов. За окнами прелестный пейзаж.

Поезд то и дело ныряет в туннели. Дух захватывает. Собрались все мудрецы в коридоре вагона, в открытые окна глядят, не наглядятся.

Вдруг в одном туннеле грохот, дым, пыль! Грязь какая-то в окна посыпалась. Проехали туннель — входит проводник. "Тут кое-кто испачкался, — говорит. — В поезде, к сожалению, воды нет. Но сейчас подряд большие остановки пойдут, так что можно будет выйти из поезда и помыться".

Надобно вас теперь предупредить— мудрецы в вагоне собрались как на подбор: столь же умные, сколь ленивые. Никто, скажем, зря мыться не пойдет (если не знает наверняка, что испачкался). И у соседей не спросит, чистое у него лицо или грязное — зачем напрасно людей тревожить и самому беспокоиться? — проще сообразить,

Что же сделают мудрецы после объявления проводника?

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

Докажем сделанное утверждение по индукции.

Случай n = 1. При n = 1 утверждение очевидно. Мудрец M1 с грязным лицом узнает из объявления проводника о том, что в вагоне имеются пассажиры с испачканными лицами. Оглядев соседей, он обнаруживает, что у них лица чистые. Значит, грязное лицо — именно у него. Поэтому на 1-й остановке он идет мыться.

Переход от n = k к n = k + 1. Покажем, что если утверждение справедливо при n = k, то оно верно и при n = k + 1.

Пусть лица испачканы у мудрецов M1, ..., Mk+1. Тогда Mk+1 видит вокруг k грязных лиц (M1 , ..., Mk) и рассуждает так:

"Возможны два случая:

1) у меня чистое лицо;
2) у меня грязное лицо.

В 1-м случае все k мудрецов с грязными лицами, которых я вижу вокруг, выйдут умываться на k-й остановке (так как по предположению индукции при n = k утверждение справедливо).

Поскольку 1-й случай возможен, мне не следует выходить ни на k-й остановке, ни раньше: если я чистый, это было бы непростительной тратой сил! К такому выводу пришел бы на моем месте любой умный и не склонный к напрасной суете человек *).

Но возможен, разумеется, и 2-й случай: может быть, у меня тоже грязное лицо. Тогда, однако, каждый из перемазавшихся мудрецов M1, ..., Mk видит вокруг себя k испачканных лиц. В этой ситуации никто из них — мудрых и неторопливых — не пойдет умываться на k-й остановке (см. предыдущий абзац).

Итак, если мудрецы M1, ..., Mk не пойдут мыться на k-й остановке, значит, я — грязный, и мне надлежит идти умываться. Дождусь k-й остановки. Если на ней никто не пойдет умываться, придется выйти на следующей — (k+1)-й остановке и вымыть лицо!"

Так же рассуждают все мудрецы с грязными лицами. Следовательно, на (k+1)-й остановке все они пойдут умываться, что и требовалось доказать.

3адачи

1. Изменим слегка наш рассказ. Зная, что в вагоне едут мудрецы, и увидав, что многие из них испачкались, проводник решает сократить свое объявление.

"Зачем же мне говорить, что кое-кто испачкался, — думает он, — когда они и сами это видят!" И пропускает первую фразу объявления.

Можно ли по-прежнему утверждать, что если лица испачканы у n человек, то на n-й остановке они пойдут мыться?

2. Внесем в рассказ другое изменение.

Пусть в тот момент, когда поезд проходил через злосчастный туннель, часть мудрецов была в своих купе: кто в окно смотрел, кто дремал...

Громкий голос проводника, который на этот раз опять произнес полный текст объявления, по счастливой случайности услышали все, но поручиться, что и другие слышали объявление, никто бы не смог. Через некоторое время (еще до первой остановки) все мудрецы собрались в коридоре вагона...

Вопрос тот же, что в задаче 1.

Предупреждение. Если вы хотите решить предложенные задачи сами (без подсказок), то не читайте пока § 5.

§ 5. Что сказал проводник?

Иль думал, что я думала, Что думал он: Я сплю!
С. Маршак Из Ковентри Патмора

Пусть мудрецы и сами — без проводника — знали и про то, что в поезде нет воды, и про то, что после туннелей пойдут долгие стоянки, на которых можно умыться. Кроме того, пусть в грязном туннеле испачкался больше чем один человек. Тогда в объявлении проводника нет как будто вообще ничего нового ни для кого из мудрецов!

Так что же — если бы проводник вовсе не приходил — пошли бы n испачкавшихся мыться на n-й остановке?

Велик соблазн ответить "Да": раз ничего не изменилось в условии задачи, то не должен, казалось бы, измениться и ответ! И все же здравый смысл подсказывает, что без объявления проводника мыться, пожалуй, никто не пойдет!! И потом — что значит: "ничего не изменилось в условии"? Все-таки в одном варианте проводник вообще не приходил, а в другом — приходил и что-то сказал!!!

Что же, наконец, он сказал?

Одними восклицаниями этот вопрос, по-видимому, не решишь. Поэтому хладнокровно и скрупулезно проанализируем простейший возможный случай: n = 2 (положить n = 1 мы не можем, так как дано, что испачкался больше чем один человек).

Случай n = 2. Лица испачканы у мудрецов M1 и M2. Они видят друг друга, и поэтому каждый из них, действительно, знает, что кто-то испачкался.

Поставив себя на место M2, попробуем повторить рассуждения § 4.

"Возможны 2 случая:

1) у меня чистое лицо;
2) у меня грязное лицо.

В 1-м случае M1 видит только чистые лица, но он знает, что кто-то испачкался. Поэтому..."

Стоп! M1, действительно, знает, что кто-то испачкался, но откуда об этом известно M2? Откуда, собственно, M2 знает, что M1 знает, что кто-то испачкался?

...Наконец-то, мы, кажется, нащупали ключ к решению.

Если проводник проходил, то его объявление, и правда, не было новостью для M1 и M2. Но M2 видел, что M1 слушал это объявление. Поэтому-то, если проводник приходил, то M2 знает, что M1 знает, что кто-то испачкался.

Если же проводник не приходил, то знать M2 об этом неоткуда. В самом деле, мы-то знаем, что у M2 грязное лицо, и поэтому знаем, что M1 знает, что кое-кто (может быть, только M2, а может быть и он тоже) испачкался, но сам M2 допускает возможность, что у него чистое лицо, и что M1 видит, следовательно, только чистые лица. Но если M1 не видит грязных лиц и если проводник не приходил, то M1 неоткуда узнать, что кто-то испачкался. Значит, если проводник не приходил, то M2 неоткуда узнать, что M1 знает, что кое-кто испачкался.

Упражнение. Пусть проводник не приходил, n = 2; испачкались мудрецы M1 и M2, мудрец М не испачкался. Какие из следующих утверждений верны?

a) M2 знает, что М знает, что кое-кто испачкался,
b) M знает, что M1 знает, что кое-кто испачкался,
c) M2 знает, что М знает, что M1 знает, что кое-кто испачкался,
d) M2 знает, что M1 знает, что кое-кто не испачкался.

Дальнейший анализ.

При n>2 каждому мудрецу и без объявления проводника становится известно не только то, что кое-кто испачкался, но и то, что все остальные знают об этом. Пусть, например, грязных мудрецов— трое: M1, M2 и M3. Тогда M2 знает, что M1 видит грязное лицо M3. Тем самым, M2 знает, что M1 знает, что кое-кто (например, M3) испачкался.

Различие между вариантами, когда проводник приходил или не приходил, при n>2 становится поэтому еще тоньше. Сформулируем его точно для n = 3.

Случай n = 3. Если проводник приходил, то M3 знает, что M2 знает, что M1 знает, что кое-кто испачкался, а если не приходил, то M3 знать об этом неоткуда.

Упражнение. Проверьте последнее утверждение.

Общий случай. Один знаменитый философ как-то заметил: Если человек говорит фразу "Я думаю о том, что я думаю о том, ...", то уже на третьем — четвертом обороте теряет смысл произносимого.

Нам в общем случае придется сделать не три — четыре, а n оборотов. Обозначим через Uk такое утверждение: Mk знает, что Mk-1 знает, ..., что M2 знает, что M1 знает, что кое-кто испачкался.

Тогда различие между сравниваемыми вариантами можно сформулировать в виде следующей теоремы:

Пусть проводник приходил, и пусть лица испачканы у мудрецов М1, ..., Mn (и, может быть, еще у кого-нибудь). Тогда утверждение Un справедливо.
Пусть проводник не приходил и пусть лица испачканы у мудрецов M1, ..., Mn (и только у них). Тогда утверждение Un несправедливо.

Докажем эту теорему по индукции.

При n = 1 она очевидна: если проводник приходил, то M1 знает из его объявления, что кто-то испачкался, если же проводник не приходил, и лицо испачкано только у M1, то ему неоткуда знать об этом; то есть в первом варианте U1 справедливо, а во втором — несправедливо.

Переход от n = k к n = k+1 проводится так.

I вариант (проводник приходил). Лица испачканы у M1, ..., Mk+1. Значит, в частности, они испачканы у M1, ..., Mk. Значит, по предположению индукции утверждение Uk справедливо. Это, разумеется, известно мудрецу Mk+1, то есть Mk+1 знает, что Mk знает, ..., что M2 знает, что M2 знает, что кое-кто испачкался. Тем самым, утверждение Uk+1 справедливо.

II вариант (проводник не приходил). Мудрец Mk-1 допускает, что у него, может быть, чистое лицо. В этом случае, с его точки зрения, лица испачканы только у k мудрецов M1, ..., Mk, и, следовательно, — по предположению индукции — утверждение Uk несправедливо. Итак, допустив, что у него чистое лицо, Mk+1 вынужден допустить, что Mk не знает, что Mk-1 знает, ..., что M2 знает, что M1 знает, что кое-кто испачкался **).

И вместе с тем выяснено, наконец, что же сообщил мудрецам проводник. Чем n больше, тем, оказывается, больше узнали из его объявления мудрецы — имеющий уши да слышит!

Другими словами, Mk+1 не знает, что Mk знает, ..., что M2 знает, что M1 знает, что кое-кто испачкался, то есть утверждение Uk+1 несправедливо.

Теорема доказана.

§ 6. Точки над i

Читателям, добравшимся через все препятствия до конца § 5, вряд ли понадобятся следующие разъяснения. Все-таки, "для порядка", дадим их.

1. В § 3 переход от k = 4 к k + 1 = 5 проделан без ошибок. Верно и то, что при больших k доказательство проходит без изменений. Нетрудно также перейти от n = 2 к n = 3 и от n = 3 к n = 4. Не получается "только" переход от n = 1 к n = 2. Он не может получиться потому, что при n = 2 утверждение неверно: не у любых двух девушек глаза одинакового цвета.

Если все-таки попытаться провести доказательство "на пальцах" и в этом случае, то ничего не выйдет (в § 3 мы соединили A и E "мостиком" С: и у A, и у E глаза оказались такого же цвета, как у С; если пальцев всего два, то такого мостика нет).

Двупалый ленивец из эпиграфа призван был привлечь внимание к указанному исключительному случаю.

2. В § 2 утверждение Y2 верно, а все утверждения Yn, начиная со второго, неверны. Переход от n = k к n = k + 1 обоснован правильно для k≥2. Переход от n = 1 к n = 2 содержит ошибку: когда мы убираем карточку A, на столе остается одна карточка; на ней написана одна цифра, но вовсе не обязательно цифра X.

3. Если оставить в стороне вопрос, знал ли M2, что M1 знает, что умываться нужно не в поезде, а на стоянках (и если знал, то знал ли об этом M3 и т. д.), то разобранная в § 5 задача эквивалента задаче 1 из § 4. Тем самым, если проводник не объявил, что "кое-кто испачкался", то никто из мудрецов мыться не пойдет (ни на n-й, ни на какой другой остановке).

Никто не пойдет мыться и в том случае, когда n>1 и не все n испачкавшихся мудрецов находились вместе\t во время объявления проводника (задача 2 из § 4). Доказательство аналогично проведенному в § 5, только индукцию нужно начинать с n = 2: при n = 1 единственный испачкавшийся мудрец пойдет мыться на 1-й остановке независимо от того, где он был во время объявления проводника.

4. В 1-м упражнении из § 5 утверждения а), b) и d) верны, а утверждение с) неверно.

5. Наряду с утверждением Ue (справедливым, если проводник приходил, и неверным, если он не приходил) для различения сравниваемых в § 5 вариантов можно использовать еще n! утверждений, которые получаются из Un всевозможными перестановками букв M1, ..., Mn. Например, M1 знает, что M2 знает, ..., что Mn знает, что кто-то испачкался.

Все эти n! утверждений содержат по n оборотов. "Более короткие" (содержащие не более чем n — 1 оборот) утверждения не позволяют различить варианты, когда проводник приходил или не приходил. Например, утверждение Un-1 справедливо и без объявлении проводника, так как Mn-1 знает, что Mn-2 знает, ..., что M2 знает, что M1 знает, что Mn испачкался.

6. Смешливая дама из эпиграфа к § 4 догадалась, что у нее грязное лицо, хотя никакой проводник не делал никаких объявлений. Роль проводника сыграл несдержанный смех ее соседок. Степенные мудрецы, конечно, не позволили бы себе ничего подобного!

*) Вероятно, так мысленно именует он свою лень.

**) Фактически Mk знает об этом, то есть фактически — а не с точки зрения Mk+1, предположившего, что у него чистое лицо - утверждение Uk справедливо. Проверьте это.
*********************
скопировано с сайта http://www.problems.ru

то, что 1й и 2й будут стрелять в 3го, а 3й во 2го - это понятно.
считаем их вероятности выжить в первом раунде:
1) 1 (в него никто не стреляет)
2) 0 (3й попадает с вероятностью 1)
3) выживет, если 1й и 2й оба промахнутся: (1-1/3)*(1-1/2)=1/3
итого с вероятность 2/3 в конце первого раунда остается один 1й и выигрывает, с вероятностью 1/3 1й остается один на один с 3м и обречен на проигрыш.

стрельба идёт по очереди поэтому когда первый выстрелил в третьего он мог в него попасть тогда 2й выстрелит в первого, т.о. вероятность первого выжить после первого раунда уже меньше единицы

тогда в оставшейся 1/3 у первого еще есть шанс попасть по третьему. итого его шанс выиграть вообще равен 2/3+1/3*1/3=7/9

в предложенном алгоритме такой итог: первый стреляет в третьего. если попадает. то после этого второй стреляет в него и он выживает с вероятностью 1/3*1/2. если не попадает, то после этого второй стреляет в первого. если второй попадает то шанс первого выжить после одного раунда 2/3*1/2, в противном случае третий застрелит второго и получим еще 2/3*1/2, итого 5/6 шанс выжить после ПЕРВОГО раунда. дальше что?

то мой последний вариант 1/6 на победу 1-го.

да, снова упустил очередность. в общем после сложных вычислений у меня вышло 25/36

в кораблекрушении его друг кормил его человеческим мясом и говорил, что это мясо альбатроса.