Задачі на інваріант

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

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

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

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

Пример 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 невозможен, поскольку увеличивает число нечетных сосудов.

При решении математических задач важную роль играет анализ задач. Успех решения задачи во многом определяется качеством анализа. Однако владение искусством анализа дается нелегко. Причина тому - творческий характер этого метода.