Анализ позиций
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
В некоторых клетках клетчатой полосы 
стоят фишки. В первой клетке (самой левой) 
штук, во второй — 
…, в 
-й клетке —
Двое игроков играют в следующую игру: каждым ходом первый игрок выбирает некоторое подмножество фишек, а второй либо
передвигает все фишки этого подмножества на 1 клетку влево, а остальные убирает с доски, либо делает то же самое с дополнением
выбранного подмножества. Первый хочет, чтобы какая-то фишка оказалась в самой первой клетке, а второй хочет ему помешать. При каких
у первого игрока есть выигрышная стратегия?
Подсказка 1
Заметим, что ближе фишка к первой клетке, тем она "ценнее" для первого игрока, ведь её легче привести на первую клетку. Может попробовать ввести веса для фишки, стоящей в клетке k, чтобы отобразить эту ценность?
Подсказка 2
Пусть вес wₖ = 1/2ᵏ⁻¹. Как изменяется вес фишки при её сдвиге на 1 влево?
Подсказка 3
Вес удваивается (wₖ → 2wₖ). Как реинтерпретировать ход в терминах суммарного веса W?
Подсказка 4
Первый делит все фишки на группы весов Wₐ и Wₛ, Wₐ+Wₛ=W, второй выбирает одну группу, удваивает её вес и убирает другую; новый суммарный вес = 2·min(Wₐ,Wₛ).
Подсказка 5
Вес фишки в первой клетке равен 1. Какой простой критерий гарантирует победу первому игроку?
Подсказка 6
Если начальный суммарный вес W ≥ 1, то первый может выиграть, для этого надо поддерживать инвариант W ≥ 1. Как делить фишки, чтобы сохранить инвариант W ≥ 1?
Подсказка 7
Нужно разбивать текущую массу на две части так, чтобы каждая имела вес ≥ 1/2, после второго хода вес удвоится. А можно ли всегда разделить мультимножество двоичных дробей (1/2,1/4,1/8, ...) с суммой W ≥ 1 на две части с массой ≥ 1/2?
Подсказка 8
Что делать, если W₀ < 1 — есть ли стратегия у второго игрока?
Подсказка 9
Второй игрок всегда выбирает группу меньшей массы; тогда новое W' = 2·min(Wₐ,Wₛ) ≤ W₀ < 1, следовательно, вес остаётся < 1, и победа первого невозможна.
Введем весовую функцию для каждой фишки. Фишке, находящейся в клетке с номером 
присвоим вес 
Суммарный вес всех
фишек на полосе в начальный момент времени обозначим как
Цель первого игрока — добиться появления на доске фишки с весом 1 (т. е. фишки в первой клетке). Когда фишка сдвигается из клетки
в клетку 
ее вес удваивается.
Игра в терминах весов выглядит следующим образом:
- 1.
-
Первый игрок разделяет множество всех фишек с общим весом
на два подмножества с весами 
и 
где
- 2.
-
Второй игрок выбирает одно из подмножеств (например,
), удваивает его вес и убирает второе. Новый суммарный вес
всех фишек на доске становится 
Второй игрок стремится минимизировать эту величину.
Докажем критерий выигрыша в обе стороны.
Случай 1: 
Докажем, что в этом случае первый игрок выигрывает. Стратегия первого игрока: на каждом ходу
поддерживать инвариант — суммарный вес всех фишек на доске 
Для этого на каждом шаге он должен делить
текущее множество фишек с общим весом 
на два подмножества, 
и 
так, чтобы их веса удовлетворяли
условиям
______________________________________________________________________________________________________________________________________________________
Лемма. Любое мультимножество фишек с весами из набора
и суммарным весом 
можно разбить на два подмножества, вес каждого из которых не менее 
Доказательство леммы. Будем последовательно заменять в мультимножестве пары одинаковых дробей 
(где 
) одной
дробью 
Этот процесс не меняет общую сумму и в итоге приведет к мультимножеству, в котором каждая дробь
вида 
(при 
) встречается не более одного раза. Если после этого в наборе есть хотя бы две дроби 
то
разбиение очевидно. В противном случае (не более одной дроби 
) сумма всех дробей, кроме, возможно, целых, строго
меньше
Это противоречит условию, что исходная сумма 
Значит, после упрощения мы получим либо целую часть, либо достаточное
количество дробей 
для разбиения.
_________________________________________________________________________________________________________________________________________________________________________________
Следуя этой лемме, первый игрок делит фишки на две группы с весами 
и 
Второй игрок вынужден выбрать одну
из них, и новый суммарный вес станет
Таким образом, суммарный вес фишек никогда не опускается ниже 1. Поскольку на каждом ходу хотя бы одна фишка сдвигается влево, игра конечна. Она не может закончиться исчезновением всех фишек (так как это состояние с весом 0). Следовательно, игра должна закончиться появлением фишки в первой клетке (весом 1).
Случай 2: 
Докажем, что в этом случае выигрывает второй игрок.
Стратегия второго игрока: после того как первый разделит фишки на группы 
и 
выбирать ту, у которой вес меньше. Пусть
Тогда 
так как 
Второй игрок оставляет группу 
и новый вес становится
Так как суммарный вес всегда остается меньше 1, состояние победы для первого игрока (фишка с весом 1) недостижимо.
У первого игрока есть выигрышная стратегия при 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
