Один из методов решения олимпиадных задач по математике 7-8 класс

Применение метода математической индукции при решении олимпиадных задач

В основе метода математической индукции лежит принцип, который

заключается в следующем:

некоторое утверждение справедливо для всякого натурального 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. Доказать, что 2021²⁰²² >2022²⁰²¹

Задача 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 число 3²ⁿ⁺¹+2ⁿ⁺² делится на 7.

Решение

Проведём доказательство методом математической индукции.

Обозначим А(n)=3²ⁿ⁺¹+2ⁿ⁺².

База индукции. Если n=1, то А(1)=3³+2³=35 и, очевидно, делится на 7.

Предположение индукции. Пусть А(k) делится на 7.

Индукционный переход. Докажем, что А(k+1) делится на 7, то есть справедливость утверждения задачи при n=k.

А(k+1)=3^2(k+1)+1+2^(k+1)+2=3^2k+1·3²+2^k+2·2¹=3^2k+1·9+2^k+2·2=

         =3^2k+1·9+2^k+2·(9–7)=(3^2k+1+2^k+2)·9–7·2^k+2=9·А(k)–7·2^k+2.

Последнее число делится на 7, так как представляет собой разность двух целых чисел, делящихся на 7. Следовательно, 3²ⁿ⁺¹+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