Посмотрим, какое количество камней могло остаться в конце игры: Такое, что половина этого количества ≤ 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 камней - выиграет. Но мы остаток докажем методом математической индукции. Пытаемся доказать предположение, что тот, кому попалась кучка из (n строго больше 1) элементов проиграет, а тот, кому попалась кучка с числом камней, не равным степени 2 - выигрывает.
База индукции у нас уже есть. Предположим, что тот, у кого выпало камней - проигрывает, а - выигрывает. Докажем, что тот, кому выпало камней выиграет, а тот, кому выпало камней - проиграет.
1) Пусть выпало камней, . Тогда мы можем взять эти l камней. Дейтсвительно, из того, что
следует, что
Итак, оппонент после этого хода попадает на кучку из камней и, по предположению индукции, проигрывает
2) Пусть выпало камней. Тогда можно взять любое количество от 1 до (так как ровно в 2 раза меньньше, чем , а по условию можно взять строго меньше, чем в 2 раза). Тогда мы получим кучку с количеством камней от
до
Начиная с которой по пункту 1) этого доказательства оппонент выигрывает. Что и требовалось доказать.
Таким образом, так как 2017 - это не степень двойки, то начиная с 2017 Петя победит. Его стратегия - забирать камни так, чтобы в кучке оставалось число камней, являющееся точной степенью 2.
21 монету перевернуть нельзя, потому что при каждом перевороте остается нечетное количество монет решкой вверх. А 20 монет можно, потому что четность все время меняется. Для 20 монет (переворачиваем по 19 каждый раз) алгоритм такой. 0) Сначало лежит 20 монет решкой вверх. 1) Переворачиваем 19 орлом вверх. 1 остается решкой вверх. 2) Переворачиваем решку и 18 орлов. Стало 18 решек и 2 орла вверх. Один орел - которого не перевернули, второй - которого перевернули с решки. 3) Переворачиваем 2 орла и 17 решек. Стало 3 решки и 17 орлов вверх. 4) Переворачиваем 3 решки и 16 орлов. Стало 16 решек и 4 орла вверх. ... 9) Переворачиваем 9 решек и 10 орлов. Стало 11 решек и 9 орлов вверх. 10) Переворачиваем 10 орлов и 9 решек. Стало 10 решек и 10 орлов вверх. Тут главное не запутаться, потому что орлы и решки сравнялись. 11) Переворачиваем 10 орлов и 9 решек. Стало 11 решек и 9 орлов вверх. 12) Переворачиваем 11 решек и 8 орлов. Стало 12 орлов и 8 решек вверх.
19) Переворачиваем 18 орлов и 1 решку. Стало 19 решек и один орел вверх. 20) Переворачиваем 19 решек. Стало 20 орлов.) Всё вроде бы
Такое, что половина этого количества ≤ 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 камней - выиграет. Но мы остаток докажем методом математической индукции.
Пытаемся доказать предположение, что тот, кому попалась кучка из (n строго больше 1) элементов проиграет, а тот, кому попалась кучка с числом камней, не равным степени 2 - выигрывает.
База индукции у нас уже есть. Предположим, что тот, у кого выпало камней - проигрывает, а - выигрывает. Докажем, что тот, кому выпало камней выиграет, а тот, кому выпало камней - проиграет.
1) Пусть выпало камней, . Тогда мы можем взять эти l камней. Дейтсвительно, из того, что
следует, что
Итак, оппонент после этого хода попадает на кучку из камней и, по предположению индукции, проигрывает
2) Пусть выпало камней. Тогда можно взять любое количество от 1 до (так как ровно в 2 раза меньньше, чем , а по условию можно взять строго меньше, чем в 2 раза). Тогда мы получим кучку с количеством камней от
до
Начиная с которой по пункту 1) этого доказательства оппонент выигрывает.
Что и требовалось доказать.
Таким образом, так как 2017 - это не степень двойки, то начиная с 2017 Петя победит. Его стратегия - забирать камни так, чтобы в кучке оставалось число камней, являющееся точной степенью 2.
Для 20 монет (переворачиваем по 19 каждый раз) алгоритм такой.
0) Сначало лежит 20 монет решкой вверх.
1) Переворачиваем 19 орлом вверх. 1 остается решкой вверх.
2) Переворачиваем решку и 18 орлов. Стало 18 решек и 2 орла вверх.
Один орел - которого не перевернули, второй - которого перевернули с решки.
3) Переворачиваем 2 орла и 17 решек. Стало 3 решки и 17 орлов вверх.
4) Переворачиваем 3 решки и 16 орлов. Стало 16 решек и 4 орла вверх.
...
9) Переворачиваем 9 решек и 10 орлов. Стало 11 решек и 9 орлов вверх.
10) Переворачиваем 10 орлов и 9 решек. Стало 10 решек и 10 орлов вверх.
Тут главное не запутаться, потому что орлы и решки сравнялись.
11) Переворачиваем 10 орлов и 9 решек. Стало 11 решек и 9 орлов вверх.
12) Переворачиваем 11 решек и 8 орлов. Стало 12 орлов и 8 решек вверх.
19) Переворачиваем 18 орлов и 1 решку. Стало 19 решек и один орел вверх.
20) Переворачиваем 19 решек. Стало 20 орлов.)
Всё вроде бы