Решение задачи 282

Условие:

Есть три стержня и n колец разного размера (изначально все кольца на одном стержне). Класть можно только кольцо меньшего размера на кольцо большего размера. Докажите, что для любого n можно всю башню переложить с одного стержня на другой.

Решение:

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

Осталось показать, что верна база индукции, то есть что утверждение верно в самом просто случае, при n=1. Действительно, переложить одно кольцо не составляет никакого труда.

Таким образом, мы показали верность базы индукции и шага индукции, следовательно, утверждение верно для любого n.