§ 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
Search
Member List
Help
