Игры → .04 Равновесия в играх

Для решения достаточно привести стратегию за первого, при которой он гарантированно объедает второго, а также стратегию за второго, при которой гарантированно первый если и объедает его, то не более, чем на граммов.

Начнём со стратегии для первого. Пусть он на каждом шаге берёт самое тяжёлое яблоко. Тогда если на м шаге первый взял яблоко с весом а второй — c весом то (на последнем шаге второму может не достаться яблока, если количество яблок нечётное, и в этом случае считаем, что Следовательно, первый однозначно объест второго.

Теперь приведём стратегию за второго. Стратегия будет аналогичной, второй на каждом шаге берёт самое тяжелое яблоко из имеющихся. Пусть первый взял на первом шаге яблоко с весом Теперь рассмотрим й и й шаги. Второй на м шаге взял яблоко с весом а первый на м — с весом Ясно, что Таким образом, если не учитывать первое яблоко, второй объел первого. А если его учесть, то первый если и смог объесть второго, то не более чем на граммов, потому что

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

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

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

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

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

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