Материалы по теме "Инвариант"
олимпиадные задания

Инвариант (1)

1. Конь вышел с поля a1 шахматной доски и через несколько ходов вернулся на него. Докажите, что он сделал четное число ходов?
2. Можно ли доску размером 5×5 заполнить «доминошками» размером 1×2?
3. В древней рукописи приведено описание города, расположенного на 8 островах. Острова соединены между собой и с материком мостами. На материк выходят 5 мостов; на 4 островах берут начало по 4 моста, 3 островах берут  начало по 4 моста, на 3 островах берут начало по 3 моста и на один остров можно пройти только по одному мосту. Может ли быть такое расположение мостов?
4. 16 корзин расположили по кругу. Можно ли в них разложить 55 арбузов так, чтобы количество арбузов в любых двух соседних корзинах отличалось на 1?
5. На столе стоят 7 стаканов – все верх дном. Разрешается за один перевернуть любые 4 стакана. Можно ли за несколько раз добиться того, чтобы все стаканы стояли правильно, т.е. вниз дном?
6. На доске написано 8 плюсов и 13 минусов. Разрешается стирать любые два знака и написать вместо них плюс, если они одинаковы, и минус в противном случае. Какой знак останется после выполнения 20 таких операций?
7. Учитель написал на листке бумаги число 10. 25 учеников передают листок друг другу, и каждый прибавляет или отнимает от числа 1 – как хочет. Может ли в результате получиться число 0?
8. В некотором государстве первоначально было 10 банков. С момента перестройки общества все захотели быть банкирами. Но по закону открыт банк можно только путем деления уже существующего банка на 4 новых банка. Через 2 гола министр финансов сообщил президенту, что в стране действует уже 2001 банк, после чего был немедленно уволен за некомпетентность. Что не понравилось президенту?
9. У Ивана-царевича есть два волшебных меча: с помощью первого он может отрубить у Змея Горыныча 21 голову, а с помощью второго – 4 головы, но тогда у Змея Горыныча отрастает 1999 голов. Может ли Иван отрубить Змею Горынычу все головы, если в самом начале у него было 30 голов? (Примечание: если у Змея Горыныча осталось 3, 2 или 1  голова, то ни каким мечом рубить нельзя.)
10. На чудо-дереве садовник вырастил 45 бананов и 50 апельсинов. Каждый день он срывает новый. Причем если он срывает 2 одинаковых плода, то вырастает апельсин, если 2 разных, то вырастает банан. Каким окажется последний плод на дереве?

Ответы ИНВАРИАНТ (1):

1. При каждом своем ходе конь меняет цвет поля, поэтому при возвращении обратно он должен сделать четное число ходов.
2. Нет, так как общее число клеток – 25 не делится на 2.
3. Найдем число концов у всех мостов: 5+4×4+3×3+1 = 31 – является числом нечетным. Так как число концов у всех мостов должно быть четным, то такое расположения мостов быть не может.        
4. Если число арбузов в соседних корзинах отличается на 1, то характер четности числа арбузов в этих корзинах будут разным. Тогда четность числа арбузов в корзинах будет чередоваться, поэтому половине корзин будет четное число арбузов, а в половине – нечетное. Тогда общее число арбузов в 8 корзинах с четным числом арбузов и в 8 корзинах  с нечетным числом арбузов будет четным. По условию же всего арбузов 55, т.е. нечетное число. Значит, разложить нельзя
5. Нет, так как в любом случае число перевернутых вверх дном стаканов будет числом нечетным.  
6. Заменяя все плюсы нулями, а минусы – единицами, заметим, что сумма двух стираемых чисел имеет тот же характер четности, что и число, записываемое вместо них. Так как сумма всех чисел была нечетной (13), то и последнее оставшееся число будет нечетным, т.е. единицей, и, значит, на доске останется минус.
7. От прибавления или вычитания единицы меняется характер четности числа 10, то в результате получиться нечетное число. Следовательно, число 0 получиться не может.
8. Заметим, что в результате превращения одного старого банка в четыре новых общее число банков увеличивается на 3. Таким образом в любой момент времени число банков будет равно 10+3n. Первоначально остаток от деления количества банков на 3 был равен 1, а 2001 при делении на 3 дает остаток 0. Значит, образоваться ровно 2001 банков в стране не могло.  
9. Змей Горыныч теряет либо 21 голову, либо приобретает 1995 голов. Оба эти числа делятся нацело на 7, а в начале поединка остаток был 2. В случае же отсутствия голов у Змея Горыныча остаток был бы 0. Значит, отрубить все головы Змею Горынычу Иван-царевич не сможет.
10. Рассмотрим несколько случаев:

1. Садовник сорвал 2 апельсина, тогда вырастает 1 апельсин и на дереве будет 45 бананов и 49 апельсинов.
2. Садовник сорвал 2 банана, в этом случае вырастает 1 апельсин и на дереве будет 43 банана и 51 апельсин.
3. Если же садовник срывает 2 разных плода: апельсин и банан, то на дереве вырастает банан и всего плодов будет: 45 бананов и 49 апельсинов.

Итак, можно заметить, что в каждом из трех случаев неизмененным остается одно, а именно: количество бананов – нечетное число. Значит, инвариантом будет нечетность числа бананов на дереве, а поэтому последним плодом окажется банан.

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

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

Вспомним определения четного и нечетного числа. Особое внимание надо уделить абстрактному понятию четности, объяснить, что такое “разная четность”. Например, число х =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. Доказать, что уравнение 3x2 – 4xy + 2y2 – 21x + 12y – 3 = 0 имеет лишь конечное число целочисленных решений.

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

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

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

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