ПОДГОТОВКА К

ОЛИМПИАДАМ ПО МАТЕМАТИКЕ

Математическая индукция "для продвинутых"

 

22.08.2017

Математическая индукция - рассуждение, в котором мы делаем общий вывод на основе частных суждений.

 

Тем, кто еще не сталкивался с мат индукцией в решении олимпиадных заданий по математике я настоятельно рекомендую ознакомится с предыдущей статьей по этой теме

 

А для тех, кто уже владеет этим методом, здесь я привожу разбор более сложной задачи на индукцию - задача №5 для 11 класса с олимпиады Высшая Проба 2017:

 

Числа P1, . . . , Pn являются перестановкой набора чисел {1, . . . , n} (то есть каждое Pi равно одному из 1, . . . , n, и все Pi различны). Докажите неравенство

 

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

 

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

1) База индукции. Сумма подразумевает, что слагаемых будет хотя бы 2, то есть минимальное n, для которого данное выражение будет иметь смысл - n = 3. Действительно, неравество верно при n = 3:

 

2) Индуктивный переход.

Пусть неравенство выполняется для некого n = k:

Нужно доказатать, что тогда неравенство будет выполняться и для n = k + 1, то есть:

 

При n = k: P1, . . . , Pk - перестановка набора чисел {1, . . . , k}, при n = k + 1: P1, . . . , Pk+1 - перестановка чисел {1, . . . , k+1}.

Без ограничения общности, пусть число k+1 в этой перестановке стоит между числами Pj и Pj+2 (то есть занимает место j+1; j - любое).

При этом, если мы уберем число Pj+1 = k + 1, то числа Pj и Pj+2 станут соседними, и вместо суммы дробей будет дробь

 

По предположению индукции, в этом случае неравенство будет выполняться (по предположению индукции неравенство доказано для k чисел).

 

Теперь воспользуемся тем же приемом, что и впервой статье при доказательстве неравенства для натурального n - для доказательства индукционного перехода нам достаточно показать, что при переходе от n=k к n=k+1 левая часть увеличивается больше чем правая.

Посмотрим, насколько увеличивается правая часть:

 

 

Теперь оценим (снизу), насколько увеличивается левая часть и покажем, что прирост левой больше прироста правой:

 

Поскольку даже больший корень этого трёхчлена меньше 3, то при всех n ≥ 3 прирост левой часть будет больше прироста правой, что нам и нужно было доказать.

 

3) Вывод. Неравенство доказано.

 

 

 Другие полезные олимпиадные задачи 8-11 класс>>

 

Записаться на бесплатное пробное занятие >>

 

 

 

 

 

 

Тел.: +7 (967) 104 01 76 | foggyjandjane@gmail.com

WhatsApp, Telegram

Skype: JandJaneHeh