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

Олимпиадные математические задачи

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

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

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

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

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

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

Типы задач

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

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

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

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

• Доказательство от противного.
• Принцип Дирихле
• Решение методами другой науки (замена алгебраической задачи геометрической или физической и наоборот)
• Правило крайнего
• Решение с конца
• Поиск инварианта
• Построение контрпримера
• Математическая индукция
• Рекурсия
• Метод итераций
• Подсчёт двумя способами
• Метод аналогий
• Провокационный метод
• Вспомогательное построение
• Переход в пространство большего числа измерений
• Вспомогательная раскраска

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

При решении многих задач используется логический метод рассуждения — "от противного". В данной брошюре рассмотрена одна из его форм — принцип Дирихле. Этот принцип утверждает, что если множество из 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 — целые числа. Возведём предполагаемое равенство в квадрат:

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

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

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

Пример:

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

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

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

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

Условие

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

Решение

Составим таблицу умножения для чисел от 1 до 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:

Доказать, что

____

Воспользуемся методом математической индукции.

1. База индукции.

При k = 1, Утверждение верно.

2. Переход индукции.

Допустим при неком k = n (n ∈ N) выражение

истинно. Докажем, что оно верно и при k = n + 1, т.е.

Но так как (исходя из истинности перехода индукции)

то нам нужно доказать следующее утверждение:

.

Делаем преобразования:

.

Для доказательства этого равенства воспользуемся формулой понижения степени косинуса 2cos²x = cos2x + 1. Тогда

= 2(cos^π/₂ⁿ⁺¹ + 1) = 2cos^π/₂ⁿ⁺¹ + 2. Что и требовалось доказать.

Переход доказан, а потому исходное утверждение верно при любом n ∈ N.

Найти все положительные корни уравнения nxⁿ⁺¹ - (n+1)xⁿ + 1 = 0.

_________________________

Запишем уравнение в следующем виде:

nxⁿ⁺¹ - (n+1)xⁿ + 1 = nxⁿ(x - 1) - (xⁿ - 1) = (x - 1)(nxⁿ - x^n-1 - x^n-2 - ... - 1) = 0.

Очевидно, что x = 1 - корень уравнения. Докажем, что других положительных корней нет.

Действительно, если x > 1, то xⁿ > xⁱ, где i < n, а потому

nxⁿ - x^n-1 - x^n-2 - ... - 1 > nxⁿ - nx^n-1 > 0.

Если же 0 < x < 1, то xⁿ < xⁱ, где i < n, а потому

nxⁿ - x^n-1 - x^n-2 - ... - 1 < nxⁿ - nx^n-1 < 0.

Что и требовалось доказать.

Ответ: x = 1.

Целые числа x, y, z удовлетворяют уравнению x³ + y³ = z³. Доказать, что хотя бы одно из этих чисел делится на 3.

________________________________

Докажем от обратного. Допустим все три числа x, y, z не делятся на 3. Тогда их можно представить в виде x = 3a ± 1, y = 3b ± 1, z = 3c ± 1. Наше уравнение будет иметь вид:

(3a ± 1)³ + (3b ± 1)³ = (3c ± 1)³;

27a³ ± 27a² + 9a ± 1 + 27b³ ± 27b² + 9b ± 1 = 27c³ ± 27c² + 9c ± 1;

9(3a³ ± 3a² + a + 3b³ ± 3b² + b - 3c³ 3a² - c) = 1 ± 1 1.

Левая часть равенства делится на 9. Правая часть не делится при любых из вариантов знака ±. Мы пришли к противоречию. А значит одно из чисел делится на 3.

Что и требовалось доказать.

В каждой клетке доски 7x7 сидит жук. В некоторый момент все жуки переползают на соседние (по горизонтали или вертикале) клетки. Обязательно ли при этом останется пустая клетка?

__

Воспользуемся методом раскрасок. Покрасим доску в два цвета с помощью шахматной расцветки:

Переползая на соседнюю клетку, жук становится на клетку другого цвета. Но у нас 24 белых и 25 черных клеток. А, значит, как минимум одна черная клетка будет пустой.

Ответ: Да, обязательно будет одна пустая клетка.

Доказать, что уравнение x³ - px + 1 = 0 не имеет рациональных корней при p ∈ Z, p > 2.

______________________________

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

Докажем от обратного.

Пусть существует некое x₁ ∈ Z, так что x₁³ - px₁ + 1 = 0, при p ∈ Z, p > 2.

Тогда x₁(x₁² - p) = -1.

Единственные решения в целых числах следующие:

x₁ = 1, (x₁² - p) = -1; Но тогда 1 - p = -1, откуда p = 2, что противоречит условию.

x₁ = -1, (x₁² - p) = 1; Тогда 1 - p = 1, p = 0, что опять же противоречит условию.

Значит целых решений нет. Покажем, что и дробных рациональных решений не существует при данном условии.

Снова докажем от обратного. Пусть существует некое x₁ ∈ Q \ Z, такое что x₁³ - px₁ + 1 = 0, при p ∈ Z, p > 2.

В таком случае, по определению x₁ можно представить в виде несократимой дроби ^m/_n,m ∈ N, n ∈ Z. Отметим также, что если дробь ^m/_n - несократима, то и дробь ^m3/_n² - несократима. Тогда уравнение будет иметь следующий вид:

(^m/_n)³ - p(^m/_n) + 1 = 0.

^m3/_n² = pm - n.

Но справа у нас целое число, а значит и слева число целое. А это противоречит нашему предположению, что дробь ^m3/_n² - несократима.

Значит уравнение не имеет рациональных решений.

Что и требовалось доказать.