Применение метода математической индукции при решении олимпиадных задач
В основе метода математической индукции лежит принцип, который
заключается в следующем:
некоторое утверждение справедливо для всякого натурального n, если:
1) оно справедливо для n = 1;
2) из справедливости утверждения для какого-либо произвольного натурального n = k следует его справедливость для n = k+1.
То есть, доказательство по методу математической индукции проводится в три этапа:
1) во-первых, проверятся справедливость утверждения для любого натурального числа n (обычно проверку делают для n = 1);
2) во-вторых, предполагается справедливость утверждения при любом натуральном n=k;
3) в-третьих, доказывается справедливость утверждения для числа n=k+1, отталкиваясь от предположения второго пункта.
Действительно, допустим, мы проверили так называемую базу индукции и получили, сто утверждение верно при n=1. Потом предположили, что утверждение верно при n=k и доказали, что в этом случае утверждение верно и при n=k+1. Тогда примем, что k=1. В таком случае мы можем сказать, что утверждение верно при n=k+1=2. Приняв k=2, мы докажем, что утверждение верно уже при n=3 и т.д. Таким образом мы докажем истинность утверждения для всех натуральных n.
ММИ позволяет довольно просто решать многие задачи, и особенно задачи математических олимпиад.
Задача 1. Доказать, что 20212022 >20222021
Задача 2 Дано n произвольных квадратов. Доказать, что их можно разрезать на части так, что из полученных частей можно сложить новый квадрат.
Решение. При n=1 утверждение не требует доказательства. Докажем, что при n=2 оно также справедливо. Обозначим стороны заданных квадратов и соответственно через x и y; пусть выполняется неравенство . На сторонах квадрата со стороной x отложим отрезки AM=BN=CP=DQ= и разрежем этот квадрат по прямым MP и NQ, которые, как легко видеть, пересекаются в центре O .
квадрата и образуют между собой прямой угол, разбивая квадрат на 4 равные части.
Эти куски приложим ко второму квадрату:
Полученная фигура тоже будет квадратом, т.к. углы , , , – прямые и .
Предположим теперь, что утверждение верно при n=k и докажем, что оно верно и при n=k+1 квадратов.
Выберем любые два из этих квадратов. Как было показано ранее, разрезая один из этих квадратов и прикладывая полученные куски ко второму, можно получить новый квадрат. Далее можно взять этот получившийся квадрат и любой другой из оставшихся и получить из двух квадратов один, и т.д. В конце концов у нас останется 2 квадрата, из которых мы сможет сделать один квадрат. Это и требовалось.
Задача 3. Дано натуральное число n > 2. Рассмотрим все покраски клеток доски n×n в k цветов такие, что каждая клетка покрашена ровно в один цвет, и все k цветов встречаются. При каком наименьшем k в любой такой покраске найдутся четыре окрашенных в четыре разных цвета клетки, расположенные в пересечении двух строк и двух столбцов?
Решение. Сначала мы предъявим пример покраски клеток в 2n − 1 цветов так, чтобы не было ни одной требуемой разноцветной четверки клеток. Покрасим все клетки первой горизонтали H и первой вертикали V в 2n − 1 различный цвет, причём клетку на их пересечении покрасим в цвет c; затем покрасим все оставшиеся клетки также в цвет c. Тогда нетрудно понять, что из четырёх клеток на пересечении любых двух столбцов и двух строк максимум две будут иметь цвет, отличный от c. Значит, требуемой четвёрки клеток не найдётся.
Осталось доказать, что при k>2n требуемые четыре клетки всегда найдутся. Мы докажем более общее утверждение: если клетки прямоугольника m × n окрашены в k>m+n цветов, причём все цвета присутствуют, то найдутся 4 разноцветных клетки на пересечении двух строк и двух столбцов.
Индукция по m+n. Заметим сразу, что при m = 1 утверждение верно, ибо раскрасок n клеток в n+1 цвет не существует; в частности, это доказывает базу индукции при m+n=2. Предположим теперь, что m, n > 1, и совершим переход индукции.
Рассмотрим произвольную раскраску клеток прямоугольника m×n в k цветов. Назовём цвет c уникальным для столбца V , если цвет c встречается только в столбце V; аналогично определим цвет, уникальный для строки. Пусть существует столбец, для которого есть не более одного уникального цвета. Тогда выбросим его; в оставшемся прямоугольнике будет встречаться не менее k−1 > m+n−1 цветов, значит, по предположению индукции в нём найдётся нужная четвёрка клеток.
Итак, осталось разобрать случай, когда в каждом столбце (и, аналогично, в каждой строке) хотя бы по два уникальных цвета. Рассмотрим любой столбец ; пусть в нём два уникальных цвета p и q, и какие-то клетки этих цветов стоят в строках и соответственно. В есть два уникальных цвета; один из них отличен от p. Пусть этот цвет – r, и в клетка этого цвета стоит в столбце . Тогда построенные два столбца и две строки – требуемые. Действительно, на их пересечении в стоят два разных цвета, уникальных для ; значит, они не встречаются в . Цвет r p уникален для , значит, он не встречается в . Итого, в нашем пересечении есть различные цвета p, q, r, а также клетка цвета, отличного от них. Это и требовалось.
|
Задача 4. Головоломка «Ханойские башни» состоит из трех стержней. На одном из стержней находится пирамидка, состоящая из нескольких колец разного диаметра, уменьшающихся снизу вверх.
Эту пирамидку нужно переместить на один из других стержней, перенося каждый раз только одно кольцо и не помещая большее кольцо на меньшее. Можно ли это сделать?
Решение. Итак, нам необходимо ответить на вопрос: можно ли переместить пирамидку, состоящую из n колец разного диаметра, с одного стержня на другой, соблюдая правила игры.
База индукции. При n=1 требуемое возможно, так как пирамидку из одного кольца, очевидно, можно переместить на любой стержень.
Шаг индукции. Предположим, что мы умеем перемещать любые пирамидки с числом колец n=k. Докажем, что тогда мы сможем переместить и пирамидку с числом колец n=k+1.
Пирамидку из k колец, лежащих на самом большом (k+1)-м кольце, мы можем, согласно предположению, переместить на любой другой стержень. Сделаем это. Неподвижное (k+1)-е кольцо не будет нам мешать провести алгоритм перемещения, так как оно самое большое, и, если понадобится в процессе перемещения пирамидки из n колец, мы можем переместить на него любое другое кольцо. После перемещения k колец, переместим это самое большое (k+1)-е кольцо на оставшийся стержень. Затем опять применим известный нам по индуктивному предположению алгоритм перемещения к колец, и переместим их на стержень с лежащим внизу (k+1)-м кольцом. Таким образом, если мы умеем перемещать пирамидки с k кольцами, то умеем перемещать пирамидки и с k+1 кольцами. Следовательно, согласно принципу математической индукции, всегда можно переместить нужным образом пирамидку, состоящую из n колец, где n>1.
1. Доказать , что при любом натуральном n число 32n+1+2n+2 делится на 7.
Решение
Проведём доказательство методом математической индукции.
Обозначим А(n)=32n+1+2n+2.
База индукции. Если n=1, то А(1)=33+23=35 и, очевидно, делится на 7.
Предположение индукции. Пусть А(k) делится на 7.
Индукционный переход. Докажем, что А(k+1) делится на 7, то есть справедливость утверждения задачи при n=k.
А(k+1)=32(k+1)+1+2(k+1)+2=32k+1·32+2k+2·21=32k+1·9+2k+2·2=
=32k+1·9+2k+2·(9–7)=(32k+1+2k+2)·9–7·2k+2=9·А(k)–7·2k+2.
Последнее число делится на 7, так как представляет собой разность двух целых чисел, делящихся на 7. Следовательно, 32n+1+2n+2 делится на 7 при любом натуральном n.
Литература
1. https://clck.ru/Ycx8A
2. http://math4school.ru/metod_matematicheskoj_indukcii.html
3. http://www.unn.ru/books/met_files/mmi.pdf
4. Мадера А.Г., Математические софизмы: Правдоподобные рассуждения, приводящие к ошибочным утверждениям: Кн. Для учащихся 7–11 кл. / А.Г. Мадера, Д.А. Мадера. – М.: Просвещение, 2003.
5. Горячев Д., Задачи, вопросы и софизмы для любителей математики / Д. Горячев, А. Воронец. – Ижевск: РХД, 2000.
6. Шень А. Математическая индукция. — М.: МЦНМО,2007.
7. Лямин А.А. Математические парадоксы и интересные задачи для любителей математики. – М., 1903.
8. Литцман В., Трир Ф. Где ошибка? – СПб., 1919.
Скачано с www.znanio.ru
© ООО «Знанио»
С вами с 2009 года.