Методические материалы для подготовки учащихся к участию в олимпиадах, матбоях
Инварианты
1. Теоретический материал
1.1. Инвариант
Инвариантом некоторого преобразования или системы действий называется величина (или свойство), остающаяся постоянной при этом преобразовании.
В качестве инварианта часто рассматриваются четность (нечетность), остаток от деления, знак выражения, перестановки, раскраски и т.д.
Под инвариантами математических уравнений понимают преобразования, сохраняющие вид уравнений. Упоминается инвариант в математике и в других контекстах.
1.2. Инвариант в различных науках
В физических процессах всегда существуют величины, которые не изменяются с течением времени, они и называются инвариантами. Примеры: энергия, компоненты импульса и момента импульса в замкнутых системах. Понятие инвариантности (инвариантов) в физике лежит в русле принятого в математике понятия "инвариант преобразований (группы преобразований)" (той или иной конкретной группы преобразований - сдвигов времени, преобразований Лоренца и т.д.). Законы сохранения также связаны с инвариантностью.
Инвариантом в программировании называют логическое выражение, истинное после каждого прохода тела цикла (после выполнения фиксированного оператора) и перед началом выполнения цикла, зависящее от переменных, изменяющихся в теле цикла.
В химии инвариант обычно рассматривается как неизменность какой-либо величины, ее независимость от физических условий и по отношению к тем или иным преобразованиям. Инвариант характеристики неорганического вещества включает следующие блоки (элементы системы): состав, название, строение, термодинамические свойства, физические свойства, химические свойства, получение, действие на организм человека, природу, применение.Инвариантом в фольклористике называется неизменяемая часть сюжета фольклорного произведения, которая характерна для всего сюжетного типа.
Инвариант в лингвистике – абстрактное обозначение одной и той же сущности в отвлечении от её конкретных модификаций, отображающее общие свойства класса объектов, образуемого вариантами, и присущие каждому из вариантов. Понятие инварианта — средство классификации, упорядочения языкового материала. Вариант и инвариант противопоставлены друг другу.
Инвариантом при переводе текста называют то, что должно оставаться неизменным в результате перевода, а именно: сообщение, понимаемое как информация, предназначенная для передачи.
1.3. Этапы применения инвариантов при решении школьных олимпиадных задач
При решении школьных олимпиадных задач на применение инвариантов можно выделить (конечно, весьма условно) следующие этапы.
1 этап. Выбор величины (свойства), являющегося инвариантом некоторого преобразования или системы действий.
2 этап. Выполнение соответствующего преобразования или системы действий.
3 этап. Нахождение значения величины (свойства), являющегося инвариантом некоторого преобразования или системы действий, на том этапе, когда вычисление возможно.
4 этап. Определение ответа в задаче на основе найденного значения инварианта.
1.4. Полезные инварианты
1. Четность суммы нескольких целых чисел совпадает с четностью количества нечетных слагаемых.
2. Знак произведения нескольких (отличных от нуля) чисел определяется четностью количества отрицательных сомножителей.
2. Примеры задач
Задача 1. На доске написаны 2010 единиц и 2011 двоек. Разрешается стереть любые две цифры и написать вместо них единицу, если они одинаковы, и двойку, если они различны. Какая цифра останется на доске последней?
Решение. Заменим двойки на –1. Инвариантом будет являться произведение чисел записанных на доске.
В исходной ситуации произведение отрицательно, следовательно, оно отрицательно и в итоге. На доске останется – 1.
Ответ: 2.
Задача 2. Кузнечик прыгал вдоль прямой и вернулся в исходную точку (длина прыжка 1 м). Докажите, что он сделал чётное число прыжков.
Решение. Поскольку кузнечик вернулся в исходную точку, инвариантом будет являться четность количества прыжков насекомого. Расстояние до исходной точки четно, если было сделано четное число прыжков, и нечетно в противном случае. В исходной точке расстояние ноль. Ноль – число четное.
Задача 3. Имеются три числа, которые можно заменять по следующим правилам: числа a, b и c стираются и вместо них записываются (a + b) / 2, (b + c) / 2 и (a + c)/2. Можно ли из чисел 101, 73, 125 получить 77, 79 и 83?
Решение.
1 этап. Инвариантом будет являться сумма
(a + b)/2+(b + c)/2+(a + c)/2 = (2a + 2b + 2c)/2 = a+b+c.
2 этап. Вычислим суммы исходной и конечной тройки
101 + 73 + 125 = 299, 77 + 79 + 83 = 239.
3 этап. Суммы исходной и конечной троек различны.4 этап. Из одной получить другую нельзя.
Ответ: нельзя.
Задача 4. В каждой клетке квадрата 5×5 сидит жук. В некоторый момент жуки переползают на соседние (по горизонтали или по вертикали) клетки. Докажите, что после этого не все клетки будут заняты.
Решение. Раскрасим клетки (через одну) белым и черным цветом. Тогда 13 клеток белых, а 12 черных (или наоборот). При переползании каждый жук меняет цвет клетки, в которой он находился.
В результате 13 жуков на черных клетках, и 12 на белых. Так получаем, что одна белая клетка остается свободной.
3. Задания для самостоятельной работы
1. На столе записаны все натуральные числа от 1 до 2013. Разрешается стереть любые два числа и записать их разность, если числа имеют одинаковый знак, если числа различных знаков на доску записывается их сумма. Может ли в результате 2012 таких действий на доске остаться единственное число 0?
Порядок чисел при нахождении разности может быть произвольным.
2. По кругу в произвольном порядке стоят натуральные числа от 1 до 2012. Разрешается к любым трем подряд идущим числам прибавить по 1 или из любых, подряд идущих чисел, вычесть 1. Можно ли с помощью нескольких таких операций сделать все числа равными 2012?
3. Сейф закрыт на кодовый замок имеющий переключатели, которые могут принимать положение двух видов: , |. Переключатели расположены в клетках таблицы 6*6 и первоначально занимают произвольное положение. При повороте по часовой стрелке одного переключателя вместе с ним поворачиваются все переключатели, находящиеся с ним в одной строке. При повороте против часовой стрелки одного переключателя вместе с ним поворачиваются все переключатели, находящиеся с ним и в одном столбце. Всегда ли можно добиться открытия сейфа? Сейф открыт, если все переключатели имеют вид: .
| | |
| |
| | | |
| | |
| | | |
| | |