Использование инвариантов при решении задач

Увлечение математикой часто начинается с размышлений над какой-то особенно понравившейся задачей. Богатым источником таких задач служат различные олимпиады – от школьных и городских до международных.

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

Рассмотрим простую задачу.

Задача 1.

Может ли разность двух четырехзначных чисел, полученных перестановкой цифр, равняться 2005.

Решение.

Четырехзначные числа, полученные перестановкой цифр, имеют одинаковую сумму цифр. По признаку делимости на 3 оба числа имеют равные остатки при делении на 3, поэтому их разность должна делиться на 3. Но число 2005 не делится на 3, значит, разность этих чисел не может равняться 2005.

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

Если данная величина не изменяется в результате производимых операций, она называется инвариантом. Если же изменяется монотонно (не возрастает или не убывает), то ее называют полуинвариантом.

Рассмотрим пример. Пусть на доске написано число 500. За один ход можно или увеличить его на 15, или уменьшить на 3. Можно ли таким образом получить 1000?

Ответ: нельзя, поскольку остаток от деления на 3 числа, записанного на доске, не меняется (инвариант). Однако остаток от деления 500 на 3 равен 2, а остаток от деления 1000 на 3 равен 1.

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

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

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

В чем же состоит главная идея применения инварианта? В задаче задан некий объект, над которым производятся некоторые операции. Ставится вопрос: можно ли получить с помощью этих операций другой объект с указанным свойством? Чтобы выяснить, это мы строим некую величину, которая не изменяется при совершении разрешенных операций (инвариантна) и, если значения этой величины различны у двух указанных объектов, то ответ на вопрос задачи отрицательный.

Инвариант – числовая характеристика объектов (или функция с какими-то другими значениями на множестве объектов), которая не меняется при указанных операциях.

В целочисленных и других «дискретных» задачах инвариантом часто служит остаток от деления на 2 (четность) или на другое натуральное число.

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

Рассмотрим несколько задач, в которых в процессе решения необходимо отыскать инвариант.

Задача 2.

На доске записаны числа 1, 2, 3, , 1998. За один ход разрешается стереть любое количество чисел и вместо них записать остаток от деления их суммы на 11. Через несколько ходов на доске остались два числа, одно из которых – 1000. Чему равно второе число?

Решение.

Что произошло перед тем, как на доске остались два числа? Было стерто некоторое количество чисел и вместо них записан остаток от деления их суммы на 11. Любое число при делении на 11 дает остатки 0, 1, 2, , 9, 10 и, значит, 1000 не может быть таким остатком. Выходит, второе число и есть остаток от деления суммы чисел на 11, т. е. оно не превосходит 10.

Определим, что в этой задаче является инвариантом. Так как для любых целых чисел a и b остаток от деления суммы (a+b) на произвольное простое число p равен сумме остатков от деления каждого из чисел a и b на p, то в результате выполнения указанных операций остаток от деления суммы всех написанных чисел на 11 не изменится. Это и есть инвариант.

Найдем остаток первоначальной суммы чисел при делении на 11.

1+2+3++1998=1999*999=1999*(1000-1)=1999000-1999=1997001=181545*11+6.

Итак, число 1997001 при делении на 11 дает остаток 6. 1000 при делении на 11 дает остаток 10, так как 1000=90*11+10.

Пусть второе число – остаток от деления на 11 – равно х, тогда 10+х=11*k+6, где 0(х(10, k – целое число. Возможен только один вариант k=1, х=7.

Ответ: второе число 7.

Задача 3.

Несколько одинаковых равносторонних треугольников, в вершинах которых стоят числа 1, 2, 3, сложены стопкой. Может ли сумма при каждой вершине быть равной а) 25; б) 50 ?

Решение.

а) Ответ: не может. Если сумма чисел при каждой вершине равна 25, то сумма всех чисел равна 25*3=75. Сумма же чисел, записанных в вершинах одного треугольника, равна 6. То есть сумма чисел на всех треугольниках должна делиться на 6 (инвариант). Но число 75 не делится на 6.

б) Ответ: может. Если сумма чисел при каждой вершине будет равна 50, то сумма при всех трех вершинах 150. Число 150 делится на 6.

Задача 4.

Дана шахматная доска. Разрешается перекрашивать в другой цвет сразу все клетки какой-либо горизонтали или вертикали. Может ли при этом получиться доска, у которой ровно одна черная клетка?

Решение.

Шахматная доска содержит 8*8=64 клетки. Пусть в одной горизонтали или вертикали k черных и 8–k белых клеток. Перекрасим их, получим 8–k черных клеток и k белых клеток. Найдем, на сколько изменится число черных клеток за один ход:

(8–k)–k=8–2k – на четное число. Так как при выполнении каждого перекрашивания четность числа черных клеток сохраняется (инвариант), из исходных 32 черных клеток мы не сможем получить одну черную клетку.

Задача 5.

Докажите, что парабола обладает следующим инвариантным свойством: абсцисса точки пересечения касательной с осью ОХ равна половине абсциссы точки касания.

Решение.

Пусть х0 – точка касания. Составим уравнение касательной y=px+q к параболе в точке х0.

p=y’(x0)=2kx0 y(x0)=kx02

Уравнение касательной: y=kx02+2kx0(x-x0), y=2kx0x-kx02. Если касательная y=2kx0x-kx02 к параболе в точке x0 пересекает ось ОХ в точке х1, то 0=2kx0x1-kx02, 2kx0x1=kx02, 2x1=x0, x1=1/2x0.