Invariants - 27 Oct 2009
Sergey Sobolev
Инвариант -- это то, что не меняется при разрешённых действиях.
Это может быть сумма, произведение, чётность, остаток от
деления чего-то на какое-то число или что-нибудь другое.
Инварианты в математике полезны так же, как законы сохранения в
физике (например, закон сохранения энергии).
Задача. На острове живут 3 серых, 5 бурых и 7 малиновых
хамелеонов. Когда встречаются два хамелеона разного цвета, они
одновременно меняют свой цвет на третий. Может ли случиться
так, что в какой-то момент все хамелеоны будут одного цвета?
Решение. Пусть a -- количество серых, b -- бурых и c --
малиновых хамелеонов. Посмотрим, как меняется тройка чисел
(a,b,c) при встречах хамелеонов:
(1) встречаются серый и бурый: (a,b,c) --> (a-1,b-1,c+2);
(2) встречаются серый и малиновый: (a,b,c) --> (a-1,b+2,c-1);
(3) встречаются бурый и малиновый: (a,b,c) --> (a+2,b-1,c-1).
Инвариантом является сумма a+b+c, так как количество хамелеонов
не меняется. Этот инвариант не говорит, что хамелеоны не смогут
стать все одного цвета, но говорит о том, что если хамелеоны
станут в какой-то момент одного цвета, то тройка (3,5,7)
превратится в тройку (4,4,4).
Есть ещё инварианты. Посмотрим, как меняется a-b:
(1) (a-1)-(b-1) = a-b
(2) (a-1)-(b+2) = a-b-3
(3) (a+2)-(b-1) = a-b+3
Итак, a-b меняется на кратное 3, то есть остаток от деления a-b
на 3 не меняется. Значит, этот остаток a-b mod 3 -- инвариант.
Вычислив a-b для (3,5,7) и для (4,4,4), получим числа -2 и 0 --
они отличаются на 2, а это число, не кратное 3. Значит,
хамелеоны не смогут быть в какой-то момент все одного цвета.
Записи "с остатком":
для (3,5,7) a-b = 3-5 = -2 = 1 mod 3,
для (4,4,4) a-b = 4-4 = 0 mod 3.
Задачи
1. На листке написаны целые числа от 1 до 10. Разрешается за
один ход стереть любые два числа и написать вместо них их
сумму. Какое число останется в конце?
2. На столе стоят 7 стаканов, все вверх дном. За один ход можно
одновременно перевернуть два стакана. Можно ли добиться того,
чтобы все стаканы стояли вниз дном?
3. Круг разбит на 6 секторов, в которых по часовой стрелке
расставлены числа 1, 2, 3, 4, 5, 6. За один ход разрешается
прибавить по единице к любым двум соседним числам. Можно ли
добиться того, чтобы все числа стали одинаковы?
4. Аня порвала лист бумаги на 3 части и дальше рвёт каждый
попадающийся ей кусок тоже на 3 части. Может ли у неё
получиться 100 кусков?
5. В банке находится 17 черных и 17 белых кофейных зёрен.
Разрешается за один ход выбрать случайно два зерна, и если они
одного цвета, то вынуть их и добавить в банку черное зерно, а
если они разного цвета, то белое зерно вернуть в банку, а
черное вынуть. Какого цвета зерно останется в банке?
6. Шесть детей стоят по кругу, и на каждом из них сидит комар.
Время от времени какие-то 2 комара одновременно перелетают со
своего ребёнка на соседнего. Могут ли все комары собраться на
одном ребёнке?
7. В таблице 8x8 одна из клеток закрашена черным цветом, а все
остальные -- белым. Можно ли с помощью перекрашивания строк и
столбцов добиться того, чтобы все клетки стали белыми?
Перекрашивание -- это операция изменения цвета всех клеток в
строке или столбце.
Подсказка. Покажите, что сохраняется Чётность (остаток от
деления на 2) числа чёрных клеток.
8. Из бумажной шахматной доски 8x8 вырезали две клетки: левую
нижнюю и правую верхнюю. Можно ли дальше разрезать её на
прямоугольники 2x1?
Подсказка. Вырезанные клетки одного цвета.
9. Можно ли пройти конём из левого нижнего угла шахматной доски
в правый верхний угол, побывав на каждой клетке ровно один раз?
Подсказка. При ходе коня меняется цвет клетки.
Решения принимаются до 27 октября. На сайте кружка
http://mathcircle.csmath.org
на странице задания есть pdf-файл для печати.
Alpha (10-12 лет): 4 задачи, Beta (13-14 лет): 8 задач.