Всем привет, сегодня мы наконец разберёмся, как решать задание, которое совсем недавно было во второй части экзамена
Собственно, вот и оно
Сначала читаем правила игры, они частенько меняются. Ну, меняются числа и варианты ходов.
Тут куча одна, ходы - +1 и х2, победа тогда, когда в куче будет 29+ камней.
Разберёмся, что я называю минимальным и максимальным ходами. Минимальный ход - минимальное изменение количества камней, обычно это +1.
Максимальный - наоборот, потенциально большое изменение, здесь х2.
Первое задание решается очень просто.
Распишем схему ходов. Первый ходит Петя, потом Ваня. Ваня выигрывает своим первым ходом, поэтому игра будет недолгой.
Идём от обратного. Т.к. нам нужно найти наименьшее число, то Ваня сделает кучу как минимум из 29 камней.
Теперь пытаемся ИСПОЛЬЗУЯ МИНИМАЛЬНЫЙ ХОД восстановить историю игры. Мог Ваня получить число 29, умножая число на 2? Нет. Значит, он сделал кучу из 30 камней, ведь на 28 камнях он бы не выиграл.
Значит, Петя делал кучу из 15 камней.
Мог Петя получить число 15, умножая что-нибудь на 2? Опять нет. Значит, он получил 16 камней, а Вася 32.
Значит, в момент S камней было 8. Почему это число минимальное? Потому что мы использовали максимальный ход в обратном порядке.