В 80-х годах XIX века в одной французской газете появилась статья. В ней рассказывалось о том, что где-то на севере Индии, высоко в горах, за непроходимыми джунглями, полными свирепых хищников, один европейский путешественник обнаружил уединённый монастырь. В центре главного храма стоит драгоценная святыня, божественная головоломка – 3 алмазных стержня, на которые нанизаны 64 золотых диска.
День и ночь монахи, распевая молитвы, перекладывают эти диски с одного стержня на другой по строгим правилам: а) за один ход можно перенести только один диск; б) во время хода диск большего размера ни в коем случае нельзя класть на диск меньшего размера. Как рассказали монахи путешественнику, сперва все божественные диски были нанизаны на крайний слева стержень. Задача же состоит в том, чтобы переложить все диски в правильном порядке на правый стержень – тогда все познают истину и наступит конец света...
Читатели этой легенде очень даже поверили. Во-первых, Индия – вообще страна загадочная, и каких только священников, монахов и прочих святых людей там не встречается, с самыми разными «заскоками». Кто-то занимается гимнастикой, кто-то спит на острых гвоздях, кто-то медитирует неподвижно в углу по нескольку месяцев и ничего не ест. «Не в наказание, а для просветления».
Или, скажем, выкладывают монахи на досках прекрасные и очень сложные картины из разноцветного песка – мандалы.
Каждая мандала создаётся несколько недель и даже месяцев, но как только она «почти совсем готова»...
...её (опять-таки, под молитвы) безжалостно сметают с доски!
Так монахи приучают себя к тому, что всё в материальном мире бренно, конечно, и в конце концов обратится в прах... В общем, почему бы не быть и алмазным стержням с золотыми дисками?
Небольшую модель такой «божественной головоломки» вполне можно сделать самому – из той самой детской пирамидки. Дисков совсем не обязательно должно быть 64 – скажем, в нашем с Лучиком случае их 8.
Попробуйте самостоятельно решить эту головоломку – переложите все диски с крайнего левого стержня на крайний правый по тем самым правилам: за один ход можно взять только один диск, и диск большего размера нельзя класть на диск меньшего размера.
Интересно, сумеете ли вы с этим справиться и сколько времени у вас уйдёт на решение? Если, конечно, вы не сталкивались с этой игрушкой-головоломкой раньше и не знаете правильный ответ...
Пока вы занимаетесь поиском решения, немножко поговорим о правдоподобности легенды. Вполне возможно, далеко в горах Индии и в самом деле спрятаны несметные сокровища, но не до такой же степени! Скажем, если наши алмазные стержни будут толщиной хотя бы в сантиметр, а длиной в метр, то общий вес стержня составит 275 граммов, или 1375 карат. Стоить один такой уникальный алмаз будет как минимум 50 миллиардов рублей! Да и золотые диски тоже «не пять копеек»... В общем, если бы такой храм существовал взаправду, то его разграбили бы уже давным-давно, как пирамиды египетских фараонов...
На самом деле эту задачку – она ещё называется «Башни Брахмы» или «Ханойские башни» – придумал французский математик, профессор Франсуа Люка.
С его подачи эта занимательная задача постоянно попадает в самые разные сборники задач и головоломок, детские (и взрослые!) журналы, и даже в современные компьютерные игры.
Давайте убедимся, что эта головоломка 100% решается для любого числа дисков. А для этого давайте максимально упростим задачу! Сколько у нас там дисков? Восемь? Не надо восемь. Давайте оставим только один! Ну как, решается эта задача?
«Да пара пустяков! – скажете вы. – Просто берём диск с первого стержня и перекладываем на третий, и всё!». Просто, не правда ли?
Тогда давайте возьмём два диска. Справитесь? «Тоже мне! – усмехнётесь вы чуть подумав. – Маленький диск с первого стержня перекладываем на второй, потом большой диск с первого стержня перекладываем на третий, а потом маленький со второго кладём на третий – и оп-ля!». И это абсолютно правильное решение.
Кстати... Не кажется ли вам, что писать «Диск с первого стержня перекладываем на второй...» – как то длинновато?
Открою секрет: все на свете математики – жуткие лодыри и лентяи! И ненавидят много и длинно писать! Давайте вместо «решение задачи для одного диска, двух дисков, трёх дисков и так далее» писать коротко (как настоящие математики!)
Р[1], Р[2], Р[3], …
Вместо «первый стержень», «второй стержень» и «третий стержень» будем писать Н («начальный»), П («промежуточный») и К («конечный»).
И тогда в итоге «с начального стержня перекладываем на промежуточный», «с начального стержня перекладываем на конечный» или «с промежуточного перекладываем на конечный» будем лениво писать
(Н → П), (Н → К) и (П → К)
Согласитесь, так быстрее! Тогда мы сможем решение для двух дисков записать кратко:
Р[2] = (Н → П) + (Н → К) + (П → К)
И времени меньше уходит, и бумага экономится, не так ли? А теперь – внимание! – а как решать задачу для трёх дисков? Каким будет Р[3]?
Внимательно подумав, вы скажете: «Аааа, так вот в чём дело! Нам надо перенести третий диск – нижний, самый большой! – с первого стержня на третий. Но для этого сперва надо перенести два верхних диска на второй, то есть промежуточный, стержень... А такую задачку мы решать уже научились!».
Именно! Просто, не правда ли? То есть решение задачи Р[3] будет состоять из трёх частей («шагов»):
1) Переносим 2 диска на промежуточный стержень (то есть решаем задачу Р[2])
2) Переносим 1 самый нижний диск на конечный стержень (это вообще задача Р[1])
3) Наконец, переносим 2 диска с промежуточного на конечный стержень (это снова задача Р[2])
Надеюсь, теперь вы уже поняли, как решается задача о Ханойских башнях для любого количества дисков? Обозначим неизвестное количество дисков традиционным «иксом», то есть буквой «X». Тогда общее решение P[X] выглядит так:
1) Переносим Х-1 дисков на промежуточный стержень (задача P[X-1])
2) Переносим 1 самый нижний диск на конечный стержень (задача P[1])
3) Переносим X-1 дисков на конечный стержень (задача P[X-1])
Итак, что мы сделали для решения задачи? Мы максимально упростили условие и убедились, что в этом случае задача решается. А затем как бы «расширили» условие, и показали, что если задачу можно решить для какого-то «Х», то её можно решить и для следующего «Х+1».
Скажем, как доказать, что Лучик может подняться по лестнице на 9 этаж? Убедимся, что он может подняться на одну ступеньку. Потом понимаем, что если он сможет одолеть 50 ступенек, то ещё на одну сил вполне хватит, то есть он сможет одолеть и 51 ступеньку тоже! В математике этот метод называется «математической индукцией», или просто индукцией, то есть в переводе с латинского «наведением» (на что-то), «подведением» (к чему-то).
Продолжим. Снова берём наши Ханойские башни. Видите – диски у нас раскрашены в два цвета, красный и синий?
Теперь внимание, задача: Доказать, что при игре в ханойские башни два диска одного цвета никогда не будут лежать друг на друге. То есть никогда не ляжет ни красный диск на красный, ни синий на синий. Сможете? Только не забывайте, что у нас есть волшебная индукция! Смотрите, снова начинаем «с простейшего случая»:
Решим задачку для 1 диска. Диск у нас только один, так что на диск того же цвета его положить не выйдет, так? Так.
Теперь для двух дисков. Дисков у нас только два, они разного цвета, так что опять «красный на красный» и «синий на синий» не выйдет, ведь так? Так.
Берём три диска. Скажем, красный сверху, синий посредине и красный снизу. Решаем: переносим 2 диска на промежуточный стержень (задача Р[2]), тогда на промежуточном стержне внизу какой диск будет? Верно, синий! Теперь переносим нижний диск на конечный стержень, ничего не меняется. Наконец, переносим 2 диска с промежуточного стержня на конечный – и снова у нас синий диск ляжет на красный!
А теперь делаем обобщение, то есть «индукционный переход». Пусть для неизвестного количества (то есть Х) дисков у нас задача решена, и положить «красный на красный» или «синий на синий» не получится. Тогда что будет, если мы возьмём X+1 дисков? При переносе Х дисков на промежуточный стержень цвета не совпадут. При переносе оставшегося «нижнего» диска на конечный стержень – ничего не поменяется. А при переносе Х дисков с промежуточного на конечный у нас опять же на «на красный диск ляжет синий» (ну, или синий на красный), потому что нижний диск на промежуточном стержне будет обязательно другого цвета. Всё, задача решена!
Индукция позволяет решать задачи, которые, казалось бы, и не совсем математические, и решить их ну просто никак невозможно. Оказывается, возможно, да ещё как!
Вот вам новая игра для двух игроков: есть две шкатулки, в каждой из которых лежат мраморные шарики. Причём в первой шкатулке шариков обязательно больше, чем во второй. Правила игры: игроки по очереди забирают себе любое количество шариков (хоть один, хоть все!), но только из одной шкатулки. Победит тот, кто заберёт последние шарики. Ну что, сыграем? Кто победит?
Раскрою секрет: это одна из игр, в которых всегда побеждает тот игрок, который делает первый ход. Правда, конечно, если он во время игры придерживается правильной стратегии. Какой именно? Отыщем ответ с помощью математической индукции! Снова начинаем с самого простого варианта:
1) Пусть во второй шкатулке 0 шариков. Тогда побеждает игрок, который ходит первым: он просто забирает все шарики из первой шкатулки и выигрывает.
2) Пусть во второй шкатулке 1 шарик. Игрок, который ходит первым, забирает из первой шкатулки все шарики, кроме одного. Остаётся по одному шарику – и там, и тут. Второй игрок может забрать шарик из левой шкатулки или из правой – без разницы, всё равно один шарик останется, тут-то первый игрок его и заберёт! Снова «кто ходит первым, тот победил».
Делаем индукционное обобщение:
3) Пусть во второй шкатулке лежит Х шариков. Тогда игрок, который ходит первым, забирает из первой шкатулки столько шариков, чтобы в ней осталось ровно Х шариков, как и во второй. И каждый раз в ответ на любой ход соперника снова забирает столько шариков, чтобы в шкатулках их стало ровно поровну. И всё – победа гарантирована!
Давайте, что называется, «закрепим тему». Как вы знаете, у нас в России нет монет достоинством 4 рубля. Но представьте, что такие монеты есть.
А теперь внимание – задача! Докажите, что из монет достоинством 4 рубля и 5 рублей можно собрать абсолютно любую сумму от 12 рублей и больше. Само собой, вы уже догадываетесь, что такая задача решается «по индукции». Справитесь сами или подсказать, с чего начинать?
«Ну, в индукции начинать надо с самого простого случая, – скажете вы (совершенно справедливо!). – А самый простой случай в этой задаче – 12 рублей. 12 рублей – это 3 монеты по 4 рубля, ёжику понятно. Так что базовый шаг сделан, здесь условие задачи выполняется. Теперь делаем индукционное обобщение: пусть любая сумма Х рублей может быть собрана из монет достоинством 4 и 5 рублей. Что мы можем сказать о сумме Х+1 рублей, то есть на 1 рубль больше? Тогда мы просто в сумме на Х рублей заменяем любую четырёхрублёвую монетку на «пятачок», и получаем нужную сумму Х+1. А если у нас нет ни одной монетки в 4 рубля, тогда любые 3 пятачка (15 рублей) мы поменяем на 4 монеты по 4 рубля (16 рублей, то есть 15+1) и снова получаем нужную сумму Х+1. Всё, задача решена!».
Напоследок, для окончательного закрепления: докажите, что из монет достоинством 5 рублей и 2 рубля можно набрать любую сумму денег, начиная от 4 рублей и выше.
Однако вернёмся к нашим ханойским башням. Если бы легенда о храме в горах была правдой, сколько времени пришлось бы ждать того самого конца света? Когда монахи закончили бы свой труд? Снова вспоминаем метод математической индукции:
Для решения задачи Р[1] нам был нужен 1 ход
Для решения задачи Р[2] нам было нужно 1 + 1 + 1 = 3 хода
Для решения задачи Р[3] нам требовалось 3 + 1 + 3 = 7 ходов
…
то есть (обобщаем!) для решения задачи Р[X+1] нам будет нужно P[X] + 1 + P[X] ходов
Тогда количество ходов для P[64] = 2 в степени 64 минус 1 = 18 446 744 073 709 551 615
Прописью: 18 квинтиллионов 446 квадриллионов 744 триллиона 73 миллиарда 709 миллионов 551 тысяча 615 ходов. Кхм. Даже если бы монахи двигались невероятно ловко и грациозно (что с золотыми дисками затруднительно – скажем, самый нижний, 64-й по счёту диск, если бы был толщиной в 1 сантиметр и диаметром в 64 сантиметра, весил бы свыше 60 килограммов!) и могли перекладывать со стержня на стержень по одному диску каждую секунду, у них ушло бы на это... 584 542 046 090 лет. Почти 585 миллиардов лет (!!) – это при том, что абсолютно все современные физики и астрономы убеждены, что наша Вселенная существует чуть больше 13 миллиардов лет. В общем, даже если легенда о «башнях Брахмы» не врёт, близкого конца света можете не бояться.
А вообще, метод индукции – штука хорошая, правильная. И в математике, и в жизни. Потому что учит нас: если ты смог сегодня отжаться от пола или подтянуться на турнике семь раз – то завтра сможешь восемь. Если смог решить одну задачку или прочитать одну книжку из заданных на лето – значит, сможешь решить или прочитать все. Если смог навести порядок у себя на столе – значит, и в комнате прибраться тоже сумеешь без проблем. Главное – начать с простого, убедиться, что у тебя всё получается, а затем двигаться всё дальше и дальше. Удалось справиться с «иксом»? Значит, уверенно бери курс на «икс плюс один»! И всё получится!
Читайте также:
Почему нельзя делить на ноль?
Выписать журнал "Лучик" можно на сайте Почты России. Предварительно полистать журнал можно здесь.