Таблицы Брадиса

Докажем, что из любого города

Докажем, что из любого города

Элементы математики в задачах - Г. А. Мерзон

 

112                      Метод математической индукции

в) В стране несколько городов, некоторые пары которых соеди­нены дорогами, причем каждый город соединен хотя бы с одним другим. Докажем, что из любого города можно проехать в любой другой по дорогам. Будем доказывать индукцией по числу городов. База индукции для стран, состоящих из одного города, очевидна. Докажем шаг индукции. Возьмем какую-нибудь страну из п горо­дов и добавим к ней еще один город. Между старыми городами можно проехать по старым дорогам, так что достаточно доказать, что из нового города можно проехать в любой из старых. По усло­вию задачи из этого города ведет дорога в один из старых городов. Следовательно, из него можно доехать в один из старых городов, а оттуда уже добраться до любого другого. Итак, в новой стране тоже можно из любого города доехать до любого другого, и шаг индукции доказан.

Решение. а) Не проверена база индукции. При п = 1 получается оче­видно неверное неравенство 1 > 2.

б)  Ошибка в шаге индукции. Приведенное рассуждение «прохо­дит» для всех п, кроме п = 2. В этом случае п — 2 равно 0, и, убрав коров А и В, мы не оставим в стаде ни одной коровы. С другой стороны, если бы вдруг утверждение оказалось верным для п = 2, то несложно было бы показать, что оно верно для любого п.

в) Ошибка в шаге индукции. В приведенном рассуждении берется какая-то страна из п городов, и в ней строится новый город. Но при доказательстве шага индукции требуется доказать утверждение для любой страны из п +1 города, а не только для стран, получающихся описанным выше способом. Например, страна, состоящая из четырех городов, в которой первый город соединен дорогой со вторым, а третий — с четвертым, не может быть получена из страны, удовле­творяющей условиям задачи, добавлением еще одного города.