Этюды об инварианте

Многие любят математику, и я вхожу в их число. Особенное удовольствие мне доставляет решение трудных и замысловатых головоломок. Наверное, по этой причине я увлекаюсь олимпиадными задачами. Пытаясь разобраться в секретах их решения, я натолкнулась на понятие «инвариант». Возникло множество вопросов. На чем основано решение задач с помощью инварианта? Каким образом можно его найти? Какие существуют виды инварианта? Одним словом, что же это такое – инвариант?

1. Инвариант - четность.

Сформулируем наиболее важное утверждение, на котором основано применение идеи четности и нечетности.

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

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

Приведем примеры:

1. Число 1+2+. +10 - нечетное, так как в сумме 5 нечетных слагаемых.

2. Число 3+5+7+9+11+13 - четное, так как в сумме 6 нечетных слагаемых.

• Важно понимать, число х+2 имеет ту же четность, что и число х (эти числа или оба четные, или оба нечетные), а числа а и а+1 имеют разную четность (если а – четное число, то а + 1 – нечетное, а если а – нечетно, то а + 1 – четно).

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

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

Решение:

На столе вверх дном стоит нечетное число стаканов. Для того чтобы все стаканы стояли правильно нужно, чтобы число, стоящих вверх дном стаканов, равнялось нулю, т. е. четному числу. Перевернуть 4 стакана можно несколькими способами. Рассмотрим их.

1. Если перевернуть 4 стакана, то на столе останется нечетное число стаканов, стоящих вверх дном.

2. Перевернув 3 стакана, а затем 1 разными способами, мы, по сути, перевернем 2 стакана. 2 – четное число, значит, на столе стоящих вверх дном стаканов останется нечетное количество.

3. И, наконец, перевернув 2 и 2 стакана разными способами, мы снова получим нечетное число, стоящих вверх дном стаканов, так как, по сути, мы не изменили ситуацию. Следовательно, невозможно добиться того, чтобы все стаканы стояли правильно, то есть вниз дном.

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

Задача 2. На доске написаны числа 1, 2, 3,. , 2004, 2005, 2006, 2007. Разрешается стереть с доски любые два числа и вместо них записать модуль их разности. В конце концов, на доске останется одно число. Может ли оно равняться нулю?

Решение:

Сумма всех записанных на доске чисел будет нечетной, так как количество нечетных чисел – нечетно. При стирании двух чисел возможны 3 варианта: а) стираются 2 четные числа, тогда модуль разности будет четным числом, а новая сумма будет числом нечетным; б) стираются 2 нечетные числа, тогда модуль разности будет четным числом, а новая сумма будет числом нечетным; в) стираются 1 четное и 1 нечетное число, тогда модуль разности будет нечетным числом, а новая сумма будет снова числом нечетным;

Таким образом, в любом случае, на доске останется нечетное число. Так как нуль – число четное, то оставшееся число нулем быть не может.

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

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

Решение:

В этой задаче полезно найти сумму всех данных чисел. Найдем сумму чисел, записанных по кругу, она равна 45. Прибавляя 2 одинаковых целых числа к соседним числам, мы к нечетному числу прибавляем четное: сумму двух одинаковых целых чисел, следовательно, получим нечетное число. Таким образом, характер четности суммы не меняется: она по-прежнему остается нечетной. Так как сумма 10 нулей – нуль – число четное, то указанными преобразованиями получить 10 нулей нельзя.

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

Решим подобную задачу.

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

Решение:

Так как сумма данных чисел: число 27 – нечетное, а при прибавлении двух одинаковых целых чисел четность суммы не меняется, то получить все нули во всех вершинах невозможно, так как сумма восьми нулей – число четное.

В этой задаче инвариант – нечетность суммы чисел, записанных в вершинах куба.

Задача 5. На чудо - дереве садовник вырастил 45 груш и 50 яблок. Каждый день он срывает 2 плода и тут же на дереве вырастает новый. Причем, если он срывает 2 одинаковых плода, то вырастает яблоко, а если – 2 разных, то вырастает груша. Каким окажется последний плод на дереве?

Решение:

Рассмотрим возможные случаи:

1) Садовник сорвал 2 яблока, тогда вырастает 1 яблоко и на дереве будет 45 груш и 49 яблок.

2) Садовник сорвал 2 груши, в этом случае вырастает 1 яблоко и на дереве будет 43 груши и 51 яблоко.

3) Если же садовник срывает 2 разных плода: яблоко и грушу, то на дереве вырастает груша и всего плодов будет: 45 груш и 49 яблок.

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

Задача 6. Круг разбит на 10 секторов, в каждом из которых стоит по одной фишке. Одним ходом разрешается любые 2 фишки передвинуть в соседние секторы. Удастся ли через несколько ходов все фишки собрать в одном секторе?

Решение:

Пронумеруем сектора последовательно числами 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 и присвоим каждой фишке номер сектора, в котором она находится. При передвижении какой-либо фишки в соседний сектор номер фишки меняется на единицу. Поэтому четность суммы номеров всех фишек при любых передвижениях двух фишек не меняется. В первоначальном положении сумма всех номеров фишек была равна 1+2++10=55 (нечетное число). Если бы все фишки удалось собрать в одном секторе, то сумма номеров была бы четной, так как сумма десяти одинаковых чисел – четное число. Значит, собрать фишки в одном секторе не удастся.

В этой задаче инвариантом будет нечетность суммы номеров секторов.

Вывод. При решении задач, аналогичных задачам 1, 2, 3, 4, 5 и 6 , нужно учитывать сохранение четности суммы чисел.

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

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

Решение:

От прибавления или вычитания единицы меняется характер четности числа: после первого ученика число становится нечетным; после второго четным; после третьего – нечетным. Следовательно, если 25 раз менять характер четности числа 10, в результате получится нечетное число. Значит, число 0 получиться не может.

В этой задаче инвариантом будет чередование четности и нечетности числа после совершения над ним предложенной операции.

Задача 8. Конь вышел с поля а1 шахматной доски и через несколько ходов вернулся на него. Докажите, что он сделал четное число ходов.

Решение:

При каждом своем ходе конь меняет цвет поля, поэтому при возвращении обратно он должен сделать четное число ходов.

Инвариантом в данной задаче будет изменение цвета клетки при изменении четности хода.

Задача 9. На плоскости расположено 13 шестеренок, соединенных по цепочке. Могут ли все шестеренки вращаться одновременно? А если шестеренок 14?

Решение:

Пусть первая шестеренка вращается по часовой стрелке, тогда вторая – против часовой стрелки, третья – по часовой стрелке и т. д. Получим, что двенадцатая будет вращаться против часовой стрелки, а тринадцатая – по часовой стрелке. Значит, первая должна вращаться против часовой стрелки, что противоречит тому, что она вращается по часовой стрелке. Поэтому, все 13 шестеренок вращаться одновременно не могут. А вот 14 уже могут.

В задаче неизменно то, что каждая четная шестеренка вращается против часовой стрелки, а каждая нечетная – по часовой стрелке, поэтому инвариантом в этой задаче является чередование четности и нечетности места шестеренки.

Задача 10. 2003 человека выстроились в шеренгу. Всегда ли можно их расставить по росту, если за один ход разрешается переставлять только двух человек, стоящих через одного?

Решение:

Нет, так как при перестановке сохраняется четность номера места. Поэтому, если самый высокий человек, например, стоит вторым, то он никогда не станет первым.

Здесь число 2003 роли не играет.

Инвариантом в этой задаче является сохранение четности или нечетности места человека.

Задача 11. 100 фишек стоят в ряд. Любые две фишки, расположенные через одну, можно менять местами. Удастся ли расположить фишки в обратном порядке?

Решение:

Так как при перестановке фишек четность места фишки сохраняется, то первую фишку никогда не сделать последней (1 – число нечетное, а 100 – число четное).

В этой задаче не изменяется четность или нечетность места той или иной фишки, а значит, инвариантом будет чередование четных и нечетных мест.

Вывод. При решении подобных задач важно найти чередующиеся объекты.

При решении задач 12, 13, 14 необходимо научиться объекты разбивать на пары.

Задача 12. Все костяшки домино выложены в цепь. На одном конце цепи оказалось 3 очка. Сколько очков на другом конце?

Решение:

Всего костяшек с тройкой на конце 7: 0-3, 1-3, 2-3, 3-3, 4-3, 5-3, 6-3. Костяшка 3-3 имеет «тройку» на обоих концах. Без нее остается 6 костяшек. Так как при игре в домино в цепи они должны располагаться парами, то на другом конце цепи будет 3 очка.

Инвариантом в данной задаче будет наличие для каждой тройки пары.

Задача 13. При дворе короля Артура собрались 30 рыцарей, причем каждый из них имеет среди присутствующих не более 14 врагов. Докажите, что Мерлин, советник Артура, может так рассадить рыцарей за Круглым Столом, что ни один из них не будет сидеть рядом со своим врагом.

Решение:

Рассадим рыцарей за Круглым Столом произвольным образом. Если при этом получится, что никакие два врага не сидят рядом, то требование задачи выполнено. В противном случае рассмотрим рыцаря А, сидящего слева от своего врага В. Среди друзей рыцаря А обязательно найдется такой рыцарь С, что его правый сосед D – друг рыцаря В (иначе у рыцаря В врагов более 14). Поменяем рыцарей В и С местами. При этом рыцарь В станет соседом рыцаря D, рыцарь С – соседом рыцаря А. Остальные пары соседей не изменятся. Поступая аналогично с рыцарями, сидящими со своими врагами, мы придем к искомому расположению рыцарей за Круглым Столом.

В АВ А С А

Задача 14. Можно ли по правилам игры в домино выложить все 28 костей в одну цепочку так, чтобы сумма на ее концах была нечетной? (Дубли кладем вдоль цепи, конечной считаем вторую половину кости).

Решение:

В наборе домино клеток-половинок кости с одинаковым количеством очков 8 штук, а в цепи они стоят подряд по 2 или 4. Значит, на концах может оказаться только разорванная пара. Поэтому сумма очков на концах будет четной. Значит, выложить цепь так, что сумма очков на концах была нечетной, нельзя.

Здесь инвариантом является то, что каждая половинка костяшки имеет пару.

Рассмотрим последний вид задач, где инвариантом является четность.

Задача 15. Можно ли разменять купюру достоинством 50 рублей с помощью 15 монет достоинством 1 и 5 рублей?

Решение:

Числа 1 и 5 – нечетные. Так как сумма 15 нечетных чисел является числом нечетным, а 50 – число четное, то разменять 50 рублей на 15 монет по 1 и 5 рублей нельзя.

Инвариантом в данной задаче будет нечетность суммы 15 нечетных чисел.

Задача 16. В древней рукописи приведено описание города, расположенного на 8 островах. Острова соединены между собой и с материком мостами. На материк выходят 5 мостов; на 4 островах берут начало 4 моста, на 3 островах берут начало 3 моста и на один остров можно пройти только по одному мосту. Может ли быть такое расположение мостов?

Решение:

Найдем число концов у всех мостов: 5+4×4+3×3+1=31.

Число 31 является нечетным. Так как число концов у всех мостов должно быть четным, то такого расположения мостов быть не может.

Инвариант – четность числа концов моста.

Задача 17. На доске написаны в строку 2003 целых числа. Докажите, что из них можно стереть одно число так, что сумма оставшихся чисел будет четной. Верно ли это для 2002 чисел?

Решение:

Рассмотрим 3 случая.

а) Среди 2003 целых чисел есть четные и нечетные числа. Если количество нечетных чисел нечетно, то стираем любое из них. Если количество нечетных чисел четно, то из 2003 целых чисел хотя бы одно четное. Его и стираем.

б) Пусть все 2003 числа – нечетные. Тогда стираем любое из них.

в) Пусть все 2003 числа – четные. В этом случае стираем любое из них.

В случае, когда чисел 2002 и все они нечетные, оставшаяся сумма не может быть четной. Поэтому для 2002 целых чисел это неверно.

Инвариантом в этой задаче является то, что сумма нечетного количества нечетных чисел – нечетное число.

Задача 18. Страницы книги пронумерованы подряд с первой до последней страницы. Хулиган Вася вырвал из разных мест книги 17 листов и сложил номера всех 34 вырванных страниц. У него получилось число 2002. Правильно ли Вася сосчитал?

Решение:

На каждом из 17 листов сумма номеров двух страниц число нечетное, так как на одной странице номер четный, а на другой – нечетный. Тогда сумма 17 нечетных чисел будет нечетной. Так как 2002 – число четное, то Вася ошибся при подсчете.

Инвариант – сумма 17 нечетных чисел – нечетное число.

Задача 19. 101 лошадь разместили в 15 конюшнях. Почему хотя бы в одной конюшне будет обязательно нечетное число лошадей?

Решение:

Докажем задачу методом от противного. Пусть в каждой конюшне находится четное число лошадей, тогда сумма четных чисел – число четное. А по условию всего лошадей 101 – число нечетное. Таким образом, получили противоречие. Значит, хотя бы в одной конюшне будет нечетное число лошадей.

Инвариантом в данной задаче будет четность суммы нескольких четных чисел.

Задача 20. 16 корзин расположили по кругу. Можно ли в них разложить 55 арбузов так, чтобы количество арбузов в любых двух соседних корзинах отличалось на 1?

Решение:

Если число арбузов в соседних корзинах отличается на 1, то характер четности числа арбузов в этих корзинах будет разным. Тогда четность числа арбузов в корзинах будет чередоваться, поэтому в половине корзин будет четное число арбузов, а в половине нечетное. Тогда общее число арбузов в 8 корзинах с четным числом арбузов и в 8 корзинах с нечетным числом арбузов будет четным. По условию же всего арбузов – 55, а это нечетное число. Значит, разложить нельзя.

Инвариантом в данной задаче будет то, что сумма четного количества чисел – четное число.

Вывод. При решении подобных задач следует определить характер четности суммы чисел.

2. Инвариант – остаток от деления.

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

Задача 21. Мише учитель математики поставил в дневник отметку «2». Миша, желая скрыть от мамы данный факт, порвал свой дневник на 4 части. Этого ему показалось мало, поэтому некоторые из этих частей (может быть и не все) он порвал на 4 части и так далее. Мама нашла 20 «кусочков» дневника. Все ли куски нашла мама?

Решение:

Для того, чтобы решить задачу, необходимо ответить на вопрос: «Какое число обрывков могло получиться?» Сначала Миша порвал дневник на 4 части. Если он порвал на 4 части один из четырех кусочков, то их станет 4+ 3 = 7. Если Миша и дальше будет рвать кусочки на 4 части, то их будет получаться 4 +6 = 10, 4 + 9 = 13, 4 + 12 = 16, 4 + 15 =19, 4 +18 =22 и так далее. Таким образом, кусочков может быть 4, 7, 10, 13, 16, 19, 22, Значит, мама нашла не все кусочки. Можно заметить, что при делении каждого из этих чисел на 3 получается остаток 1.

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

Решим еще несколько подобных задач.

Задача 22. Хулиганы Вася и Петя порвали школьную стенгазету, в которой была заметка об их плохой учебе. Причем Вася рвал каждый кусок на 5 частей, а Петя на 9. Заместитель директора школы, заметив такое безобразие, потребовала собрать обрывки стенгазеты. Ребята нашли 1999 обрывков. Все ли обрывки были найдены и почему?

Решение:

Рассмотрим, какое число обрывков могло получиться. Если Вася первоначально порвал стенгазету на 5 кусков, а затем один из кусков снова на 5, то всего их получается 9. Если теперь Вася будет дальше рвать некоторые куски на 5, а Петя на 9, то число кусков может получиться 5, 9, 13, 17, 21 и т. д. Можно заметить, что общее число кусков можно записать как 4n+1. Так как 1999=499×4+3, то ученики собрали не все обрывки стенгазеты.

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

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

Решение:

В результате превращения одного старого банка в четыре новых общее число банков увеличивается на 3, тогда количество банков может быть равным 10 + 3 =13, 10 +6 = 16, 10 +9 = 19, и так далее. Таким образом, в любой момент времени число банков будет равно 10+3n. Остаток от деления 10 (первоначальное количество банков) на 3 равен 1, а 2001 делится на 3 без остатка. Значит, образоваться ровно 2001 банка в стране не могло.

Здесь инвариантом является остаток от деления на 3.

Вывод. При решении задач, аналогичных задачам 22, 23, 24, инвариантом является остаток от деления.

3. Инвариант – знак произведения.

Сформулируем наиболее важное утверждение, которое используется при решении задач, где в качестве инварианта выступает знак произведения:

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

Приведем примеры:

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

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

Применяя это утверждение, решим следующие задачи.

Задача 24. Квадрат 5×5 заполнен числами так, что произведение чисел в каждой строке отрицательно. Доказать, что найдется столбец, в котором произведение чисел так же отрицательно.

Решение:

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

Инвариантом в этой задаче является знак произведения всех чисел в квадрате – оно отрицательное.

Задача 25. В каждую клетку квадратной таблицы размером 25×25 вписано произвольно одно из чисел: +1 или -1. Под каждым из столбцов записывается произведение всех чисел данного столбца, а справа от каждой строки – произведение всех чисел данной строки. Может ли сумма всех 50 произведений быть равной нулю?

Решение:

Перемножая все 50 произведений, мы получим 1, так как в каждое произведение любое из чисел, вписанных в клетки таблицы, войдет 2 раза - один раз в произведение по строкам, один раз – по столбцам. Тогда в число пятидесяти множителей будет входить четное число произведений, с «-1». Поэтому сумма четного числа произведений, с «1», и четного числа произведений, с «-1», не может быть равна 0. (Одинакового числа слагаемых не будет, так как 50 : 2 = 25 – число нечетное. )

Инвариантом в этой задаче будет знак произведения 50 множителей.

Вывод: При решении задач, аналогичных задачам 24 и 25, используется идея – нахождение произведения чисел.

III. «Свои» задачи.

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

Задача 1. В магазин привезли несколько коробок с конфетами. Продавец раскладывал конфеты из каждой маленькой коробки в 18 пакетов, а из каждой большой – в 27 пакетов. Разложив все конфеты, продавец насчитал 352 пакета с конфетами. Докажите, что он ошибся.

Решение:

Числа 18 и 27 делятся на 3 без остатка, значит сумма нескольких таких чисел, тоже будет нацело делиться на 3. Но 352:3=117+1, значит, продавец ошибся.

Задача 2. По кругу записаны числа 1, 2, 3, , 99, 100. Разрешается прибавить или отнять от числа модуль разности соседних чисел и записать вместо него полученный результат. Можно ли после нескольких таких операций получить одинаковые числа?

Решение:

Два соседних числа либо оба четные, либо оба нечетные, значит модуль их разности всегда четное число. От его прибавления четность числа не меняется. Значит, четные и нечетные числа будут чередоваться, и получить одинаковые не удастся.

Задача 3.

Сумма 507 чисел - четное число. Каким, четным или нечетным будет произведение этих чисел?

Решение:

Сумма 507 нечетных чисел – нечетная, значит, среди них есть хотя бы одно четное число. А произведение четного и нечетных – четное число. Значит, произведение этих чисел четное.

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