Этюды о полуинварианте

63

Этюды
о полуинварианте

Л. Д. КУРЛЯНДЧИК, Д. В. ФОМИН

Если вы пожелаете совместить приятное с полезным, то запаситесь кульком конфер и пограйте вдвоем с приятельем в такую игру. Сложите на столе две кучки конфер, в первой — 12 конфер, а во второй — 13. За ход каждой из вас может либо съеть две конферты из одной кучки, либо переложить одну конферту из первой кучки во вторую. Проигрывает тот, кто не может сделать хода.

Если ваш ресурсы позволят вам пограть в эту замечательную игру достагоно долго, то вы заметите странную закономерность: начинающий всегда проигрывает! Впрочем, причину этого легко понять. Дело в том, что при каждом ходе разность между количеством конфер во второй и первой кучке меняется на два. Значит, остatok от деления этой разности на 4 будет изменяться строго определенным образом: 1, 3, 1, 3, 1, 3,… Мы видим, что при каждом ходе второго игрока этот остatok будет равен trem. Но игра-то прекращается, только если конферты кончились или осталасьровно одна конферта, причем во второй кучке. Такая ситуация не может возникнуть при ходе второго игрока.

Очень возможно, что идея этого рассуждения вам известна, в частности, если ваш «читательский стаж» достаточно велик, вы могли встретить подобные рассуждения в стране «Пониск инварианта» («Квант», 1976, № 2). Помните? Инвариант — это то, что не меняется. А здесь как раз через каждые два хода не меняется остatok при делении на четые разности чисел конфер в кучках. (Это сообщение применимо, конечно, и при любом другом числе конфер.) Однако наша

65

ную картинику, состоящую из $n$ прямы и $n$ перпендикуляров. Выберем на ней два пересекающих перпендикуляра и применим нашу операцию: заменим эти два перепендикуляра на два других с меньшей суммой длин. В полученной картинике снова найдем два пересекающих перпендикуляра, снова применим к ним нашу операцию и так далее. Тогда либо на каком-то шаге мы получим картинику с попарно непересекающимся перпендикулярами, либо в конце концов получим картинику с минимально возможной суммой длин перпендикуляров (так как эта сумма может принимать лишь конечное число значений; почему?). Эта картиника и является исключой: если два перепендикуляра на ней пересекаются, то, применив нашу операцию еще раз, мы получили бы картинику с еще меньшей суммой длин перпендикуляров.

Проанализируем эти два решения. Мы действовали в них по одному схеме: вводили неокоторую величины (в первой задаче это сумма всех чисел таблицы, а во второй — сумма длини перпендикуляров) и операцию, в результате применения которой эта величина менялась определенным образом: в первой задаче увеличивалась, а во второй — уменьшалась. Решение основываясь на том, что введенная величина может принимать лишь конечное число различных значений. Следовательно, данная операция может быть применена лишь конечное число раз, и мы неизбежно придет к требуемой в задаче ситуации.

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

Кроме того, второй задача — прекрасный пример того, как легко можно получить по ложному следу: новые перепендикуляры $AA_2$ и $BB_2$ не пересекаются, и поэтому каждым следу за количество точек пересечения наших $n$ перпендикуляров, которое, на первый взгляд, всегда уменьшается при описанной операции. Однако это не так (постройте соответствующий пример).

Научиться придумывать нужную пару «операция — величина» далее не просто. Здесь требуется опит и интуиция.

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

Следующую задачу также можно отнести к разряду хорошего известных.

Задание 3. Докажите, что любые 2$n$ точек на плоскости являются концами $n$ пересекающих отрезков.

Проведем $n$ отрезков с концами в данных точках произвольным образом. Если никакие два из них не пересекаются, то требование задачи выполняно. В противном случае рассмотрим пару пересекающих отрезков $AB$ и $CD$ (рис.2). В качестве исключения естественно рассмотрить замену пересечения отрезков $AB$ и $CD$ на пересекающую отрезки $AC$ и $BD$.

Осталось найти получиванент — величины, которая при этой операции ведет себя монотно. Так как сумма длини диагоналей $AB$ и $CD$ выпуклого четырехугольника $ACBD$ больше, чем

66

сумма длины противоположных сторон AC и BD, в качестве полупваранта можно взять сумму длины n отрезков. Ясно, что эта сумма может принимать лишь конечное число значений. Рассуждая так же, как в предыдущей задаче, в конце концов получаем набор из n отрезков с минимальной суммой длины. Нетрудно понять, что в нем никакие два отрезка не пересекаются.

В задаче 3, по сути дела, вначале не было ни операции, ни полупваранта. Однако после того, как мы подбрали операцию, выбор полупваранта не представлял труда.

Задача 4. По окружности расстояния n чисел. Если подряд стоит числа a, b, c и d и при этом (a-d)(b-c)>0, то числа b и c разрезается поменять местами. Докажите, что через несколько шагов нам не удался произвести ни одной такой перестановки.*)

Здесь операция замены чисел задана. Несмотря на то, что она затрагивает лишь два числа, удобно воспринять эту операцию на всем наборе чисел, считая, что все остальные числа операция оставляет неизменными: ведь в соответствии с нашей «философей решения» необходимо подбрать неоктору величину, зависимости от всего набора чисел.

Итак, путь подряд идущие числа a, b, c и d таковы, что (a-d)(b-c)>0, т. е. ab+cd>ac+bd. При выполнении нашей операции мы перешли отчетверки a, b, c, d кчетверке a, c, b, d, причем мы видим, что сумма произведений соседних чисел уменьшилась: ab+bc+cd>ac+cb+bd.

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

Следующая задача взята нами из книги В. В. Прасолова «Задачи по планетарии» (Часть 2, 21, 25).

Задача 5. С невеликим многоугольником производается следующие операции. Если он лежит по одному сторону от прямой AB, где A и B — несмежные вершины многоугольника, то одна из частей, на которые контур многоугольника делится точками A и B, центрально симметрично отражается относительно середины отрезка AB. Докажите, что после нескольких таких операций многоугольник становится выпуклым.

Итак, операция снова задана — это преобразование многоугольника. Полупварант, монotonно уvelичивающийся при этой операции, здесь очень видим, что сумма произведений соседних чисел уменьшилась: ab+bc+cd>ac+cb+bd.

Теперь ясно, что полупварантом в этой задаче является сумма попарных произведений相邻 соседних чисел всего набора. При данной операции полупварант уменьшается, и так как он может принимать лишь конечное число значений (почему?), то наш операция может быть применена лишь конечное число раз.

Следующая задача была предложена восемьиклассиком на Всесоюзной олимпiadе в 1979 году. Ее решили всего три участника.

Задача 6. В парамента у каждой не более трех врагов. Докажите, что парамент можно разбить на две палаты так, что у каждой

67

парламентрия в одной с ним палате будет не более одного врага.*)

Разобем parlament на палаты произвольным образом. Если у каждой parlamentaria при этом в одной с ним палате не более одного врага, то требование задачи выполнено. В противном случае рассмотрим parlamentaria $A$, у которой в одной с ним палате не менее двух врагов. В качестве полинваранта рассмотрим число пар врагов, находящемся в одной палате. Понятно, что перемещая parlamentaria $A$ в другую палату, мы уменьшаем это число. Остается лишь произвести стандартную фразу: «Полинварант может принимать лишь конечное число значений».

Следующая задача предлагалась на Московской городской олимпiadе в 1964 году. Она оказалась настолько сложной, что ее не решил ни один из участников олимпiadы.

Задача 7. При двое короля Артура собратьсь 2N рыцарей, причем каждый из них имеет среди прусуствуоших не более $N-1$ врага. Докажите, что Мерлин, советник Артура, может так рассадить рыцарей за Круглым Столом, что ни один из них не будет сидеть рядом со своим врагом.

Рассадим рыцарей за Круглым Столом произвольным образом. Если при этом получится, что никакие два врага не сидят рядом, то требование задачи выполнено. В противном случае рассмотрим рыцария $A$, сидящо слева от своего врага $B$ (рис. 4, а).

*) См. также задачу M580 («Квант», 1979, № 8).

Как и в предыдущей задаче в качестве полинваранта (это подсказывает самим условия задачи) рассмотрим число пар врагов-соседей. Нужно придумать операцию, уменьшающего это число. Это и есть самая сложная часть решения.

Среди друзей рыцария $A$ обязатьсяно найти такая рыцарь $C$, что его правый сосед $D$ — друг рыцаря $B$ (инначе у рыцаря $B$ врагов более $N-1$). Тепер «развернем» весь участок слова от $B$ до $C$ (справа от $B$, рис. 4, б) в «обратную» сторону (рис. 4, б). При этом рыцарь $B$ станет соседом рыцаря $D$, рыцарь $C$ — соседом рыцаря $A$. Остальные пары соседей не изменятся. Следовательно, полинварант действительно уменьшается.

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

Задача 8. На доске в ряд произвольным образом написаны $N$ чисел, каждое из которых равно $+1$ или $-1$. За один ход разрешается поменять знак у нескольких подряд идущих чисел. За какое наименьшее число ходов можно завершено получить из исходного набора набор из одних единиц?

Операция нам задана, а в качестве полинваранта рассмотрим число пар соседей разного знака. При выполнении одной операции замены знаков этот полинварант может измениться не более чем на два.

Рис. 4.

68

Докажем теперь, что из набора чисел —1, +1, —1, +1, … нельзя получить набор +1, +1, +1, … менее чем за [(N+1)/2] шагов. (Через [x] обозначена целая часть числа x.) Расстоянием отдельно случайного и нечетного N. Пусть N=2k, т. е. [(N+1)/2]=k. Тогда вначале получиванит равен 2k—1, а в конце он должен быть равен нулю. Но за k—1 ход добавляется требуемого невозможно.

Пусть N=2k+1, т. е. [(N+1)/2]=k+1. В этом случае получиванит исходного набора равен 2k, поэтому за k—1 ход исходный набор завершено нельзя перевести в набор из одних единиц. Докажем, что это нельзя сделать и за k ходов. Для этого достаточно заменить, что по крайней мере один раз получиванит изменится не более чем на единицу (это произойдет тогда, когда операция замены знаков затронет какие-то из крайних чисел —1).

Остается показать, что за [(N+1)/2]ходов из любого исходного набора можно получить набор из одних единиц. Выделим в исходном наборе все группы подряд иуших чисел —1, их не более [(N+1)/2]. Тепер после добавления изменим знаки у чисел этих групп.

Обращаясь в заключение к исходной задаче про конфеты, заметим, что в ней в качестве получиванита можно было взять величины 2a+b, где a — число конфет в первой кучке, а b — число конфет во второй кучке.

У разження

1. На плоскости данной 2N точек, никакие три из которых не лежат на одной прямой. N из них оказываны в краский цвет, остальные — в синий. Докажите, что эти точки можно соединить N непересекающимся отрезками, каждой из которых будет соединять краchyную точку с синой. («Квант», 1975, № 1, задача M301.)

2. На плоскости данной N точек, неоторные из которых соединены отрезками. Известно, что из любой точки выходит не более 11 отрезков. Докажите, что эти точки можно раскрыть в четыре цвета так, чтобы отрезков с однозвечными концами были не более N.

3. Задано несколько красных и несколько синих точек. Некоторые из них соединены отрезками. Известно, что точку особы, если более половины соединены с ней точек имеют цвет, отличный от ее цвета. Если хотя бы одна особы точка, то выбирается любая особы точка и перекрашивается в другой цвет. Докажите, что через конечное число шаров не останется ни одной особой точки. («Квант», 1974, № 8, задача M277; Всеосновная олимпида, 1974)

4. На каждой грани куба написано число, причем не все эти числа одинаковы. Каждый из написанных чисел заменяется на среднее арифметическое чисел, написанных на четырех соседних гранах. Могут ли через несколько таких операций на всех гранах оказаться исходные числа?

5. По окружности выписаны n натуральных чисел. Между каждыми двумя соседними числами вписывается их наиболее общий делитель. После этого прежние числа стирают, а с оставшимся проделывают ту же операцию. Докажите, что через несколько шаров все числа на окружности будут равны. (Ленинградская городская олимпида, 1973.)

6. На доске написаны 10 чисел: единица и девять нулей. Разрешается выбрать любые числа и заменить каждое их средним арифметическим. Какое наиболее число может оказаться на месте единиц после серии таких операций? (Ленинградская городская олимпида, 1984.)

7. На бесконечном клеттом листе белой бумаги несколько клеток закрашено в черный цвет. В моменты времени t=1, 2, 3, … проискают одновременное перекрашивание всех клеток листа по следующему правилу: каждая клетка K принимает тот цвет, который имело в предыдущей моменте большинство из трех клеток: самой клетки K и ее соседей справа и сверху. Докажите, что через некоторое время на листе не останется черных клеток. (Всеосновная олимпида, 1973.)

8. По кругу стоит несколько ребят, у каждой из них несколько конфеты. По сигналу ведущего каждый передает половину своих конфет стоящему справа (если число конфеты у когоибудь нечетно, то ведущий передавитель добавляет ему одну конфету). Это повторяется много раз. Докажите, что когда-нибудь у всех ребят поровну конфет. (Ленинградская городская олимпида, 1983.)

9. По одной стороны бесконечного коридора расположено бесконечное число комнат, заумерованных по порядку целыми числами, и в каждой стороне по роялю. В этих комнатах живет некоторое конечное число пинастиков (в одной комнате может жить и несколько пинастиков). Каждый день какие-то два пинастика, живущие в соседних комнатах — k-й и (k+1)-й, — приходит к выводу, что они мешают друг друга, и пересекаются соответствующим в (k—1)-ю и (k+2)-ю комнаты. Докажите, что через конечное число дней эти пересечения прекратиется. («Квант», 1984, № 6, задача M870.)

10. В библиотеке на полке в произвольном порядке расставлены N томов Британской энциклопедии. Робот-библиотекарь каждую минуту делает следующуюе: берет произвольный том, не стоящий на своей месте, и ставит его на место (т. е. если номер том — k, то он ставит его k-м по счету). Докажите, что через некоторое время все томы будут стоять на своей месте. (Ленинградская городская олимпида, 1987.)