ЗАДАЧИ: 1)Сравнить олимпиадные задания прошлых лет. 2)Выявить классы нестандартных заданий. 3)Привести нестандартные примеры

При всем многообразии нестандартных олимпиадных задач по математике можно выделить некоторые, часто встречающиеся классы таких задач. Их знание сразу дает солидное преимущество участнику любой олимпиады. Деление нестандартных задач на классы в известной степени условно. На практике одна задача может принадлежать двум или нескольким таким классам. Их лучше всего изучать на конкретных примерах.

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

Докажите, что два натуральных числа а и b обладают следующим свойством: либо а, либо b, либо a + b, либо a – b делится на 3.(…)

Пусть ни одно из двух чисел не делится на три. Тогда, при делении на 3 они либо дают равные остатки 1 или 2, либо разные остатки. В первом случае на 3 разделится их разность, во втором – их сумма. Возможна следующая символическая запись полученного решения.

К классу целочисленных задач относятся также так называемые Диофантовы уравнения. То есть уравнения с двумя переменными вида: ax + by = c, в которых и переменные и известные параметры являются целыми числами. Легко доказать, что если такое уравнение имеет хотя бы одно целочисленное решение, то оно имеет их бесконечное множество, которое можно выразить соответствующей формулой. Геометрически это означает, что если на прямой ax + by = c с целыми коэффициентами лежит хотя бы одна точка M(x 0 ; y 0 ) с целочисленными координатами, то точек с целочисленными координатами на этой прямой бесконечное множество. Приведём доказательство этого факта с выводом нужных расчётных формул.

§ 2. Задачи на принцип Дирихле Принцип Дирихле (П. Г. Дирихле (1805–1859 гг.) – немецкий математик) иногда называют принципом ящиков. Если в n ящиках находится не менее (n + 1) предметов, то найдётся такой ящик, в котором будет, по меньшей мере, 2 предмета. В шутливой форме можно сказать и так: если 6 кроликов рассаживаются по пяти клеткам, то обязательно найдётся клетка, в которой не менее 2 кроликов. Более общая форма принципа Дирихле утверждает: если в n ящиках находится не менее k*n + r предметов, то в каком – то из этих ящиков находится не менее k + 1 предмета. В задачах на этот принцип важно понять, что имеется в виду под ящиками, а что под предметами.

В университете на 10 факультетах учатся 2008 студентов. Найдётся ли факультет с количеством студентов не менее 201?

Решение. Допустим от противного, что на каждом факультете менее 200 студентов. Но тогда во всём университете их должно быть не более Пришли к противоречию. Следовательно, найдётся факультет, на котором учатся не менее чем 201 студент. Для большей солидности, приведём ещё один пример.

На отрезке [ 0 ; 1 ] числовой оси расположены четыре различные точки: a, b, c, d. Докажите, что на этом отрезке найдётся такая точка х, что имеет место следующее неравенство: (16 Турнир Городов, весенний тур 1996г).

Решение. Четыре точки разбивают отрезок длинной 1 на 5 частей. Следовательно, найдутся две соседние точки, расстояние между которыми не менее 0,2. Пусть, к примеру это точки а и с. Тогда выбираем x = 0.5*( a + c ), то есть среднее арифметическое чисел а и с. Тогда: Следовательно, условие задачи выполнено. Заметим лишь, что в решении использован геометрический смысл модуля: модуль разности равен расстоянию между соответствующими точками на координатной прямой.

§ 3. Логические задачи Задачи с рыцарями и лжецами – традиционные участники многих олимпиад. Для их решения естественно нужны логические рассуждения, доступные конечно не только математикам. Эти задачи формируют культуру доказательных рассуждений. А раздел «Математическая логика» подводит строго научную базу, обосновывающую многие интуитивные догадки. Основная идея поиска решений подобных задач заключена в том, что лгун не признает себя лгуном, а правдивец не может солгать. При всей очевидной простоте изначальных теоретических посылок, бывает не так просто сразу сообразить, каким путём будет найдено нужное решение. Эти задачи выгодно отличаются от многих других незаурядной непредсказуемостью.

Узнику было предоставлено право выйти на свободу, но только в том случае, если он справится с таким заданием: перед ним две двери, одна ведёт на волю, другая – дорога к смерти. Сидят два стражника: один из них – лгун, а второй всегда говорит правду; причём не известно кто из них кто. Задав лишь один вопрос, одному из стражников, узник должен определить дорогу на свободу. Какой вопрос нужно задать?

Ответ: Можно, например, задать такой вопрос, показав на конкретную дверь: «Твой товарищ сказал бы, что эта дверь ведёт на свободу?». Ответ «да» означает, что эта дверь не ведёт на свободу. На мой взгляд – очень красивое, остроумное решение!

§ 4. Задачи на взвешивание Этот класс нестандартных задач по популярности и рейтингу интереса не уступает задачам предыдущего параграфа. Примеров можно привести довольно много. С каждым годом организаторы придумывают всё новые вариации на данную тему. Соответственно решения могут усложняться. Но неизменной остаётся логика рассуждений и перебора возможных ситуаций. При этом могут возникать варианты – одинаковые с точностью до симметричной перестановки. Это существенно сокращает поиск. Но эти варианты должны быть распознаны заранее, иначе можно утонуть в море ложно различных сочетаний.

Есть 12 внешне одинаковых монет двух сортов, по 6 штук каждого сорта. За одно взвешивание про любую группу можно узнать, сколько в ней монет первого сорта. Требуется за два взвешивания найти пару монет разного сорта. Какая именно монета первого сорта, а какая второго, выяснять не надо.

Решение. Для удобства описания договоримся монеты первого сорта обозначать 1, а монеты второго сорта – 0. Предлагается взвесить сразу 8 каких-нибудь монет. С точностью до симметричной перестановки сортов, можно получить всего три существенно различных результата: Будем считать, что взвешенные монеты отложены в зону А, не взвешенные (после 1-го взвешивания – в зону В). Рассмотрим решение в каждом из получившихся вариантах. ВариантРезультат 1) ) )

Вариант 1) Первое взвешивание. (Восемь любых монет) Зона АЗона В Второе взвешивание. Две монеты из зоны А Возможный результатВыборы монет а) 10Выбор монет разного сорта сделан б) 00Берём одну из этих монет, она 2-го сорта, а вторую – любую, оставшуюся в зоне А, она 1-го сорта в) 11Берём одну из этих монет, а вторую – любую из зоны В

Вариант 2) Первое взвешивание. Восемь любых монет. Зона АЗона В Второе взвешивание. Две любых монеты из зоны В Возможный результатВыбор монет а) 10Выбор монет разного сорта сделан б) 00Тогда в зоне В остались две монеты разного сорта

Вариант 3) Первое взвешивание. Восемь любых монет. Зона АЗона В Второе взвешивание. Две любых монеты из зоны В Возможный результатВыбор монет а) 10Выбор монет разного сорта сделан б) 00Одну из этих монет и другую – оставшуюся в зоне В в) 11Случай, симметричный пункту б)

§ 5. Задачи на раскраску и инварианты В этом классе олимпиадных задач для ответа на определённый вопрос помогает удачная раскраска либо клеток некоторой таблицы, либо точек некоторой области в разные цвета. Такое разделение по цветам часто бывает связано с некоторым свойством, которое сохраняется в некоторых состояниях системы, но может меняться в других. Такое свойство принято называть инвариантом. В зависимости от того, сохраняется или меняется инвариант, делается вывод о том способна или нет система перейти из одного состояния в другое. Рассмотрим простой, интересный пример.

Деревянный куб размером 3х3 условно разделен на 27 маленьких кубиков. Жук начинает прогрызать один из крайних угловых кубиков, двигаясь только параллельно рёбрам куба. Может ли жук прогрызть все кубики, побывав в каждом только один раз, и закончив путь в центральном кубике?

Решение. Раскрасим кубики в шахматном порядке. То есть так, чтобы любые два соседних имели разный цвет: один белый, другой – чёрный. Тогда, двигаясь по условию задачи, жук непременно должен проходить из кубика одного цвета – в кубик другого цвета. Чередование цвета при переходе из одного кубика в другой – инвариант данной задачи. Пусть жук начинает движение из кубика чёрного цвета. (См. рис. 29). Рис 29. Раскраска куба в шахматном порядке

Составим таблицу смены цветов кубиков при движении жука. кубика1234…2627 Цвет кубикаЧБЧБ…БЧ То есть последний 27-й кубик должен быть черным, но по рисунку совершенно очевидно, что он – белый. Это противоречие говорит о том, что жук не сможет проделать путь, описанный в задании.

§ 6. Задачи на геометрическую интерпретацию О задачах этого класса уже упоминалось в предыдущих главах. Основной смысл поиска решения – это удачная замена аналитических выражений наглядными геометрическими образами. Для решения задач методом геометрической интерпретации нужно знать, в частности уравнения основных фигур в декартовых координатах. Кроме того, может понадобиться умение построения четвёртого пропорционального отрезка по данным трём отрезкам. Полезно также представлять себе аналитические соотношения между сторонами прямоугольного и других треугольников. Для этого, в принципе, достаточно просто знать теоремы Пифагора и косинусов. Красивый вариант геометрической интерпретации представляет использование неравенства между модулем скалярного произведения двух векторов и произведением модулей этих векторов: Равенство имеет место в случае коллинеарности векторов.

Решите уравнение:

Решение. Введём векторы:. Тогда: Так как равенство возможно лишь для коллинеарных векторов, то имеем уравнение: Проверка показывает, что это и есть корень исходного уравнения.

§ 7. Задачи, решаемые с помощью графов Случается, что в процессе поиска решения приходится обозначать точками некоторые элементы и соединять их линиями. Тогда мы невольно применяем, по крайней мере, самые простейшие понятия теории графов. Рассмотрим некоторые определения из этой теории. Графом называется непустое множество точек, некоторые из которых соединены отрезками. При этом точки называются вершинами, а соединяющие их отрезки – рёбрами графа. Степенью вершины называется число ребер графа, которым принадлежит эта вершина. Вершина называются изолированной, если она не принадлежит ни одному ребру. Граф называется полным, если каждые две различные вершины его соединены единственным ребром. Число рёбер полного графа, имеющего n вершин равно n(n – 1) / 2. Уже перечисленных сведений вполне достаточно для решения многих задач на теорию графов. Рассмотрим не самый сложный пример.

В футбольном первенстве МЯЧЛАНДИИ изъявили желание участвовать сразу 2008 команд. Причем турнир решено провести так, что каждая команда встречается с каждой по одному разу. Может ли случиться так, что в какой-то момент времени каждая из участвующих команд сыграет разное количество матчей?

А что такое всего 2008 команд?! Пусть их будет намного больше, к примеру, целых n. Допустим, в какой-то момент каждая из команд действительно сыграла по разному количеству матчей. Тогда, не нарушая общности, можно представить следующую таблицу. Номер команды 1234…n Число сыгранных матчей 0123…n - 1

Легко убедиться в том, что тогда общее число матчей, сыгранных на данный момент равно n(n – 1) / 2, то есть числу рёбер полного графа, содержащего n вершин. Но тогда откуда одна из них оказалась изолированной? Следовательно, ситуации, описанной в задании, не существует ни в МЯЧЛАНДИИ, ни в какой другой футбольной стране.