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

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

Оценка 4.6
doc
19.12.2023
Один из методов решения олимпиадных задач по математике 7-8 класс
Применение Метода математической индукции Сухановой О.В..doc

 

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

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

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

некоторое утверждение справедливо для всякого натурального 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; аналогично определим цвет, уникальный для строки. Пусть существует столбец, для которого есть не более одного уникального цвета. Тогда выбросим его; в оставшемся прямоугольнике будет встречаться не менее k1 > m+n1 цветов, значит, по предположению индукции в нём найдётся нужная четвёрка клеток.

Итак, осталось разобрать случай, когда в каждом столбце (и, аналогично, в каждой строке) хотя бы по два уникальных цвета. Рассмотрим любой столбец ; пусть в нём два уникальных цвета 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

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

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

Задача 2 Дано n произвольных квадратов

Задача 2 Дано n произвольных квадратов

Полученная фигура тоже будет квадратом, т

Полученная фигура тоже будет квадратом, т

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

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

Эту пирамидку нужно переместить на один из дру­ гих стержней, перенося каждый раз только одно коль­ цо и не помещая большее кольцо на меньшее

Эту пирамидку нужно переместить на один из дру­ гих стержней, перенося каждый раз только одно коль­ цо и не помещая большее кольцо на меньшее

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

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

Литература 1. https://clck

Литература 1. https://clck
Материалы на данной страницы взяты из открытых истончиков либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.
19.12.2023