Инвариант и полуинвариант

Инвариант

Инвариант — это некоторая величина или свойство, которое не меняется при каких-то преобразованиях или действиях, то есть что-то, что постоянно сохраняется.

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

Решим несколько вспомогательных задач.

1.  Дана таблица Изначально в ней записаны числа 1, 2, 3 и 4, как показано на картинке. Разрешается к любым двум числам, расположенным в соседних по стороне клетках, прибавить по единице. Может ли после некоторых действий сумма чисел в таблице стать равной 101?

Ответ. Нет, не может

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

Таким образом, сумма чисел в таблице всегда будет четна, то есть никогда не будет нечетной, в том числе никогда не будет равна 101.

2.  Круг разделен на 6 секторов, в которых по часовой стрелке стоят числа 1, 0, 1, 0, 0, 0. Разрешается прибавлять по единице к любым числам, стоящим в двух соседних секторах. Можно ли сделать все числа равными?

Ответ. Нет, нельзя

Решение. Закрасим в черный цвет сектора, которые расположены через один, начиная с сектора с числом 1. Получим такую раскраску:

Тогда сумма чисел, стоящих в черных секторах, изначально равна 2, а в белых секторах — 0. Следовательно, разность между суммами чисел в черных секторах и белых секторах равна 2.

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

Заметим, что если в какой-то момент окажется, что все числа стали равными, то разность между суммами чисел в черных и белых секторах должна равняться 0. Но мы доказали, что эта разность всегда равна 2, следовательно, числа во всех секторах нельзя сделать равными.

3.  На острове живут 13 серых, 15 бурых и 17 малиновых хамелеонов. При встрече два хамелеона разного цвета одновременно меняют свой цвет на третий. Может ли случиться, что через некоторое время все хамелеоны станут одного цвета?

Ответ. Нет, не может

Решение. Предположим, что может, тогда распределение по цветам будет таким в некотором порядке: 45, 0, 0.

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

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

Тогда остаток при делении на 3 нашей разности не меняется и не может стать нулем. Следовательно, все хамелеоны не могут стать одного цвета.

Рассмотрим следующую задачу с ЕГЭ-2022:

Есть три коробки: в первой коробке 64 камня, во второй — 77 камней, а в третьей коробке камней нет. За один ход берут по одному камню из любых двух коробок и кладут в оставшуюся. Сделали некоторое количество таких ходов.

а) Может ли в первой коробке оказаться 64 камня, во второй — 59 камней, а в третьей — 18 камней?

б) Может ли в третьей коробке оказаться 141 камень?

в) В первой коробке оказался 1 камень. Какое наибольшее число камней может оказаться в третьей коробке?

Ответ. а) Да, может

б) Нет, не может

в) 138

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

б) Рассмотрим разность чисел камней во второй и первой коробках. Пусть в первой сейчас камней, во второй камней. Тогда разность равна

Если мы переложим два камня в первую коробку, то разность будет равна

Если мы переложим два камня во вторую коробку, то разность будет равна

Если мы переложим два камня в третью коробку, то разность будет равна

Мы получили, что после любой операции разность либо изменяется на 3, либо остается прежней, то есть после любых операций разность должна измениться на число, кратное 3.

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

Изначально разность была равна значит, она изменилась на Однако 13 не делится на 3, значит, в третьей коробке не мог оказаться 141 камень.

а) Покажем, как переместить ровно три камня из второй коробки в третью:

За 6 раз такими операциями мы можем переместить 18 камней из второй коробки в третью. Значит, могло оказаться так, что в первой коробке лежат 64 камня, во второй — 59 камней, а в третьей — 18 камней.

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

Тогда посмотрим на изначальную разность между второй и первой коробками. Она равна По условию в первой коробке оказался 1 камень.

Найдем наименьшее количество камней, которое могло оказаться во второй коробке. Так как разность изменяется на число, кратное 3, то имеем:

Тогда в третьей коробке может быть не более камней.

Покажем, как можно добиться 138 камней ровно. Сначала научимся перемещать по 3 камня в третью коробку из каждой другой:

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

Теперь будем перекладывать по 3 камня из второй коробки в третью:

Окончательно имеем:

Полуинвариант

Напомним, что инвариантом называется величина, не меняющаяся при некотором процессе.

Теперь скажем, что полуинвариант — величина, которая при некотором процессе может меняться только в одну сторону: она либо всегда уменьшаться, либо всегда увеличиваться.

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

4.  В клетках таблицы расставлены плюсы и минусы. Если в каком-то ряду (строке или столбце) минусов больше чем плюсов, разрешается в этом ряду поменять все знаки на противоположные. Докажите, что через некоторое время и во всех строках, и во всех столбцах плюсов будет больше чем минусов.

Решение. Рассмотрим общее количество плюсов. Заметим, что при указанной в условии операции это количество постоянно увеличивается хотя бы на 1.

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

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

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

Решение. Посмотрим, что происходит с периметром всей клетчатой фигуры, заросшей бурьяном. Когда новая клетка заполняется бурьяном, она имеет хотя бы две заросшие соседние клетки, а значит хотя бы две ее стороны уже до ее заполнения посчитаны в общем периметре всей фигуры. Тогда после ее заполнения она сможет добавить в периметр не более двух новых сторон, то есть увеличить периметр не более, чем на 2. При этом все ее стороны, которыми она примыкает к соседним заросшим клеткам, «удалятся» из периметра, то есть больше не будут на границе фигуры. Значит, периметр уменьшится хотя бы на 2. Итого, после одной операции периметр не увеличится.

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