§ 1. Метод математической индукции

— "Знаете ли вы украинскую ночь?" — с чувством начал Оська.
- Нет, нет!!! — закричал зал. — Не знаем! Просим! Просим!
- "Нет, вы не знаете украинской ночи!" — продолжал немного смущенный Оська.
— Ясно, не знаем, — согласились матери.— Откуда нам знать? Какое наше воспитание было?
Л. Кассиль "Кондуит и Швамбрания"

Знаете ли вы, что такое математическая индукция?

"3наем, знаем!" — чудится мне ответ читателей. "Пусть в очереди первой стоит женщина, и за каждой женщиной пусть стоит женщина. Тогда все в очереди — женщины!" — вот шутливая формулировка принципа математической индукции. А вот серьезная: "Пусть имеется последовательность утверждений Y₁, Y₂, Y₃, ... Пусть первое утверждение Y₁ верно, и пусть за каждым верным утверждением Y_k стоит верное утверждение Y_k+1. Тогда все утверждения Y_n верны".

Ну, что ж. Это действительно так. Поскольку за каждым верным утверждением Y_k следует верное утверждение Y_k+1 и поскольку утверждение Y₁ верно, то утверждение Y₂ верно; а раз Y₂ верно, то и Y₃ верно; но тогда и Y₄, следующее за Y₃, верно, и т. д.

И все-таки, мне кажется (вы уж меня простите): "Нет, вы не знаете, что такое математическая индукция!" А впрочем, давайте проверим.

Впереди вас ждут несколько испытаний: в § 2 и § 3 — попроще, в § 4 и § 5 — посложнее.

§ 2. Фокус — покус

Если на клетке слона написано "буйвол", не верь глазам своим.
Козьма Прутков. Афоризмы

С помощью метода математической индукции можно обосновать следующий поразительный фокус.

Вырежьте из картона 999 одинаковых карточек. На 111 карточках напишите 1, на 111 карточках — 2, и т. д., на последних 111 карточках напишите 9. Переверните все карточки цифрой вниз и тщательно перемешайте. Затем возьмите совершенно произвольно n карточек, где n — любое целое число от 1 до 100, и положите их на стол цифрой вверх. Тогда цифры, написанные на всех n выбранных карточках, обязательно окажутся одинаковыми! Сколько бы раз ни повторять этот фокус и какое бы n ни выбирать (1≤n≤100), результат неизменно будет один: на всех n карточках будет одна и та же цифра! Каждый может на досуге проверить сказанное экспериментально, а сейчас докажем этот замечательный факт по индукции.

Нам нужно доказать утверждение Y_n: На всех n выбранных карточках (1≤n≤100) окажется одна и та же цифра. Фактически здесь имеется 100 утверждений: Y₁, ..., Y₁₀₀ (в зависимости от того, какое значение принимает n).

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

Докажем теперь, что если утверждение Y_n верно при n = k (где k — любое целое число от 1 до 99), то оно верно и при n = k + 1.

Положим на стол цифрой вверх k + 1 карточку. Одну карточку (назовем ее A) на минутку снимем со стола. На столе останется k карточек. На них (по предположению индукции) написана одна и та же цифра (некоторая цифра X).

Итак, на всех карточках — кроме, быть может, A — написана цифра X.

Заменим теперь одну из k карточек на столе карточкой А. На столе по-прежнему k карточек, значит, по предположению индукции, на них всех написана одна и та же цифра (которую мы выше обозначили через X). В том числе цифра X написана и на карточке А, которую мы вначале сняли, а теперь вернули на стол.

Итак, на карточке А тоже написана цифра X.

Значит, на всех n карточках (n = k + 1) написана цифра X, что и требовалось доказать.

Таким образом, в терминах § 1 утверждение Y₁ верно, и за каждым верным утверждением Y_k (1≤k≤99) следует верное утверждение Y_k+1. Следовательно, все утверждения Y_n верны (1≤n≤100). И как ни поразителен наш фокус с карточками, он теперь обязан всегда получаться — это строго доказано!

§ 3. На пальцах

Из мешка вывалился большой, крайне
рассерженный двупалый ленивец.
Дж. Даррелл. Три билета до Эдвенчер

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

Последнее утверждение заслуживает, нам кажется, того, чтобы остановиться на нем подробнее. Итак, соберем вместе совершенно произвольных n девушек, — тогда (сейчас мы это докажем) у них у всех глаза окажутся одинакового цвета.

При n=1 это утверждение очевидно (хотя и малосодержательно). Переход от n = k к n = k + 1 поясним буквально "на пальцах" (рис. 1). Для этого возьмем k = 4, k + 1 = 5, по числу пальцев на руке.

Согласно предположению индукции, у всяких четырех девушек глаза одинакового цвета. Соберем вместе 5 совершенно произвольных девушек (A, В, С, D и Е). По предположению индукции у любых четырех из них глаза одинакового цвета. В частности, у всех, кроме A, глаза такого же цвета, как у С, и у всех, кроме Е, глаза тоже такого же цвета, как у С. Итак, у любых пяти девушек глаза одинакового цвета.

При больших k доказательство проходит без всяких изменений (только, если вы захотите проводить его "на пальцах", вам, возможно, придется пригласить на помощь нескольких приятелей).

Упражнения

1. Если вы сомневаетесь в справедливости доказанного утверждения, "можете испытать экспериментальный подход, заглянув в глаза нескольким девушкам" (Пойя. Математика и правдоподобные рассуждения.)

2. Если имя биолога и писателя Дж. Даррелла не было знакомо вам раньше, то эпиграф к § 3 уже сыграл свою основную роль: настоятельно советуем вам скорее познакомиться с книгами Даррелла, интересными и полными своеобразного мягкого юмора. Выбирая эпиграф, мы преследовали, однако, кроме чисто пропагандистских целей, еще одну цель. Как вы думаете — какую?

Указание. Эпиграф имеет некоторое отношение и к заглавию § 3, и к его содержанию, и к содержанию § 2. (Отметим, что всякие ассоциации с заголовком § 4, напротив, случайны.)

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

Случай 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₁ знает, что кое-кто не испачкался.

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

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

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

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

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

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

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

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

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

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

При n = 1 она очевидна: если проводник приходил, то M₁ знает из его объявления, что кто-то испачкался, если же проводник не приходил, и лицо испачкано только у M₁, то ему неоткуда знать об этом; то есть в первом варианте 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

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

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

Никто не пойдет мыться и в том случае, когда n>1 и не все 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 справедливо. Проверьте это.