Решение олимпиадных математических задач

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

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

Олимпиадные задачи получили своё название от популярных соревнований школьников и студентов, так называемых Математических олимпиад. Цель создания задач этой категории — воспитание в будущих математиках таких качеств как творческий подход, нетривиальное мышление и умение изучить проблему с разных сторон. Не случайно академик А. Н. Колмогоров в своей речи на открытии сравнил работу математика с «чередой решения (порою больших и трудных) олимпиадных задач».

Внешняя простота олимпиадных задач — их условия и решения должны быть понятны любому школьнику — обманчива. Лучшие олимпиадные задачи затрагивают глубокие проблемы из самых разных областей математики. К сожалению, этой кажущейся простотой иногда пользовались не по назначению: на приёмных экзаменах с помощью таких задач отсеивали абитуриентов нежелательных национальностей. Неудивительно, что олимпиадные задачи из арсенала таких приёмных комиссий стали называть «гробами».

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

Большой вклад в популяризацию методов решения олимпиадных задач внесли публикации журнала «Квант», книги серий «Популярные лекции по математике», «Библиотека математического кружка» и другие книги, а также многочисленные веб-сайты, посвящённые олимпиадным задачам.

Типы задач

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

• Задачи на инвариант

Методы решения

Не существует единого метода решения олимпиадных задач. Напротив, количество методов постоянно пополняется. Некоторые задачи можно решить несколькими разными методами или комбинацией методов. Характерная особенность олимпиадных задач в том, что решение с виду несложной проблемы может потребовать применения методов, использующихся в серьёзных математических исследованиях. Ниже приводится (по определению) неполный список методов решения олимпиадных задач:

• Доказательство от противного.

• Принцип Дирихле

• Решение методами другой науки (замена алгебраической задачи геометрической или физической и наоборот)

• Правило крайнего

• Решение с конца

• Поиск инварианта

• Построение контрпримера

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

• Рекурсия

• Метод итераций

• Подсчёт двумя способами

• Метод аналогий

• Провокационный метод

• Вспомогательное построение

• Переход в пространство большего числа измерений

• Вспомогательная раскраска

Цель работы: Научиться решать олимпиадные математические задачи разного типа и изучить методы их решения.

Рассмотрим каждый метод решения олимпиадных задач подробнее.

Принцип Дирихле

При решении многих задач используется логический метод рассуждения — "от противного". В данной брошюре рассмотрена одна из его форм — принцип Дирихле. Этот принцип утверждает, что если множество из N элементов разбито на n непересекающихся частей, не имеющих общих элементов, где N>n то, по крайней мере, в одной части будет более одного элемента. Принцип назван в честь немецкого математика Дирихле (1805-1859), который успешно применял его к доказательству арифметических утверждений.

По традиции принцип Дирихле объясняют на примере "зайцев и клеток". Если мы хотим применить принцип Дирихле при решении конкретной задачи, то нам предстоит разобраться, что в ней — "клетки", а что — "зайцы". Это обычно является самым трудным этапом в доказательстве.

Формулировка принципа Дирихле

Самая популярная формулировка принципа Дирихле звучит так:

ФОРМУЛИРОВКА 1. "Если в n клетках сидит n+1 или больше зайцев, то найдётся клетка, в которой сидят по крайней мере два зайца".

Заметим, что в роли зайцев могут выступать различные предметы и математические объекты - числа, отрезки, места в таблице и т. д.

Принцип Дирихле можно сформулировать на языке множеств и отображений.

ФОРМУЛИРОВКА 2. "При любом отображении множества P, содержащего n+1 элементов, в множество Q, содержащее n элементов, найдутся два элемента множества P, имеющие один и тот же образ".

Несмотря на совершенную очевидность этого принципа, его применение является весьма эффективным методом решения задач, дающим во многих случаях наиболее простое и изящное решение. Однако во всех этих задачах часто нелегко догадаться, что считать "зайцем", что - "клеткой", и как использовать наличие двух "зайцев", попавших в одну "клетку". С помощью принципа Дирихле обычно доказывается существование некоторого объекта, не указывая, вообще говоря, алгоритм его нахождения или построения. Это даёт так называемое неконструктивное доказательство - мы не можем сказать, в какой именно клетке сидят два зайца, а знаем только, что такая клетка есть.

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

Доказательство по индукции наглядно может быть представлено в виде так называемого принципа домино:

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

Доказательство «от противного» в математике — один из самых часто используемых методов доказательства утверждений. Этот способ доказательства основывается на истинности формулы в классической логике и законе двойного отрицания.

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

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

Доказательство иррациональности числа.

Допустим противное: рационален, то есть представляется в виде несократимой дроби , где m и n — целые числа. Возведём предполагаемое равенство в квадрат:

Отсюда следует, что m2 чётно, значит, чётно и m; следовательно, m2 делится на 4, а значит, n2 и n тоже чётны. Полученное утверждение противоречит несократимости дроби. Значит, исходное предположение было неверным, и  — иррациональное число.

Метод раскраски.

Суть данного метода состоит в следующем. Раскрасив некоторые ключевые элементы, которые фигурируют в задаче в несколько цветов, исследовать, что будет происходить, если выполнять условия задачи. Цвет позволяет значительно упростить понимание процесса, фигурируемого в условии, и зачастую приводит к решению. Этот метод позволяет эффективно решать ряд задач, в частности, игровые и шахматные задачи.

Пример:

Дан квадрат клетчатой бумаги размером 8 x 8, из которого вырезаны две крайние диагональные клетки (верхняя-правая и нижняя-левая). Можно ли полученную фигуру покрыть прямоугольниками размером 1 x 2?

Решение: Раскрасим наш обрезанный квадрат с помощью двух цветов в шахматную расцветку. Заметим, что отрезанные диагональные клетки будут одного цвета. Отметим также, что в нашем раскрашенном квадрате любые соседние две клетки (имеющие общую сторону) будут разного цвета. Это значит, что любой прямоугольник размером 1 x 2, которым мы будем пытаться покрыть обрезанный квадрат будет покрывать клетки обоих цветов. И если мы сможем покрыть обрезанный квадрат прямоугольниками 1 x 2, то будет покрыто одинаковое количество клеток с разными цветами; то есть фигура должна содержать одинаковое количество клеток обоих цветов. Но так как мы отрезали диагональные клетки одного цвета, то их количество в обрезанном квадрате на две меньше. Это означает, что мы не сможем польностью покрыть указанный обрезанный квадрат прямоугольниками 1 x 2.

Контрпример — пример, опровергающий верность некоторого утверждения.

Построение контрпримера — обычный способ опровержения гипотез. Если имеется утверждение типа «Для любого X из множества M выполняется свойство A», то контрпримером для этого утверждения будет: «Существует объект X0 из множества M, для которого свойство A не выполняется».

Условие

В вершинах правильного девятиугольника расставляют числа 1, 2, 3, 4, 5, 6, 7, 8, 9, после чего на каждой диагонали пишут произведение чисел, стоящих на её концах. Можно ли так расставить числа в вершинах, чтобы все числа на диагоналях были разные?

Решение

Составим таблицу умножения для чисел от 1 до 9.

  1 2 3 4 5 6 7 8 9 1   2 3 4 5 6 7 8 9 2     6 8 10 12 14 16 18 3       12 15 18 21 24 27 4         20 24 28 32 36 5           30 35 40 45 6             42 48 54 7               56 63 8                 72 9                   Произведение для каждых двух сомножителей мы записали в таблицу только один раз. То есть, если, например, в клетку 4×7 мы поставили число 28, то клетку 7×4 оставили пустой. Мы также не заполнили клетки 1×1, 2×2, 3×3 и т.  д. , потому что такие произведения нам встретиться не могут (в условии каждое число дано только один раз).

Мы видим, что некоторые значения произведений встречаются по два раза (они выделены жирным шрифтом), а остальные - по одному разу.

Например,

1×6 = 2×3 = 6.

Чтобы число 6 не оказалось написанным на двух диагоналях, нужно поставить рядом (на концах одной их сторон 9-угольника; сторона диагональю не считается) или числа 1 и 6, или числа 2 и 3 (разумеется, можно разместить и 1 и 6 рядом друг с другом, и 2 и 3 рядом друг с другом - тогда число 6 не будет написано вообще ни на одной диагонали). Аналогично следует поступить и с другими такими сомножителями.

Составим полный список значений произведений, которые в таблице встречаются по два раза (и укажем, как именно эти значения получаются):

Нам достаточно расставить числа так, чтобы из каждой строчки сомножители хотя бы одного произведения стояли рядом (то есть на стороне 9-угольника, а не на диагонали). Например, это можно сделать так (мы поставили рядом сомножители первого произведения в каждой строчке):

-3-8-1-6-2-9-4-5-7-

Да, можно.

Реку́рсия — метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса или метода, ссылающегося прямо или косвенно на эти базовые случаи.

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

Задача «Ханойские башни». Её содержательная постановка такова:

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

Рекурсивный вариант решения задачи можно описать так:

Алгоритм по передвижению башни, алгоритм передвинет нужное количество дисков из пирамиды «источник» на пирамиду «задание» используя «запасную» пирамиду. Если число дисков равно одному, тогда:

• Передвиньте диск из источника в задание

В противном случае:

• Рекурсивно передвиньте все диски кроме одного из источника в запас, используя задание как запас

• Передвиньте оставшийся диск из источника в задание

• Передвиньте все диски из запаса в задание используя источник как запас

Правило «крайнего»

Если Вы хотите научиться решать задачи, Вам надо попытаться овладеть более или менее общими подходами, приемами и методами математических рассуждений. Рассмотрим один общий подход, который мы будем называть правилом «крайнего».

Правило «крайнего» может быть кратко выражено словами: «Рассмотрите крайнее!». Это правило есть попросту рекомендация рассмотреть объект, обладающий какими либо «крайними» или как говорят в математике, экстремальными свойствами. Если в задаче речь идет о множестве точек на прямой, то, по правилу «крайнего», необходимо рассмотреть самую крайнюю точку множества (самую левую или самую правую). Если в задаче фигурирует некоторый набор чисел, то правило «крайнего» рекомендует рассмотреть наибольшее или наименьшее из этих чисел. Рассмотрим применение этого подхода на некоторых примерах.

Задача 1. На полях бесконечной шахматной доски записаны натуральные числа так, что каждое число равно среднему арифметическому четырех соседних чисел – верхнего, нижнего, правого и левого. Докажите, что все эти числа равны между собой.

Решение. Решим эту задачу, используя правило «крайнего» в форме «рассмотрите наименьшее!».

1) Среди натуральных чисел записанных на доске обязательно существует наименьшее. Действительно, пусть К – одно из данных чисел. Если среди чисел записанных на доске есть единица, то она и является таким наименьшим числом. Если единицы на доске нет, посмотрим, нет ли там двойки. Если есть, то она и является наименьшим числом, если же нет, то поищем на доске тройку и т. д. Не более чем за К шагов мы отыщем таким образом наименьшее число.

2) Обозначим наименьшее из чисел, записанных на доске, буквой m. Рассмотрим поле Р , на котором записано это число. Обозначим числа записанные на соседних полях, буквами а, b, с, d. По условию. Отсюда.

3) В силу выбора числа m имеем:. Если бы хотя бы одно из этих неравенств было строгим, то имели бы :. Значит , т. е. соседние числа раны m. Отсюда следует, что на горизонтали, содержащей поле Р, записаны одни только числа m, а так как любая вертикаль пересекает эту горизонталь, то она содержит число m и, значит, все числа на ней равны m. Откуда имеем, что все числа равны m.

Метод итераций

Это способ численного решения математических задач. Его суть – нахождение алгоритма поиска по известному приближению (приближенному значению) искомой величины следующего, более точного приближения. Применяется в случае, когда последовательность приближений по указанному алгоритму сходится.

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

Подсчет 2 способами

Условие

В классе каждый мальчик дружит ровно с двумя девочками, а каждая девочка — ровно с тремя мальчиками. Еще известно, что в классе 31 пионер и 19 парт. Сколько человек в этом классе?

Показать решение

Решение

Обозначим количество мальчиков в классе через M, а девочек — через D. Из условий следует, что 31 ≤ D + M ≤ 38 и 3D = 2M. Последнее равенство показывает, что количество девочек четно, а количество мальчиков делится на 3. Более того, , откуда D + M = 5n. Существует единственное целое число, заключенное между 31 и 38, делящееся на 5. Поэтому можно утверждать, что в классе 35 учеников — 14 девочек и 21 мальчик.

Инвариа́нт в математике — это свойство некоторого класса (множества) математических объектов оставаться неизменными при преобразованиях определённого типа.

Задача: Ребёнок овладел всего лишь двумя звуками: "У" и "А", причем два слова в лексиконе этого ребёнка означают одно и то же, если одно получается из другого при помощи следующих преобразований: исключения идущих подряд звуков "УА" или "ААУУ" и добавления в любое место сочетания "АУУА". Докажите, что слова "ААУАААУУА" и "ААУУААА" означают одно и то же.

Решение: Нетрудно проверить, что второе слово получается из первого в результате последовательного применения трёх преобразований, указанных выше (назовём их смыслосохраняющими преобразованиями) — надо только найти эту цепочку смыслосохраняющих преобразований. Однако, на вопрос, означают ли слова "АУУ" и "УАА" одно и то же, ответить гораздо сложнее. Перебор последовательностей смыслосохраняющих преобразований не позволит получить второе слово из первого, так как данные слова имеют разный смысл. Для доказательства этого нужен принципиально другой подход, именуемый поиском инварианта.

Примеры задач

Задача 1:

В мешке лежат шарики двух разных цветов: черного и белого. Какое наименьшее число шариков нужно вынуть из мешка вслепую так, чтобы среди них заведомо оказались два шарика одного цвета?

Решение:

Обозначим первое из этих чисел через a. Получим

Задача 2:

В лесу растет миллион елок. Известно, что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым числом иголок.

Решение:

Перед нами миллион «кроликов»-елок и, увы, всего лишь 600001 клетка с номерами от 0 до 600000. Каждый «кролик»-елка сажается нами в клетку с номером, равным количеству иголок на этой елке. Так как «кроликов» гораздо больше, чем клеток, то в какой-то клетке сидит по крайней мере два «кролика» – если бы в каждой сидело не более одного, то всего «кроликов»-елок было бы не более 600001 штук. Но ведь, если два «кролика»-елки сидят в одной клетке, то количество иголок у них одинаково.

Задача 3:

Дано 12 целых чисел. Докажите, что из них можно выбрать два, разность которых делится на 11.

Решение:

Остатки по модулю 11 – «клетки», числа – «кролики».

Задача 4:

В городе Ленинграде живет более 5 миллионов человек. Докажите, что у каких-то двух из них одинаковое число волос на голове, если известно, что у любого человека на голове менее миллиона волос.

Решение:

Постройте миллион клеток с номерами от 0 до 999999 и рассадите там людей, поместив каждого ленинградца в клетку, номер которой равен количеству волос на его голове.

Задача 5:

В магазин привезли 25 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта.

Решение:

25 ящиков-«кроликов» рассадим по 3 клеткам-сортам. Так как 25 = 3 • 8 + 1, то применим «обобщенный принцип Дирихле» для N = 3, k = 8 и получим, что в какой-то клетке-сорте не менее 9 ящиков.

Задача 6:

В стране Курляндии m футбольных команд (по 11 футболистов в каждой). Все футболисты собрались в аэропорту для поездки в другую страну на ответственный матч. Самолет сделал 10 рейсов, перевозя каждый раз по m пассажиров. Еще один футболист прилетел к месту предстоящего матча на вертолете. Докажите, что хотя бы одна команда была целиком доставлена в другую страну.

Решение:

Так как перевезено всего 10m + 1 футболистов, то, рассадив их по клеткам-командам, получаем, что в какой-то клетке сидит 11 футболистов.

Задача 7:

Дано 8 различных натуральных чисел, не больших 15. Докажите, что среди их положительных попарных разностей есть три одинаковых.

Решение:

Различных разностей может быть 14 – от 1 до 14 – это те 14 клеток, в которые мы будем сажать кроликов. Кто же будет нашими кроликами? Ими, конечно, должны быть разности между парами данных нам натуральных чисел. Однако имеется 28 пар и их можно рассадить по 14 клеткам так, что в каждой клетке будет сидеть ровно два «кролика» (и значит, в каждой меньше трех). Здесь надо использовать дополнительное соображение: в клетке с номером 14 может сидеть не более одного кролика, ведь число 14 можно записать как разность двух натуральных чисел, не превосходящих 15, лишь одним способом: 14 = 15 – 1. Значит, в оставшихся 13 клетках сидят не менее 27 кроликов, и применение обобщенного принципа Дирихле дает нам желаемый результат.

Задача 8:

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

Решение:

Вариантов числа знакомых всего 5: от 0 до 4. Осталось заметить, что если у кого-то 4 знакомых, то ни у кого не может быть 0 знакомых.