Готовимся к олимпиаде. Инварианты

Категория: Математика.

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

В некоторых задачах по математике дается набор преобразований исходного объекта и спрашивается: можно ли, используя эти преобразования, получить из одного состояния объекта другое? Перебором вариантов часто легко убедиться в правильности ответа “нельзя”, однако обосновать этот ответ бывает трудно. Методом, позволяющим во многих случаях решать доказательную часть таких задач, является метод инвариант. Инвариантом называется нечто, не меняющееся в преобразованиях, например, число, набор чисел, четность какого – либо числа и другое. Если значение инварианта в двух состояниях объекта различно, то одно из них нельзя получить из другого. Придумать инвариант должен ученик, самостоятельно решающий задачу; обычно это вызывает у него затруднения. В качестве инварианта чаще всего рассматриваются четность (нечетность) чисел и остаток от деления. Причем применение четности – одна из наиболее встречающихся идей при решении олимпиадных задач.

Вспомним определения четного и нечетного числа. Особое внимание надо уделить абстрактному понятию четности, объяснить, что такое “разная четность”. Например, число х =2 имеет ту же четность, что и число х (или оба четные, или оба нечетные), а при прибавлении единицы четность меняется. Применение идеи четности и нечетности основано на двух важных утверждениях (леммах):

Лемма 1. Четность суммы нескольких целых чисел совпадает с четностью количества нечетных слагаемых.

Пример. Число 1 +2 + 3 + … + 10 – нечетное, так как в сумме 5 нечетных слагаемых. Пример 2. Число 5 + 7 + 9 + 11 +13 + 15 – четное, так как в сумме 6 нечетных слагаемых.

Лемма 2. Знак произведения нескольких (отличных от 0) чисел определяется четностью количества отрицательных сомножителей.

Рассматриваем с учащимися несколько примеров.

Арифметика, алгебра, комбинаторика.

Пример 1. Число (-1) *(-2) *(-3) *(-4) положительно, так как в произведении четное число отрицательных сомножителей.
Пример 2. Число (-1) *2 * (-3) * (-4) отрицательно, так как в произведении нечетное число отрицательных сомножителей.

После этого разбираем подробно следующие задачи.

Задача 1. На листе бумаги написано число 11. Шестнадцать учеников передают листок друг другу, и каждый прибавляет к числу или отнимает от него единицу – как хочет. Может ли в результате получиться число 0?

Нужно предложить выполнить эту операцию учащимся (результат каждого хода записывается на доске), заметить закономерность: после каждого хода характер четности меняется: после первого ученика число становится четным, после второго нечетным; после третьего - четным; после четвертого – нечетным. Тогда после шестнадцатого число будет нечетным. Поэтому нуль в конце получиться не может.

Задача 2. На вешалке висят 20 платков. 17 девочек по очереди подходят к вешалке и либо снимают, либо вешают платок. Может ли после ухода девочек остаться ровно 10 платков?

Решение. После подхода первой девочки количество оставшихся платков либо 19, либо 21 (нечетное количество); после подхода второй девочки – либо 18, либо 20, либо 22 (четное количество); после подхода третьей девочки – либо 17, либо 21, либо 23, либо 19 (нечетное количество). После подхода 17 девочки остается нечетное количество платков. Получается противоречие. Значит, 10 платков остаться не может.

В первой и во второй задачах инвариантом является четность суммы чисел.

Задача 3. В таблице, где имеются 15 чисел (-1), можно производить следующую операцию: одновременно изменить знак двух (не более, не меньше) чисел в таблице. Можно ли, применяя эту операцию конечное число раз, получить таблицу, состоящую из (+ 1)?

Решение. Ответ: нельзя. Так как число чисел в таблице нечетно, а после каждой операции число чисел (+ 1) в таблице четно. На языке инвариантов это означает: инвариантом таблицы относительно введенной операции является произведение всех чисел в таблице. В начальный момент это произведение равно ( - 1), а нам нужно получить таблицу, инвариант которой равен ( + 1).

Задача 4. Имеется набор чисел а, в, с. Данный набор чисел меняется на тройку чисел: а + в – с, в + с – а, а + с – в. Дан набор чисел 2000, 2002, 2003. Можно ли из него получить набор из чисел 2001, 2002, 2003?

Решение. Ответ: нельзя. Так как (а + в + с) и (а + в - с) +(в +с – а) +(а + с – в) равны, а сумма 2000+2002 +2003 и сумма 2001 + 2002 +2003 различны.

Задача 5. На столе 6 стаканов, Из них 5 стоят правильно, а один перевернут вверх дном. Разрешается переворачивать одновременно 4 любых стакана. Можно ли все стаканы поставить правильно?

Решение. Нет, так как в любом случае перевернутых вверх дном стаканов будет числом нечетным.

Задача 6. Из цифр 2, 3, 4,… 9 составили два натуральных числа. Каждая цифра использовалась один раз. Могло ли одно из этих чисел оказаться вдвое больше другого?

Решение. Ответ: нет. Пусть а и b = 2а – полученные числа, S(a) и S(b) – суммы их цифр. По признаку делимости числа N и S(N) имеют одинаковые остатки при делении на 3. Поскольку число a + b = 3a делится на 3, то сумма S = S(a) + S(b) должна делиться на 3, что неверно, так как S = 2 + 3 + 4 + … + 9 = 44.

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

Решение. Так как в конечном итоге на доске оказались записанными два числа, то хотя бы одно из них является остатком от деления некоторого числа на 11, т.е. не превосходит 10.Число 1000 не может являться остатком от деления какого-то числа на 11, поэтому искомое число не больше 10. Заметим, что в результате выполнения указанных операций остаток от деления суммы всех написанных чисел не изменится, так как для любых чисел а и в (а + в)(mod p) (a(mod p) + b(mod p))(mod p), где р – произвольное простое число. Первоначально 1 + 2 + … +1998 = 1997001 6 (mod 11) 1000 (mod p) + второе число. Так как 1000 10 (mod 11), то второе число 7.

Задача 8. В некотором государстве было 10 банков. С момента перестройки общества все захотели стать банкирами. Но по закону открыть банк можно только путем деления уже существующего банка на 4 новых. Через некоторое время министр финансов сообщил президенту, что в стране действует 2007 банков, после чего был немедленно уволен за некомпетентность. Что не понравилось президенту?

Решение. Заметим, что в результате превращения одного старого банка в четыре новых общее количество банков увеличится на 3. Таким образом, в любой момент времени число банков равно Б = 10 + 3 k и остаток от деления числа банков на 3 постоянен. (Это и есть инвариант). То есть Б . Первоначально Б ( mod 3) >, а 2007 .

Задача 9. Разместите цифры 0,1,2,3, …, 9 по кругу так, чтобы сумма всех разностей (по модулю) между соседними числами оказалась равна 25.

Решение. Пусть заданные числа каким-то образом проставлены по кругу и a, b, c, d – четыре соседних числа. Поменяем местами числа a >и c. Исследуем, как изменилась сумма рассматриваемых в задаче разностей. Для расстановки a, b, c, d она равна , а для расстановки a , c, b , d – , где – сумма разностей для оставшихся чисел. Изменение общей суммы Если b >и c имеют одинаковую четность, то будет представлять собой сумму двух четных чисел, а если они разной четности, то является суммой двух нечетных чисел, но в любом случае четно. Следовательно, мы получили инвариант – при перестановке двух соседних чисел четность суммы разностей не изменится. Любую расстановку заданных чисел по кругу можно получить, переставляя несколько раз соседние числа, тем самым мы доказали, что для любой расстановки заданных чисел сумма разностей имеет одну и ту же четность. Рассмотрев произвольную расстановку чисел (от одного до девяти), мы получим, что сумма разностей четна, и, значит, требуемая в задаче расстановка невозможно.

Задача 10. На доске написаны числа 1, 2, 3, …, 1998. За один ход разрешается стереть любые два числа и вместо них записать их разность. В результате многократного выполнения таких действий на доске окажется записанным одно число. Может ли оно быть нулем?

Решение. Не может. Так как вначале на доске 999 нечетных чисел. На каждом шаге их количество не меняется, если среди выбранных чисел не более одного нечетного числа. А если выбранные числа оба нечетны, то количество нечетных чисел уменьшается на два. Таким образом, инвариант преобразования: количество нечетных чисел нечетно. Поэтому в конце должно остаться нечетное число. А нуль – четное число.

Задача 11. Числа 0,1,2,3, …, 9 записаны по кругу. За один ход разрешается прибавить к двум соседним числам одно и то же целое число. Можно ли за несколько ходов получить десять нулей?

Решение. Нельзя. При прибавлении одинаковых целых чисел к любым двум из имеющихся не меняет четность общей суммы всех чисел. Первоначально эта сумма равно 1 + 2 + 3 + … 9 = 45, следовательно, после каждого хода общая сумма полученных чисел должна быть нечетна, а нуль – четное число.

Задача 12. В десяти сосудах содержится 1, 2, 3,…, 10 литров воды. Разрешается перелить из сосуда А в сосуд В столько воды, сколько имеется в В. Можно ли добиться, чтобы после нескольких переливаний в 5 сосудах оказалось 3 литра, а в остальных 6, 7, 8, 9, 10?

Решение. Нельзя. Предложенная операция обладает полуинвариантом: при любом переливании число нечетных сосудов (содержащих нечетное число литров воды) не увеличивается. Количество таких сосудов уменьшается при переливании из нечетного сосуда в нечетный, а в остальных случаях не изменяется. Следовательно, переход 1, 2, … 10 —> 3, 3, 3, 3, 3, 6,…,10 невозможен, поскольку увеличивает число нечетных сосудов.

При решении математических задач важную роль играет анализ задач. Успех решения задачи во многом определяется качеством анализа. Однако владение искусством анализа дается нелегко. Причина тому - творческий характер этого метода. Как научить ребят сознательному владению приемами анализа в решении математических задач? В чем состоит его суть? Смысл анализа состоит в извлечении из формулировки задачи полезных сведений. Однако объём извлеченных сведений иногда оказывается недостаточен для решения. Тогда возникает необходимость в повторном, более глубоком анализе. Почему в одних случаях достигается решение, а в других – лишь некоторые осознание проблемной ситуации? Что мешает этому осознанию?

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

Задача 13. Доказать, что уравнение 3x² – 4xy + 2y² – 21x + 12y – 3 = 0 имеет лишь конечное число целочисленных решений.

Анализ задачи. Заданное уравнение связывает определенными отношениями переменные x и y. Левая её часть представляет собой довольно громоздкий многочлен, а правая равна 0. О самих же переменных известно, что они целые числа. Это обобщенное понятие является и ключевым в нашей задаче. Если рассмотреть каждое слагаемое, легко заметить, что второе, третье, пятое из них всегда являются четными числами, а свободный член – нечетным. Перепишем уравнение в виде: 3x(x – 1) – 18x – 4xy + 2y² + 12y = 3.

Вспомнив свойство четности произведения двух последовательных целых чисел, установим четность первого слагаемого. Теперь мы знаем, что каждое слагаемое левой части уравнения всегда четно, следовательно, четна и их сумма. А в правой части –нечетное число. Приходим к выводу о том, что уравнение не имеет целочисленных решений. >

Задача 14. Найдите множество точек плоскости XOY, координаты которых удовлетворяют уравнению .

Решение. Левая часть уравнения представляет собой сумму расстояний OM + MC, где , . Для любых трех точек имеем полуинвариант, следующий из неравенства треугольника: . В нашем случае . Следовательно, точка должна лежать на отрезке .

16.04.2010

• Назад
• Вперед