Задача о ленивых мудрецах

Задача О ленивых мудрецах http://www.problems.ru/articles/215.php

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

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

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

Переход от n = k к n = k + 1. Покаж, что если утверждение верно при n = k, то оно верно и при n = k + 1. Пусть лица испачканы у мудрецов M₁, ..., M_k+1. Тогда M_k+1 видит вокруг k грязных лиц (M₁ , ..., M_k) и рассуждает так:"Возможно 2 случая:

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

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

Но возможен, и 2-й случай: может быть у меня тоже грязное лицо. Тогда, однако, каждый из перемазавшихся мудрецов M₁, ..., M_k видит вокруг себя k испачканных лиц. В этой ситуации никто из них — мудрых и неторопл — не пойдет умываться на k-й Итак, если мудрецы M₁, ..., M_k не пойдут мыться на k-й остановке, значит, я — грязный, и мне надлежит идти умываться. Дождусь k-й остановки. Если на ней никто не пойдет умываться, придется выйти на следующей — (k+1)-й остановке и вымыть лицо!"

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

все они пойдут умываться, что и требовалось доказать.

3адачи

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

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

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

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

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

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

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

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

Пост себя на место M₂, попр повторить рассуж § 4.Возм 2 случая:

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

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

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

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

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

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

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

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

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

При n2 каждому мудрецу и без объявл провод стан известно не только то, что кое-кто испачкался, но и то, что все оста знают об этом. Пусть, напр, грязных мудрецов— трое: M₁, M₂ и M₃. Тогда M₂ знает, что M₁ видит грязное лицо M₃. Тем самым, M₂ знает, что M₁ знает, что кое-кто (например, M₃) испачкался.

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

Сл n = 3. Если прово приходил, то M₃ знает, что M₂ знает, что M₁ знает, что кое-кто испачкался, а если не приходил, то M₃ знать об этом неоткуда.

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

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

Нам в общем сл придется сделать не три — четыре, а n оборотов. Обоз через U_k такое утв: M_k знает, что M_k-1 знает, ..., что M₂ знает, что M₁ знает, что кое-кто испачкался.

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

Пусть проводник приходил, и пусть лица испачк у мудр М₁, ..., M_n (и, быть, еще у кого-нибудь). Тогда утве U_n справедливо. 
Пусть проводник не приходил и пусть лица испачканы у мудрецов M₁, ..., M_n (и только у них). Тогда утв U_n несправедливо.

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

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

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

I вар (провод приходил). Лица испач у M₁, ..., M_k+1. Зна, в частн, они испач у M₁, ..., M_k. Значит, по предп инд утв U_k справ. Это, раз, изв мудрецу M_k+1, т е M_k+1 знает, что M_k знает, ..., что M₂ знает, что M₂ знает, что кое-кто испачкался. Тем самым, утверждение U_k+1 справедливо.

II вар (проводник не приходил). Мудрец M_k-1 доп, что у него, может быть, чистое лицо. В этом сл, с его точки зрения, лица испач только у k мудр M₁, ..., M_k, и, след, — по предп индук — утв U_k неспр. Итак, доп, что у него чистое лицо, M_k+1 вынужден доп, что M_k не знает, что M_k-1 знает, ..., что M₂ знает, что M₁ знает, что кое-кто испачкался ^**).

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

Др сл, M_k+1 не знает, что M_k знает, ..., что M₂ знает, что M₁ знает, что кое-кто испачк, то есть утв U_k+1 несправ. Теорема доказана.

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

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

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

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

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

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

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

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

5. Наряду с утв U_e (справ, если проводник приходил, и неверн, если он не приходил) для различ сравн в § 5 вар м исп еще n! утве, кот получ из U_n всевозм перестан букв M₁, ..., M_n. Напр, M₁ знает, что M₂ знает, ..., что M_n знает, что кто-то испачкался.

Все эти n! утв содержат по n оборотов. "Б короткие" (содерж не б чем n — 1 оборот) утв не позв разл вар, когда проводник приходил или не прих. Напр, утв U_n-1 спра и без объявл проводника, так как M_n-1 знает, что M_n-2 знает, ..., что M₂ знает, что M₁ знает, что M_n испачкался.

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

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

^**) Фактич M_k знает об этом, то есть фактич — а не с т зр M_k+1, предпол что у него чистое лицо - утв U_k справ. Проверьте это.