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

м
Откат правок 2.93.174.246 (обс.) к версии AVUmnov
(→‎Ханойские башни: интервики, пунктуация, орфограф)
м (Откат правок 2.93.174.246 (обс.) к версии AVUmnov)
* Пирамидку, в которой только одно кольцо <math>n = 1</math>, переместить можно (очевидно).
* Предположим, что мы умеем перемещать пирамидки с числом колец <math>n \leqslant K</math>.
* Попробуем научиться перемещать пирамидку с <math>n = K + 1</math> . Пира__FORCETOC__мидкуПирамидку из <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>.
 
7076

правок