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

Ответы

Violetta291 07.10.2020 08:59

Посмотрим, какое количество камней могло остаться в конце игры:
Такое, что половина этого количества ≤ 1 (иначе можно взять 1 камень и это будет не конец игры).
То есть могло остаться 0, 1 или 2
Если осталось 0 (или 1), то на предыдущем ходе количество камней было меньше, чем 0 * 2 = 0 (или 1 * 2 = 2), то есть < 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 раза меньньше, чем $2^{k+1}$ , а по условию можно взять строго меньше, чем в 2 раза). Тогда мы получим кучку с количеством камней от
$2^{k+1}-(2^k-1)=2^k+1$
до
$2^{k+1}-1$
Начиная с которой по пункту 1) этого доказательства оппонент выигрывает.
Что и требовалось доказать.

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

ПОКАЗАТЬ ОТВЕТЫ

Другие вопросы по теме Математика