Математическая индукция

Размещено на http://www.allbest.ru/

Математическая индукция -- один из методов доказательства. Используется, чтобы доказать истинность некоего утверждения для всех натуральных чисел.

Вообразим очередь, где первой стоит женщина, за ней снова женщина, а за ней снова женщина. Верно ли, что все стоящие в очереди -- женщины?

Конечно, верно! Раз первые три человека в очереди -- женщины, то, скорее всего, это очередь за косметикой, или за чем-нибудь таким, в чём нуждаются и разбираются исключительно женщины, и мужчин в этой очереди нет.

Пусть подобные рассуждения иногда оправдывают себя на практике, они не являются математически строгими и никак не связаны с методом математической индукции, о котором мы сегодня хотим поговорить.

Рассмотрим два утверждения:

1. Первый человек в очереди есть женщина.

2. За женщиной в очереди может стоять только женщина.

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

Вот строгая формулировка принципа математической индукции:

Пусть имеется последовательность утверждений  И пусть первое утверждение Y₁ верно и мы умеем доказать, что из верности утверждения Y_k следует верность Y_{k + 1}. Тогда все утверждения в этой последовательности верны.

Верность этого метода доказательства вытекает из так называемой аксиомы индукции, пятой из аксиом Пеано, которые определяют натуральные числа. Рассмотрение аксиом Пеано выходит за рамки этой статьи.

Заметим, что аксиому индукции можно заменить на аксиому существования минимума, и доказать аксиому индукции как теорему.

Ханойские башни

математический индукция аксиома истинность

Есть три стержня и n колец разного размера. Класть можно только кольцо меньшего размера на кольцо большего размера. Можно ли переместить пирамидку с одного стержня на другой? Можно или нельзя?

§ Пирамидку, в которой только одно кольцо n = 1, переместить можно (очевидно).

§ Предположим, что мы умеем перемещать пирамидки с числом колец .

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

§ Следовательно утверждение верно для всех случаев, то есть для всех n.

Заметим, что всё решение было разбито на четыре этапа:

1. [БАЗА] Показываем, что доказываемое утверждение верно для некоторых простейших частных случаев (в нашей задачке это был случай n = 1)

2. [ПРЕДПОЛОЖЕНИЕ] Предполагаем, что утверждение доказано для первых K случаев.

3. [ШАГ] В этом предположении доказываем утверждение для случая n = K + 1.

4. [ВЫВОД] Утверждение верно для всех случаев, то есть для всех n.

В задаче «Ханойские башни» роль переменной индукции играло количество колец в пирамидке.

Пересечение прямых

Докажите, что любые n прямых, расположенных на одной плоскости, никакие две из которых не параллельны, и никакие три не пересекаются в одной точке, пересекаются ровно в  точках.

Решение:

[БАЗА] В простейшем случае, когда прямых две, известно, что они непаралельны, а значит пересекаются как минимум в одной точке. Они не могут пересекаться в более чем одной точке, так как согласно аксиомам Евклидовой геометрии (а именно, следствие из аксиомы «через две точки можно провести прямую и только одну»), если бы были хотя бы две точки пересечения у двух прямых, то эти прямые совпадали бы, то есть мы бы имели одну прямую, а не две. Имеем, что должно быть не менее одной (включительно) и не более одной (включительно) точек пересечения, а значит точка пересечения одна и утверждение верно.

[ПРЕДПОЛОЖЕНИЕ] Предположим, что оно верно для k прямых, то есть что любых k прямых, никакие две из которых не параллельны, и никакие три не пересекаются в одной точке, пересекаются ровно в  точках.

[ШАГ] Попробуем доказать его для k + 1 прямых. По предположению, 1-я, 2-я, …, k-я прямая пересекаются в  точках. Рассмотрим k + 1-ю прямую и одну из прямых, обозначем её i из списка 1-я, 2-я, …, k-я прямая. Как мы уже доказали в [БАЗЕ] любые две прямые, удовлетворящие условиям задачи, пресекаются ровно в одной точке, а значит и прямые k + 1 и i пересекаются в одной точке. Вспомним, что i обозначает любую прямую из списка 1-я, 2-я, …, k. Отсюда k + 1-я прямая пересекается с каждой из этих k прямых ровно в одной точке.

Рассмотрим список из k + 1 прямых и их точек пересечения. Уберём прямую k + 1 вместе с её точками пересечения. Останется kпрямых удовлетворяющих [ШАГУ]. Значит количество точек пересечения у этих k прямых равняется . Как было показано выше, количество точек пересечения, которое мы убрали вместе с прямой k + 1, равняется k.

Следовательно, количество точек пересечения всех k + 1 прямых есть 

.

То есть для k + 1 прямых утверждение доказано.

[ВЫВОД] Утверждение верно для любого количества прямых.

Разрезание квадрата

Из квадрата клетчатой бумаги размером  вырезали одну клетку. Докажите, что полученную фигуру можно разрезать на «уголки» из трёх клеток.

Решение:

[БАЗА] Для n = 1 получим квадрат размером . Вырежем, скажем, правый верхний квадрат. Останется три квадрата, представляющие из себя «уголки». Утверждение верно.

[ПРЕДПОЛОЖЕНИЕ] Пусть это уже доказано для квадратов со стороной 2^k с вырезанной одной клеткой. Докажем для квадратов .

[ШАГ] Разбиваем квадрат  на четыре квадрата  и вырезаем из каждой недырявой части угловую клетку так, чтобы вырезанные клетки образовали уголок:

[ВЫВОД] Таким образом, получаем четыре квадрата, в каждом из которых вырезано по одной клетке, и по предположению индукции их мы можем замостить уголками. Замощение квадрата  будет состоят из замощения четырёх квадратов  c вырезанной одной клеткой по середине. Что и требовалось доказать.

Размещено на Allbest.ru