ГУ «Аманкарагайская сш им.Н.Островского отдела образования акимата Аулиекольского района» Инвариант как способ решения олимпиадных задач учитель математики Войлошникова Л. И.

Что такое инвариант? Инвариант (от лат. Invarians, неизменяющийся)– числа, алгебраические выражения, величины и т. п., связанные с каким-либо математическим объектом и остающиеся неизменными при определенных преобразованиях. В качестве инварианта могут выступать четность числа, остатки от деления на число, раскраска…

Понятие инвариант употреблялось ещё немецким математиком О. Гессе (1844), но систематическое развитие теория инвариант получила у английского математика Дж. Сильвестра (185152), предложившего и термин «инварианта». В течение 2-й половины 19 в. теория инвариант была одной из наиболее разрабатываемых математических теорий. В 20 в. глубокое влияние на развитие теории инвариант оказала теория относительности.

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

Идея инварианта может возникнуть в задачах, в условиях которых задано некоторое правило преобразования данного в задаче объекта. Величина, которая не изменяется в процессе этого преобразования, называется инвариантом.

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

Стандартные инварианты а ) остаток по некоторому модулю; б) выделение части объекта; в) раскраска; г) алгебраическое выражение от данных задач.

Среди числовых инвариантов наиболее популярны: сумма или произведение всех чисел; четность суммы всех чисел; четность количества имеющихся объектов; разность между двумя числами (например, суммами) или четность этой разности; делимость на 3 и 9; остаток от деления на 3, 4, …

В близком родстве с инвариантами состоят полуинварианты – величины, которые все время увеличиваются (или все время уменьшаются) при операциях.

1. Задачи на инвариант очень распространены. В олимпиаде их может быть не менее двух или трех, что важно сообщить ученикам, т.к. это может быть стимулом для них в изучении данной темы. 2. Идеи инварианта проникают в разные области науки. В качестве примера можно разобрать (если учащиеся знакомы с физикой) различные следствия закона сохранения энергии, а также теоремы типа закона сохранения импульса и т.п.

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

Для этого: 1) тщательно разбирать решение простейших задач; 2) добиваться, чтобы каждый ученик решал задачу самостоятельно; 3) иллюстрировать задачи какими-то примерами; 4) сделать изложение более наглядным; 5) логику изложения сделать более простой; 6) ввести незнакомое слово «инвариант» и излагать его философию после решения и разбора нескольких простейших задач;

7) придумать сам инвариант, для этого: –а) придумываемые величины должны быть инвариантны; –б) эти инварианты должны давать разные значения для двух данных в условии задачи объектов; –в) необходимо сразу задать класс объектов, для которых будет определяться наша величина.

I. Задачи, в которых инвариантом является четность числа. Задача 1.1 Кузнечик прыгает на 1 см, затем прыгает на 3 см в том же или противоположном направлении, затем в том же или противоположном направлении на 5 см и т.д. Может ли он после 57-го прыжка оказаться в исходной точке?

Решение Что бы вернуться в изначальную точку кузнечик должен был пропрыгать какое-то расстояние вправо (х) и такое же расстояние влево (х), следовательно он должен был пропрыгать расстояние равное 2 х, а это число четное. Он прыгнул нечетное количество раз, каждый раз на нечетное количество сантиметров, следовательно он пропрыгал нечетное количество сантиметров. Получено противоречие. Ответ: не может

Задача 1.2 Даны 6 чисел: 1, 2, 3, 4, 5, 6. Разрешается к любым 2-ум из них прибавлять по 1. Можно ли все числа сделать равными?

Решение. Пусть Х- число, к которому мы приведём все числа, тогда 6Х – это сумма всех чисел, а это число четное. Сумма всех чисел равняется 21, а это число нечетное Получено противоречие Ответ: нельзя.

Задача 1.3 Арман купил общую тетрадь объемом 96 листов и пронумеровал все страницы по порядку от 1 до 192. Алибек вырвал из этой тетради 25 листов и сложил все 50 чисел, которые на них написаны. Могло ли у него получиться число 1990?

Решение. Всего 25 листов-нечетное число. Сумма чисел на листе - нечетное число. Следовательно, сумма всех чисел - нечетное число четное число. Получили противоречие Ответ: не может

Задача 1.4 В народной дружине 100 человек. Каждый день на дежурство выходят трое. Докажите, что нельзя организовать график дежурств, чтобы любые два человека дежурили вместе ровно один раз.

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

Задача 1.5 –В парламенте каждый депутат имеет не более трех врагов. Докажите, что парламент можно так разбить на две палаты, что у каждого депутата в палате будет не более одного врага.

Решение. Сначала, разобьем депутатов на две палаты произвольным образом. Если какой-то депутат обнаружит в своей палате более одного врага, то мы переведём его в другую палату. И мы будет производить это действие, пока не выполнится условие задачи

Задача 2.1. Дана шахматная доска размером 5*5. Можно ли замостить доску доминошками 2*1? II. Задачи, в которых инвариантом является раскраска

Решение. Каждая доминошка занимает одну черную и одну белую клетку, следовательно, количество белых и черных клеток должно быть равным. А на доске 5*5 всего 25 клеток, значит количество черных и белых клеток неравное. Получено противоречие.

Задача 2.2. Из шахматной доски вырезали две противоположные угловые клетки. Докажите, что оставшуюся фигуру нельзя разрезать на прямоугольники 2*1.

Решение. Каждая доминошка занимает одну черную и одну белую клетку, следовательно, количество белых и черных клеток должно быть равным. Но когда мы вырезали две противоположные угловые клетки, мы сделали количество белых и черных клеток неравным, следовательно, мы не сможем разрезать данную фигуру.

Задача 2.3. Конь вышел с поля а 1 и через некоторое количество ходов вернулся на него. Докажите, что он сделал четное число ходов

Решение. Т.к. конь ходит буквой «Г»(размером 1*2), то через каждый ход цвет клетки на которой он будет находиться будет меняться, следовательно только через четное количество ходов он вернется на клетку того же цвета.

III. Задачи, в которых инвариантом являются остатки от деления на число Задача 3.1 В стране Серобуромалин живет 13 серых, 15 бурых и 17 малиновых хамелеонов. Когда встречаются два хамелеона разного цвета, они одновременно приобретают окраску третьего цвета (например, серый и бурый становятся малиновыми). Может ли через некоторое время оказаться, что все хамелеоны имеют один цвет?

Решение. Описанная операция состоит в том, что «пропадают» два хамелеона двух разных цветов и «появляются» два хамелеона третьего цвета. Если догадаться о том, что величину-инвариант нужно определять по набору чисел (А,В,С), где А, В и С количества серых, бурых и малиновых хамелеонов соответственно, то дальше решение получается почти сразу же. В самом деле, операция, описанная в условии, означает то, что из набора (А,В,С) получается набор (А-1, В-1, С+2), или набор (А-1, В+2, С- 1), или набор (А+2, В-1, С-1) все зависит от того, в какой цвет перекрашиваются хамелеоны.

Очевидно, что разности между числами набора либо не меняются, либо изменяются на 3, а значит, остатки этих разностей при делении на 3 не меняются они инвариантны. Но в начале А-В=13-15=-2, а в случае, если все хамелеоны малиновые, А-В=0-0=0. Числа 0 и -2 имеют разные остатки при делении на 3, что и доказывает невозможность такого положения дел в стране.

Задача 3.2. К натуральному числу прибавили удвоенную сумму его цифр. Могло ли получиться число 2006?

Решение. Нет. При замене числа на сумму его цифр остаток от деления на 3 не меняется (остаток – инвариант). Так как у данного числа и двух сумм его цифр остатки при делении на 3 одинаковы, сумма этих трех чисел делится на 3, а число 2006 не делится.

Задача 3.3. В последовательности 1; 2; 3; 4; 5; … каждое число заменили суммой его цифр, в новой последовательности проделали то же самое и так далее, пока не получили однозначные числа. Чего больше в последней последовательности – единиц или двоек?

Решение. При замене числа на сумму его цифр остаток от деления на 9 не меняется (инвариант!), поэтому в последнем ряду получились остатки от деления данных чисел на 9: 1; 2; … 9; 1; 2; …; 9; 1; 2; …; 9; 1. Остаток последнего числа, очевидно, равен 1, так десятичная запись числа состоит из одних девяток. Теперь ясно, что единиц в последней последовательности на одну больше, чем любых других чисел.

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

Решение. За одно взвешивание один, более легкий камень выбывает из числа претендентов на звание самого тяжелого. Поэтому независимо от выбора камушков для взвешивания, чтобы оставить только один алмаз, надо удалить 100 алмазов, то есть сделать сто взвешиваний. Так как 100 – четное число, последнее взвешивание сделает второй игрок. Он и победит

СПАСИБО ЗА ВНИМАНИЕ!