Равновесия в играх

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

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

Теперь докажем, что Бяо может всегда действовать так, чтобы после поворота второго кубика совпало хотя бы ребер. Выделим произвольное ребро на первом кубе. Отметим, что второй куб всегда можно повернуть так, чтобы направление на этом ребре у них совпало. Действительно, возможно, оно у них и так совпадает, и поворот не требуется. Иначе, выделим произвольную грань, которой принадлежит это ребро, и рассмотрим композицию поворота на относительно оси, перпендикулярной этой грани, и на относительно оси, параллельной этой грани. Первый поворот переводит ребро в противоположное на выбранной грани, а второй – наоборот, переводит противоположное ребро в исходное. В результате этих двух поворотов получилась расстановка стрелочек, в которой направление выбранного ребра поменялось. Это означает, что из всех способов поворота второго куба ровно у половины направление на выделенном ребре совпадает с направлением на первом кубе, и ровно у половины – нет. Действительно, композиция поворота на относительно оси, параллельной фиксированной грани, и поворота на относительно оси, перпендикулярной этой грани, является обратным преобразованием к композиции выше. Поэтому композиция поворотов выше является взаимно однозначным соответствием, и разбивает все повороты второго куба на пары, в каждой из которых у одного поворота направление на фиксированном ребре совпадает с первым кубом, а у другого – нет.

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

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

Ивану достаётся многочлен нечетной степени, поэтому он не может проиграть. Однако Кощей тоже не может проигрывать: для этого ему достаточно каждый раз выбирать положительный корень. Заметим, что свободный член всегда равен Легко проверить, что при такой стратегии Кощея Ивану будут доставаться многочлены нечетной степени с чередующимися знаками коэффициентов (старший - положительный), и поэтому у них есть лишь положительные корни; а Кощею будут доставаться многочлены четной степени с положительным старшим коэффициентом и свободным членом поэтому у них существует положительный корень