Знакомство с методом математической индукции: различия между версиями

Содержимое удалено Содержимое добавлено
мНет описания правки
Строка 49:
* Пирамидку, в которой только одно кольцо <math>n=1\,\!</math> переместить можно (очевидно).
* Предположим, что мы умеем перемещать пирамидки с числом колец <math>n\le K\,\!</math>.
* Попробуем научиться перемещать пирамидку с <math>n=K+1\,\!</math> . Пирамидку из <math>K\,\!</math> колец, лежащих на самом большом <math>K+1\,\!</math>-м кольце, мы можем согласно предположению переместить на любой стержень. Сделаем это, переместим её на третий стержень. Неподвижное <math>K+1\,\!</math>-е кольцо не будет нам мешать провести алгоритм перемещения, так как оно самое большое. После перемещения <math>K\,\!</math> колец переместим оставшимсяоставшееся <math>K+1\,\!</math>-е кольцо на второй стержень. Мы можем это сделать, так как второй стержень пустой. Теперь обратим внимание, тот факт, что второй стержень не пустой, не мешает нам класть на него ''любые'' кольца, так как имеющееся на нём кольцо самое большое (любое кольцо можно положить на большее, а значит и самое большое по условию задачи). И затем опять применим известный нам по предположению алгоритм перемещения <math>K\,\!</math> колец и переместим их на второй стержень, стержень с лежащим внизу <math>K+1\,\!</math>-м кольцом. Таким образом, если мы умеем перемещать пирамидки с <math>K\,\!</math> кольцами, то умеем перемещать пирамидки и с <math>K+1\,\!</math> кольцом.
* Следовательно утверждение верно для всех случаев, то есть для всех <math>n\,\!</math>.