Лесенка

Материал из Algocode wiki
Перейти к: навигация, поиск

Задача

Есть лестница с $n$ ступеньками (занумерованными от 1 до $n$), на $i$-ой ступеньке лежит $a_i$ монет. За один ход разрешается переместить некоторое ненулевое число монет с $i$-ой на $i-1$-ую ступеньку. Проигрывает тот, кто не может сделать хода.

Решение

Возьмем ним только с четными номерами ступенек($a_{2}, a_{4}, \dots$).

Есть два варианта хода :

Мы можем положить со ступеньки $i$ с четным номером на ступеньку $i - 1$ с нечетным номером $x$ камней, но такое действие эквивалентно действию в ниме(забрать из $i$-ой кучки $x$ камней).

Мы можем положить со ступеньки $i$ с нечетным номером на ступеньку $i - 1$ с четным номером $x$ камней, но такое действие эквивалентно действию в ниме с прибавлением (прибавить к $i$-ой кучке $x$ камней), а следовательно мы можем в победной стратегии на него ответить, тем что заберем с $i - 1$ ступеньки $x$ камней, так как сумма количества камней конечна, то и количество действий конечно, а следовательно игра ациклична.



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin