Есть кучка из 2017 камней. Петя и Вася по очереди берут

Question

Есть кучка из 2017 камней. Петя и Вася по очереди берут

Есть кучка из 2017 камней. Петя и Вася по очереди берут из неё камешки (начинает Петя). Разрешается брать строго меньше половины от текущего числа камешков. Проигрывает тот, кто не может сделать ход. Кто выиграет?

Задать свой вопрос

Диана Зензинова 2019-08-21 02:23:23

На всякий случай: я НЕ смогла найти решение в вебе!

Оля 2019-08-21 02:25:13

С обоснованием, пожалуйста)

Гарелкин Николай
Математика
2019-08-21 02:19:06
1
1

1 ответ

, оставишь ответ?

Имя:*

E-Mail:

Похожие вопросы

Расставить знаки плюс минус умножить поделить и скобки в образце 96

Перевидите пожалуйста текст!

допишите окончания прилегательных,определите падеж в

Решите пожалуйста британский

Найдите слова-определения, выраженные сущ. 1. There are many new machine

Написать ЭССЕ на тему Совесть

Как получают данные о погоде на нашей планете и делают её

решите пример (1837371813529)+(10000005)150

Сделайте словообразовательный разбор следующих

Розв039;язати рвняння:А) 2^х-1=4Б) 0,5^2х-1=0,125В) (1/3)^х+1=1/81Г) 27^х=1/27

Вован Гарькавый · Answer 1 · 2019-08-21 02:20:05+3:00

Поглядим, какое количество камешков могло остаться в конце забавы:
Такое, что половина этого количества 1 (иначе можно брать 1 камень и это будет не конец забавы).
То есть могло остаться 0, 1 либо 2
Если осталось 0 (или 1), то на прошлом ходе количество камешков было меньше, чем 0 * 2 = 0 (или 1 * 2 = 2), то есть lt; 0 камней (1 камень), чего быть не могло. Означает осталось 2 камня.
Сейчас мы знаем, что тот, кому после очередного хода выпала кучка с 2 камнями, проигрывает.
Значит тот, кому выпала кучка с более, чем 2 камнями, но менее, чем с 2 * 2 - выигрывает (это кучка из 3 камней. Он берет 1 камень и выигрывает).
Проводя подобные рассуждения мы увидим, что тот, кому выпадает кучка с 4 камнями - проигрывает (единственный вероятный ход - взять 1 камень, что приводит к 3 камням, а тот, кто начинает с кучки из 3 камешков выигрывает).

Можно бы было далее посмотреть, что тот, у кого в кучке 8 камешков проиграет, а тот, у кого в кучке 5 .. 7 камней - выиграет. Но мы остаток докажем методом математической индукции.
Пытаемся доказать предположение, что тот, кому попалась кучка из $2^n$ (n взыскательно больше 1) частей проиграет, а тот, кому попалась кучка с числом камней, не одинаковым ступени 2 - выигрывает.

База индукции у нас теснее есть. Представим, что тот, у кого выпало $2^k$ камешков - проигрывает, а $2^k-1+1\, ...\, 2^k-1$ - выигрывает. Докажем, что тот, кому выпало $2^k+1\, ...\, 2^k+1-1$ камешков выиграет, а тот, кому выпало $2^k$ камешков - проиграет.

1) Пусть выпало $2^k + l$ камешков, $0 \ \textless \ l \ \textless \ 2^k$ . Тогда мы можем брать эти l камней. Дейтсвительно, из того, что
$l \ \textless \ 2^k$
следует, что
$2l \ \textless \ 2^k+l \Rightarrow l \ \textless \ 2^k+l\over 2$
Итак, оппонент после этого хода попадает на кучку из $2^k$ камешков и, по предположению индукции, проигрывает

2) Пусть выпало $2^k+1$ камешков. Тогда можно брать любое количество от 1 до $2^k -1$ (так как $2^k$ ровно в 2 раза меньньше, чем $2^k+1$ , а по условию можно брать требовательно меньше, чем в 2 раза). Тогда мы получим кучку с количеством камешков от
$2^k+1-(2^k-1)=2^k+1$
до
$2^k+1-1$
Начиная с которой по пт 1) этого подтверждения оппонент выигрывает.
Что и требовалось обосновать.

Таким образом, так как 2017 - это не ступень двойки, то начиная с 2017 Петя одолеет. Его стратегия - забирать камешки так, чтоб в кучке оставалось число камешков, являющееся четкой ступенью 2.

О проекте

Есть кучка из 2017 камней. Петя и Вася по очереди берут

Добро пожаловать!