Яндекс Учебник Петя и Ваня решили поиграть. Перед ними лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: • убрать из кучи два камня • убрать из кучи четыре камня • уменьшить количество камней в куче в два раза (с округлением в большую сторону) Например, из кучи в 39 камней за один ход можно получить кучу из 37, 35 или 20 камней. Игра завершается, когда количество камней в куче становится не более 35. Победителем считается игрок, который сделал последний ход, то есть в результате его действия в куче стало 35 камней или меньше. До начала игры в куче было S камней, S ≥ 36. У игрока выигрышная стратегия, если он может выиграть при любых ходах противника. Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

Для решения задачи определим критерии выигрыша и проигрыша для каждого игрока, например, будем обозначать: - Состояние, в котором игрок, который должен ходить, может гарантированно выиграть, будем считать "выигрышным" состоянием. - Состояние, в котором игрок вынужден проиграть, — "проигрышным" состоянием. Обратите внимание, что игра заканчивается, когда количество камней становится 35 или меньше. Следовательно, если игрок приводит к такому состоянию, он выигрывает. Теперь давайте проанализируем возможные состояния: 1. Если на очереди игрок с количеством камней 35 или меньше, он выигрывает (это выигрышное состояние). 2. Если у игрока 36 камней, он может сделать следующий ход: - Убрать 2, в результате получится 34 (выигрышное состояние). - Убрать 4, в результате получится 32 (выигрышное состояние). - Уменьшить вдвое, в результате получится 18 (выигрышное состояние). Это проигрышное состояние для игрока. 3. Теперь рассмотрим 37 камней: - Убрать 2, останется 35 (выигрышное состояние). - Убрать 4, останется 33 (выигрышное состояние). - Уменьшить пополам, останется 19 (выигрышное состояние). Это также проигрышное состояние для игрока. 4. Анализируем 38 камней: - Убрать 2, останется 36 (проигрышное состояние). - Убрать 4, останется 34 (выигрышное состояние). - Уменьшить пополам, останется 19 (выигрышное состояние). Это выигрышное состояние. 5. Анализируем 39 камней: - Убрать 2, останется 37 (проигрышное состояние). - Убрать 4, останется 35 (выигрышное состояние). - Уменьшить пополам, останется 20 (выигрышное состояние). Это также выигрышное состояние. 6. Анализируем 40 камней: - Убрать 2, останется 38 (выигрышное состояние). - Убрать 4, останется 36 (проигрышное состояние). - Уменьшить пополам, останется 20 (выигрышное состояние). Это выигрышное состояние. 7. Анализируем 41 камней: - Убрать 2, останется 39 (выигрышное состояние). - Убрать 4, останется 37 (проигрышное состояние). - Уменьшить пополам, останется 21 (выигрышное состояние). Это выигрышное состояние. 8. Анализируем 42 камня: - Убрать 2, останется 40 (выигрышное состояние). - Убрать 4, останется 38 (выигрышное состояние). - Уменьшить пополам, останется 21 (выигрышное состояние). Это выигрышное состояние. 9. Анализируем 43 камня: - Убрать 2, останется 41 (выигрышное состояние). - Убрать 4, останется 39 (выигрышное состояние). - Уменьшить пополам, останется 22 (выигрышное состояние). Это выигрышное состояние. 10. Анализируем 44 камня: - Убрать 2, останется 42 (выигрышное состояние). - Убрать 4, останется 40 (выигрышное состояние). - Уменьшить пополам, останется 22 (выигрышное состояние). Это выигрышное состояние. 11. Анализируем 45 камней: - Убрать 2, останется 43 (выигрышное состояние). - Убрать 4, останется 41 (выигрышное состояние). - Уменьшить пополам, останется 23 (выигрышное состояние). Это выигрышное состояние. 12. Анализируем 46 камней: - Убрать 2, останется 44 (выигрышное состояние). - Убрать 4, останется 42 (выигрышное состояние). - Уменьшить пополам, останется 23 (выигрышное состояние). Это выигрышное состояние. 13. Анализируем 47 камней: - Убрать 2, останется 45 (выигрышное состояние). - Убрать 4, останется 43 (выигрышное состояние). - Уменьшить пополам, останется 24 (выигрышное состояние). Это выигрышное состояние. 14. Анализируем 48 камней: - Убрать 2, останется 46 (выигрышное состояние). - Убрать 4, останется 44 (выигрышное состояние). - Уменьшить пополам, останется 24 (выигрышное состояние). Это выигрышное состояние. 15. Анализируем 49 камней: - Убрать 2, останется 47 (выигрышное состояние). - Убрать 4, останется 45 (выигрышное состояние). - Уменьшить пополам, останется 25 (выигрышное состояние). Это выигрышное состояние. 16. Анализируем 50 камней: - Убрать 2, останется 48 (выигрышное состояние). - Убрать 4, останется 46 (выигрышное состояние). - Уменьшить пополам, останется 25 (выигрышное состояние). Это выигрышное состояние. 17. Анализируем 51 камней: - Убрать 2, останется 49 (выигрышное состояние). - Убрать 4, останется 47 (выигрышное состояние). - Уменьшить пополам, останется 26 (выигрышное состояние). Это выигрышное состояние. 18. Анализируем 52 камня: - Убрать 2, останется 50 (выигрышное состояние). - Убрать 4, останется 48 (выигрышное состояние). - Уменьшить пополам, останется 26 (выигрышное состояние). Это выигрышное состояние. 19. Анализируем 53 камня: - Убрать 2, останется 51 (выигрышное состояние). - Убрать 4, останется 49 (выигрышное состояние). - Уменьшить пополам, останется 27 (выигрышное состояние). Это выигрышное состояние. 20. Анализируем 54 камня: - Убрать 2, останется 52 (выигрышное состояние). - Убрать 4, останется 50 (выигрышное состояние). - Уменьшить пополам, останется 27 (выигрышное состояние). Это выигрышное состояние. 21. Анализируем 55 камней: - Убрать 2, останется 53 (выигрышное состояние). - Убрать 4, останется 51 (выигрышное состояние). - Уменьшить пополам, останется 28 (выигрышное состояние). Это выигрышное состояние. 22. Анализируем 56 камней: - Убрать 2, останется 54 (выигрышное состояние). - Убрать 4, останется 52 (выигрышное состояние). - Уменьшить пополам, останется 28 (выигрышное состояние). Это выигрышное состояние. 23. Анализируем 57 камней: - Убрать 2, останется 55 (выигрышное состояние). - Убрать 4, останется 53 (выигрышное состояние). - Уменьшить пополам, останется 29 (выигрышное состояние). Это выигрышное состояние. 24. Анализируем 58 камней: - Убрать 2, останется 56 (выигрышное состояние). - Убрать 4, останется 54 (выигрышное состояние). - Уменьшить пополам, останется 29 (выигрышное состояние). Это выигрышное состояние. 25. Анализируем 59 камней: - Убрать 2, останется 57 (выигрышное состояние). - Убрать 4, останется 55 (выигрышное состояние). - Уменьшить пополам, останется 30 (выигрышное состояние). Это выигрышное состояние. 26. Анализируем 60 камней: - Убрать 2, останется 58 (выигрышное состояние). - Убрать 4, останется 56 (выигрышное состояние). - Уменьшить пополам, останется 30 (выигрышное состояние). Это выигрышное состояние. 27. Анализируем 61 камень: - Убрать 2, останется 59 (выигрышное состояние). - Убрать 4, останется 57 (выигрышное состояние). - Уменьшить пополам, останется 31 (выигрышное состояние). Это выигрышное состояние. 28. Анализируем 62 камня: - Убрать 2, останется 60 (выигрышное состояние). - Убрать 4, останется 58 (выигрышное состояние). - Уменьшить пополам, останется 31 (выигрышное состояние). Это выигрышное состояние. 29. Анализируем 63 камня: - Убрать 2, останется 61 (выигрышное состояние). - Убрать 4, останется 59 (выигрышное состояние). - Уменьшить пополам, останется 32 (выигрышное состояние). Это выигрышное состояние. 30. Анализируем 64 камня: - Убрать 2, останется 62 (выигрышное состояние). - Убрать 4, останется 60 (выигрышное состояние). - Уменьшить пополам, останется 32 (выигрышное состояние). Это выигрышное состояние. 31. Анализируем 65 камней: - Убрать 2, останется 63 (выигрышное состояние). - Убрать 4, останется 61 (выигрышное состояние). - Уменьшить пополам, останется 33 (выигрышное состояние). Это выигрышное состояние. 32. Анализируем 66 камней: - Убрать 2, останется 64 (выигрышное состояние). - Убрать 4, останется 62 (выигрышное состояние). - Уменьшить пополам, останется 33 (выигрышное состояние). Это выигрышное состояние. 33. Анализируем 67 камней: - Убрать 2, останется 65 (выигрышное состояние). - Убрать 4, останется 63 (выигрышное состояние). - Уменьшить пополам, останется 34 (выигрышное состояние). Это выигрышное состояние. 34. Анализируем 68 камней: - Убрать 2, останется 66 (выигрышное состояние). - Убрать 4, останется 64 (выигрышное состояние). - Уменьшить пополам, останется 34 (выигрышное состояние). Это выигрышное состояние. 35. Анализируем 69 камней: - Убрать 2, останется 67 (выигрышное состояние). - Убрать 4, останется 65 (выигрышное состояние). - Уменьшить пополам, останется 35 (выигрышное состояние). Это выигрышное состояние. 36. Анализируем 70 камней: - Убрать 2, останется 68 (выигрышное состояние). - Убрать 4, останется 66 (выигрышное состояние). - Уменьшить пополам, останется 35 (выигрышное состояние). Это выигрышное состояние. 37. Переходим к 71 камням: - Убрать 2, останется 69 (выигрышное состояние). - Убрать 4, останется 67 (выигрышное состояние). - Уменьшить пополам, останется 36 (проигрышное состояние). Это выигрышное состояние. 38. Переходим к 72 камням: - Убрать 2, останется 70 (выигрышное состояние). - Убрать 4, останется 68 (выигрышное состояние). - Уменьшить пополам, останется 36 (проигрышное состояние). Это выигрышное состояние. И в конце, для 73 камней: - При убирании 2, останется 71 (выигрышное состояние). - Убрав 4, останется 69 (выигрышное состояние). - Уменьшить вдвое, останется 37 (проигрышное состояние). Таким образом, мы видим, что для первоначального количества камней S = 36, 37, 38, 39, 40, 41, 42, 43, 44 и 45 — везде существует выигрышная стратегия для первого игрока. Проверяя S от 36 до 70, мы видим, что 36 - это значение, где игра относится к началу и 37- это значение, в котором первый игрок проигрывает. Следовательно, минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Вани он может выиграть своим первым ходом, будет равно **36**.